【算法學(xué)習(xí)】再談回溯法

再談回溯法

當(dāng)當(dāng)當(dāng)，我又來(lái)了，這次又是臨時(shí)工~

眾所周知，我們老板最近很忙，

這也就是拉我來(lái)當(dāng)臨時(shí)工的原因啦。

嗯，習(xí)慣了老板文章的老觀眾可能會(huì)覺得我的內(nèi)容比較簡(jiǎn)單，

請(qǐng)不要介意，我會(huì)努力學(xué)習(xí)做出更優(yōu)秀的內(nèi)容的。。。

還是繼續(xù)邀請(qǐng)新手一起來(lái)學(xué)習(xí)算法，

這次講的是老板在兩年前寫過的算法——

回溯法。

在此感謝老板，參考了他的文章，老板賽高，老板賽高。

那么我在這里嘗試從不同的角度講，

大家也可以點(diǎn)擊鏈接看看老板過去寫的文章↓↓↓↓

【算法進(jìn)階】用回溯法(backtracking algorithm)求解N皇后問題(N-Queens puzzle)

?

話說多了，那么就開始吧。

目錄

01.回溯法介紹

02.01背包：子集樹

03.旅行收獲商：排序樹

04.總結(jié)

壹

回溯法介紹

回溯法，又叫試探法，是一種尋找最優(yōu)解的暴力搜尋法，也比較容易理解（適合小白學(xué)習(xí)）。但是，由于暴力，回溯法的時(shí)間復(fù)雜度較高，因此在比較一些數(shù)字較大的問題時(shí)，比如上次我們提到的最短路徑問題等，運(yùn)行時(shí)間一般比較長(zhǎng)。

在回溯法中，深度優(yōu)先搜索是一種很重要的工具——說到這是不是想起來(lái)上次的最短路徑問題的DFS解法了？了解了DFS，就比較容易理解回溯法。

?

簡(jiǎn)單地介紹一下DFS，用一句話概括，就是“不撞南墻不回頭”。（這句話也適用于回溯法）

它的基本思想是：

（1）某一種可能情況向前探索，并生成一個(gè)子節(jié)點(diǎn)。

（2）過程中，一旦發(fā)現(xiàn)原來(lái)的選擇不符合要求，就回溯至父親結(jié)點(diǎn)，然后重新選擇另一方向，再次生成子結(jié)點(diǎn)，繼續(xù)向前探索。

（3）如此反復(fù)進(jìn)行，直至求得最優(yōu)解。

?

我們?cè)倩氐交厮莘ā?/span>

?

回溯法基本思想是：

（1）針對(duì)具體問題，定義問題的解空間；

（2）確定易于搜索的解空間結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)的選擇）。

（3）一般以DFS的方式搜索解空間。

（4）在搜索過程中，可以使用剪枝函數(shù)等來(lái)優(yōu)化算法。

?

是不是看到了幾個(gè)生詞？沒關(guān)系，我們?cè)俳忉屢幌隆?/span>

?

解空間：顧名思義，就是一個(gè)問題的所有解的集合。（但別忘了，這離我們要求的最優(yōu)解還差很遠(yuǎn)！）

剪枝函數(shù)：用約束函數(shù)和限界函數(shù)剪去得不到最優(yōu)解的子樹，統(tǒng)稱為剪枝函數(shù)。

?

慢著，又多了幾個(gè)生詞！

別著急，我們繼續(xù)看。

?

約束條件：有效解的要求，即題目的要求。

約束函數(shù)：減去不滿足約束條件的子樹的函數(shù)

限界函數(shù)：去掉得不到最優(yōu)解的結(jié)點(diǎn)的函數(shù)

擴(kuò)展結(jié)點(diǎn)：當(dāng)前正在產(chǎn)生子結(jié)點(diǎn)的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)

?

那么，為什么我們這里要提到樹呢？

?

因?yàn)槲覀冇没厮莘ㄌ幚淼慕饪臻g常常可以分為這兩種（或者說可以采取這兩種方法）：

子集樹：當(dāng)所給問題是從集合中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。

排列樹：當(dāng)所給問題事從集合中確定滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。

?

解釋了這么多名詞，相信大家對(duì)回溯法都有了一點(diǎn)基礎(chǔ)的了解。但很多同學(xué)可能還有一個(gè)很大的問題：

回溯法到底和DFS有什么區(qū)別？

其實(shí)我認(rèn)為吧，真沒什么區(qū)別。真要說的話，DFS是一種遍歷搜索圖、樹等數(shù)據(jù)結(jié)構(gòu)的一種算法，更像一種工具；而回溯法則是為了解決問題不斷地生成又放棄一些解決方案（解空間在搜索問題的過程中動(dòng)態(tài)產(chǎn)生是回溯法的一個(gè)重要特點(diǎn)），直至找到最優(yōu)解或搜索完畢為止的一種方法，更像一種指導(dǎo)思想，在解空間中利用DFS進(jìn)行全面的搜索。

?

我覺得也沒必要太糾結(jié)這兩者的區(qū)別。。。（不是因?yàn)槲腋悴欢。。。?/span>

?

還有就是關(guān)于優(yōu)化的剪枝函數(shù)。

剪枝就是在搜索過程中利用過濾條件來(lái)剪去完全不用考慮（已經(jīng)判斷這條路走下去得不到最優(yōu)解）的搜索路徑，從而避免了一些不必要的搜索，優(yōu)化算法求解速度，當(dāng)然還必須得保證結(jié)果的正確性。

應(yīng)用到回溯算法中，我們可以提前判斷當(dāng)前路徑是否能產(chǎn)生結(jié)果集，如果否，就可以提前回溯。而這也叫做可行性剪枝。

另外還有一種叫做最優(yōu)性剪枝，每次記錄當(dāng)前得到的最優(yōu)值，如果當(dāng)前結(jié)點(diǎn)已經(jīng)無(wú)法產(chǎn)生比當(dāng)前最優(yōu)解更優(yōu)的解時(shí)，可以提前回溯。

然而，剪枝的過濾條件不好找，想通過剪枝優(yōu)化來(lái)提高算法高效性，又要保證結(jié)果正確性，還要保證剪枝的準(zhǔn)確性。是非常難得的。哎，我太難了。。。

?

了解完回溯法的一些概念后，我們來(lái)就著題目講解吧~~

貳

01背包：子集樹

之前我們提到了，用回溯法處理解空間大致可以分為兩種（當(dāng)然也可以不用這兩種），其中一種是子集樹。01背包問題就是由子集樹解決的一個(gè)經(jīng)典問題。

?

我們貼一張圖來(lái)說明：

因?yàn)槲覀兛紤]的是找子集，所以每個(gè)物品只有選與不選兩種狀態(tài)，因此解空間是一個(gè)二叉樹。在這個(gè)樹中，每一層的邊表示對(duì)一個(gè)物品的選擇與否。

舉個(gè)例子，選擇第一層點(diǎn)0與左邊點(diǎn)1間的邊，表示選擇1號(hào)物品，也就是選擇左子樹走下去；如果不選擇1號(hào)物品入包，則進(jìn)入右子樹，選擇右邊點(diǎn)1。那么，一共有n件物品，就有n層的邊，n+1層點(diǎn)。最后一層的每一個(gè)葉結(jié)點(diǎn)分別表示一種選擇法，一共有2^個(gè)葉結(jié)點(diǎn)，即解空間中共有2^n種解，我們要在這些葉結(jié)點(diǎn)中選擇最佳結(jié)點(diǎn)。

?

我們先給出利用回溯法搜索子樹集的偽代碼框架：

void?search(層數(shù))

{

If(搜索到最底層)

打印出結(jié)果解;

Else?? for(遍歷當(dāng)前層解)

{

If(合適解)繼續(xù)搜索;

撤消當(dāng)前狀態(tài)的影響;//回溯

}

}?

來(lái)看看題干：

01背包問題。

某舟同學(xué)打算去拜訪某欣同學(xué)，他打算帶一背包的巧克力作為禮物。他希望裝進(jìn)的巧克力總價(jià)值最高，這樣可能比較好吃。然而小舟體力有限，巧克力包不能太重，只能有8kg。

可供選擇的巧克力如下：

1? ? 費(fèi)列羅? ? ? ? ? ? ? ? ? ? ? 4kg? ? $4500

2? ? 好時(shí)之點(diǎn)? ? ? ? ? ? ? ? ? ?5kg? ? $5700

3? ? 德芙? ? ? ? ? ? ? ? ? ? ? ? ? 2kg? ? $2250

4? ? Cudie（西班牙）? ? ? ?1kg? ? $1100

5? ? 自制? ? ? ? ? ? ? ? ? ? ? ? ? 6kg? ? $6700

（某欣不會(huì)介意巧克力太重太貴的）

玩笑開玩了。。。不知道看懂題目沒？不懂也得懂~

?

回溯法講究“暴力”。我們從暴力的角度思考，想把所有的盡量裝滿背包的搭配都找出來(lái)，標(biāo)記每一種裝法（每一個(gè)解）最大value，從而找到最優(yōu)解。

?

我們從第一種巧克力開始裝，然后找下一個(gè)，判斷能否裝入，再遞歸，到達(dá)邊界，比較，記錄較優(yōu)解，回溯，繼續(xù)往下找。。。循環(huán)。

從子集樹的角度將，我們優(yōu)先選擇走左子樹，也就是入包；當(dāng)走到葉結(jié)點(diǎn)或不符合約束的重量條件時(shí)，回溯到父結(jié)點(diǎn)，進(jìn)入右結(jié)點(diǎn)，最后遍歷全樹。

?

判斷能否裝入后可以用一個(gè)book數(shù)組來(lái)標(biāo)記是否選擇入包。（我第一次自己編時(shí)就忘了！！不斷通過循環(huán)來(lái)調(diào)用尋找下一個(gè)結(jié)點(diǎn)的函數(shù)，實(shí)在是太傻了，明明這個(gè)方法超級(jí)常用！！果然小白。。。）

?

再根據(jù)這個(gè)寫出01背包問題的代碼（注釋中有詳解，請(qǐng)放心食用）：

?

//01背包問題——回溯法子集樹 #include using namespace std;
int n,bag_v,bag_w;int bag[100],x[100],w[100],val[100];
void search(int cur,int cur_v,int cur_w){   //search遞歸函數(shù)，當(dāng)前current節(jié)點(diǎn)的價(jià)值為current value，重量為current weight     if(cur>n)   //判斷邊界       {        if(cur_v>bag_v)             //是否超過了最大價(jià)值        {            bag_v=cur_v;            //得到最大價(jià)值            for(int i=1;i<=n;i++)                      bag[i]=x[i];      //x表示當(dāng)前是否被選中，將選中的物品存入bag中         }    }    else         for(int j=0;j<=1;j++)    //遍歷當(dāng)前解層:是否選擇該物品         {            x[cur]=j;                  if(cur_w+x[cur]*w[cur]<=bag_w)   //滿足重量約束,繼續(xù)向前尋找配對(duì)             {                cur_w+=w[cur]*x[cur];                cur_v+=val[cur]*x[cur];                search(cur+1,cur_v,cur_w);//遞歸，下一件物品                 //清楚痕跡，回溯上一層                 cur_w-=w[cur]*x[cur];                   cur_v-=val[cur]*x[cur];                x[cur]=0;            }        }}
int main(){    int i;    bag_v=0; //初始化背包最大價(jià)值    //輸入數(shù)據(jù)     cout<<"請(qǐng)輸入背包最大容量:"<<endl;;    cin>>bag_w;    cout<<"請(qǐng)輸入物品個(gè)數(shù):"<<endl;    cin>>n;    cout<<"請(qǐng)依次輸入物品的重量:"<<endl;    for(i=1;i<=n;i++)         cin>>w[i];    cout<<"請(qǐng)依次輸入物品的價(jià)值:"<<endl;    for(i=1;i<=n;i++)         cin>>val[i];    search(1,0,0);    cout<<"最大價(jià)值為:"<<endl;    cout<endl;    cout<<"物品的編號(hào)依次為:"<<endl;
    for(i=1;i<=n;i++)        if(bag[i]==1)             cout<" ";    cout<<endl;????    return 0;}

?

我們?cè)賮?lái)略微講解一下如何優(yōu)化。

?

我們可以用一個(gè)上界函數(shù)bound():當(dāng)前價(jià)值+剩余容量可容納的最大價(jià)值，去和目前的背包最大價(jià)值（也就是最優(yōu)解）比較，如果bound（）更小，那就沒有繼續(xù)搜索的意義了，剪去左子樹，即不選擇當(dāng)前物品，進(jìn)入右子樹。

因?yàn)槲锲分挥羞x與不選2個(gè)決策，而總共有n個(gè)物品，所以時(shí)間復(fù)雜度為O（2^n）。

因?yàn)檫f歸棧最多達(dá)到n層，而且存儲(chǔ)所有物品的信息也只需要常數(shù)個(gè)一維數(shù)組，所以最終的空間復(fù)雜度為O(n)。

?

那么，我們?nèi)绾斡?jì)算這個(gè)“剩余容量可容納的最大價(jià)值”呢？

首先，我們先將物品按照其單位重量?jī)r(jià)值從大到小排序，此后就按照順序考慮各個(gè)物品。

接下來(lái)，我們貼代碼講解。（對(duì)不起我也是網(wǎng)上看來(lái)的嗚嗚嗚）

?

    if(cur_w+w[cur]<=bag_w)//將物品cur放入背包,搜索左子樹,即選擇當(dāng)前物品     {        cur_w+=w[cur];//同步更新當(dāng)前背包的重量        cur_v+=val[cur];//同步更新當(dāng)前背包的總價(jià)值        put[cur]=1;        search(cur+1,cur_v,cur_w);//深度搜索進(jìn)入下一層        cur_w-=w[cur];//回溯復(fù)原        cur_v-=val[cur];//回溯復(fù)原    }    if(bound(cur+1,cur_v,cur_w)>bag_v)//如若符合條件則搜索右子樹,即不選擇當(dāng)前物品   {        put[cur]=0;        search(cur+1,cur_v,cur_w);    }

?

當(dāng)i<=n，重量超過限制時(shí)，leftw為負(fù)，我們得到的是一個(gè)達(dá)不到的理想最大價(jià)值，因?yàn)榇藭r(shí)最后放入的物品單位價(jià)值較高，但無(wú)法完全塞進(jìn)書包，我們就去掉多余的部分，只取一部分該物體入包。當(dāng)然，這是做不到的。因此計(jì)算出的值是一個(gè)達(dá)不到的理想值。

當(dāng)i>n，重量未超過限制時(shí)，則是可達(dá)到的最大價(jià)值。

?

這樣就解釋了這個(gè)上界函數(shù)的優(yōu)化。可以看出，這是一個(gè)最優(yōu)性剪枝優(yōu)化，判斷當(dāng)前結(jié)點(diǎn)是否有機(jī)會(huì)產(chǎn)生更優(yōu)解。

總代碼：

//01背包問題優(yōu)化#include using namespace std;
int n,bag_v,bag_w;int bag[100],put[100],w[100],val[100],order[100];double perp[100]; 
//按照單位重量?jī)r(jià)值排序，這里用冒泡 void bubblesort(){    int i,j;    int temporder = 0;    double temp = 0.0;    for(i=1;i<=n;i++)        perp[i]=val[i]/w[i]; //計(jì)算單位價(jià)值（單位重量的物品價(jià)值）    for(i=1;i<=n-1;i++)    {        for(j=i+1;j<=n;j++)            if(perp[i]//冒泡排序perp[],order[],sortv[],sortw[]        {            temp = perp[i];  //冒泡對(duì)perp[]排序交換             perp[i]=perp[i];            perp[j]=temp;            temporder=order[i];//冒泡對(duì)order[]交換             order[i]=order[j];            order[j]=temporder;            temp = val[i];//冒泡對(duì)val[]交換             val[i]=val[j];            val[j]=temp;            temp=w[i];//冒泡對(duì)w[]交換             w[i]=w[j];            w[j]=temp;        }    }}
//計(jì)算上界函數(shù)，功能為剪枝double bound(int i,int cur_v,int cur_w){   //判斷當(dāng)前背包的總價(jià)值cur_v＋剩余容量可容納的最大價(jià)值<=當(dāng)前最優(yōu)價(jià)值    double leftw= bag_w-cur_w;//剩余背包容量    double b = cur_v;//記錄當(dāng)前背包的總價(jià)值cur_v,最后求上界        //以物品單位重量?jī)r(jià)值遞減次序裝入物品    while(i<=n && w[i]<=leftw)    {        leftw-=w[i];        b+=val[i];        i++;    }    //裝滿背包    if(i<=n)        b+=val[i]/w[i]*leftw;    return b;//返回計(jì)算出的上界}
void search(int cur,int cur_v,int cur_w){   //search遞歸函數(shù)，當(dāng)前current節(jié)點(diǎn)的價(jià)值為current value，重量為current weight     if(cur>n)   //判斷邊界       {        if(cur_v>bag_v)             //是否超過了最大價(jià)值        {            bag_v=cur_v;            //得到最大價(jià)值            for(int i=1;i<=n;i++)                      bag[order[i]]=put[i];      //put表示當(dāng)前是否被選中，將選中的物品存入bag中         }    }    //如若左子節(jié)點(diǎn)可行，則直接搜索左子樹;    //對(duì)于右子樹，先計(jì)算上界函數(shù)，以判斷是否將其減去    if(cur_w+w[cur]<=bag_w)//將物品cur放入背包,搜索左子樹,即選擇當(dāng)前物品     {        cur_w+=w[cur];//同步更新當(dāng)前背包的重量        cur_v+=val[cur];//同步更新當(dāng)前背包的總價(jià)值        put[cur]=1;        search(cur+1,cur_v,cur_w);//深度搜索進(jìn)入下一層        cur_w-=w[cur];//回溯復(fù)原        cur_v-=val[cur];//回溯復(fù)原    }    if(bound(cur+1,cur_v,cur_w)>bag_v)//如若符合條件則搜索右子樹,即不選擇當(dāng)前物品   {        put[cur]=0;        search(cur+1,cur_v,cur_w);    }}
int main(){    int i;    bag_v=0; //初始化背包最大價(jià)值    //輸入數(shù)據(jù)     cout<<"請(qǐng)輸入背包最大容量:"<<endl;;    cin>>bag_w;    cout<<"請(qǐng)輸入物品個(gè)數(shù):"<<endl;    cin>>n;    cout<<"請(qǐng)依次輸入物品的重量:"<<endl;    for(i=1;i<=n;i++)         cin>>w[i];    cout<<"請(qǐng)依次輸入物品的價(jià)值:"<<endl;    for(i=1;i<=n;i++)         cin>>val[i];    for (i=1;i<=n;i++)  //新增的order數(shù)組，存儲(chǔ)初始編號(hào)         order[i]=i;    search(1,0,0);    cout<<"最大價(jià)值為:"<<endl;    cout<endl;    cout<<"物品的編號(hào)依次為:"<<endl;
    for(i=1;i<=n;i++)        if(bag[i]==1)             cout<" ";    cout<<endl;    return 0;}

叁

旅行售貨員：排序樹

?

講完子集樹，我們?cè)僦v講排序樹。排列樹與子集樹最大的區(qū)別在于，子集樹的解是無(wú)序的子集，而排列樹的解則包含整個(gè)集合的所有元素，我們從暴力的原則出發(fā)，將元素進(jìn)行全排列。

?

我們?cè)儋N出排序樹的圖。

｛｝外的數(shù)表示已經(jīng)排好序，｛｝內(nèi)的數(shù)尚未排序。

在排序樹中，每一層選擇一個(gè)數(shù)字排到隊(duì)尾，因此對(duì)一個(gè)n元素的集合，樹的第一層將有n個(gè)子結(jié)點(diǎn)，表示可選n個(gè)數(shù)放在隊(duì)伍的第一個(gè)位置，一次分叉比前一次減少一個(gè)（因?yàn)橐呀?jīng)確定了一個(gè)位置的元素）；

樹共有n+1層（圖中省略了最后一層），表示選擇n次；

葉結(jié)點(diǎn)共有n！個(gè)，表示組合數(shù)A，全排列共有n！種情形（因此時(shí)間復(fù)雜度也是n！）。

?

我們?cè)俳o出算法框架（這次換英文了~保持新鮮感）：

void backtrack(int t)

{

??? if(t>n)

??????? output(x)

??? else

??? {

??????????? for(int i=t;i<=n;i++)??????

?{

??????????? swap(x[t],x[i]);

??????????? if(constraint(t)&&bound(t))//

??????????????? backtrack(t+1)

??????????? swap(x[i],x[t]);

??????? }

??? }

}

這里的swap是一個(gè)交換函數(shù)，對(duì)于一個(gè)排列，只要交換任意兩數(shù)后就是一個(gè)新排列。constraint（）和bound（）分別是約束條件和限定函數(shù)（用于剪枝優(yōu)化）。

為什么要用swap來(lái)交換，而不是把數(shù)據(jù)放入新數(shù)組啦等等什么別的操作呢？

這是因?yàn)椋?dāng)我們?cè)谠却鎯?chǔ)數(shù)據(jù)的數(shù)組x內(nèi)進(jìn)行交換時(shí)，我們把排好序的元素放到了數(shù)組的前面，留下的數(shù)據(jù)則是未排序的。這樣在我們進(jìn)行for循環(huán)的時(shí)候就能從t開始，同時(shí)避免了重復(fù)遇到排過序的數(shù)，也不需要book記錄等多余的代碼。

?

差不多了解了排序樹的概念和回溯法在排序樹中的框架，我們就來(lái)看題目啦。

?

旅行售貨員問題（TSP）：

某舟同學(xué)在去小欣同學(xué)那前想了一想，準(zhǔn)備順便拜訪各高校的高中同學(xué)。他打算從本校出發(fā)，途徑高中同學(xué)所在的一些高校，最終回到自己學(xué)校。小舟很懶，希望只走最短的路，同時(shí)不想在一個(gè)學(xué)校玩第二次，因?yàn)樗麄儾皇侵饕繕?biāo)。怎么滿足貪得無(wú)厭的小舟，制定一個(gè)旅行方案？

繼續(xù)開玩笑。。。別介意~~

?

回到正題，乍一看這個(gè)題目是不是和最短路徑問題很像？但很可惜的是，最短路徑不要求通過每一個(gè)點(diǎn)，還是有所不同。

關(guān)鍵詞：最短，每點(diǎn)一次，閉合回路。

（但學(xué)過的知識(shí)還是有用的：比方說我們可以用上次學(xué)過的鄰接矩陣來(lái)存儲(chǔ)圖的內(nèi)容。）

?

在這個(gè)問題中，我們的解空間就是所有城市的全排列，即走過每一個(gè)城市的順序，因此可以用排序樹來(lái)考慮這個(gè)問題。

?

放碼：

//旅行售貨員問題——回溯法排序樹 #include using namespace std; int n,t; int dis[100][100],x[100],bestroad[100];  int cur_dis,bestdis; const int INF=99999; void swap(int&a,int&b)  //swap函數(shù)，交換 {   int temp;   temp=a;   a=b;   b=temp; } void backtrack(int t)   {   if (t==n)     { //判斷邊界。很長(zhǎng)的判斷 ，不能到自己或到不了，要比當(dāng)前最優(yōu)解短        if (dis[x[n - 1]][x[n]] != 0 && dis[x[n]][1] != 0 &&(cur_dis + dis[x[n - 1]][x[n]] + dis[x[n]][1] < bestdis || bestdis == 0))            {  //記錄最優(yōu)路徑，最優(yōu)距離              for (int j=1;j<=n;j++)                    bestroad[j]=x[j];             bestdis=cur_dis+ dis[x[n - 1]][x[n]] + dis[x[n]][1];             return;         }     }  else     {    for (int j=t;j<=n;j++)       {         if(dis[x[t]][x[j]]!=0&& (cur_dis + dis[x[t - 1]][x[t]] + dis[x[t]][1] < bestdis || bestdis == 0))             {               swap(x[t],x[j]);               cur_dis+=dis[x[t]][x[t-1]];               backtrack(t+1);               //回溯                cur_dis-=dis[x[t]][x[t-1]];               swap(x[t],x[j]);           }       }     } } int main(){    int i,j,m,a,b,c;    cout<<"輸入城市數(shù):"<<endl;    cin>>n;     cout<<"輸入路徑數(shù):"<<endl;     cin>>m;    //初始化鄰接矩陣    for(i=1;i<=n;i++)        for(j=1;j<=n;j++)            dis[i][j]=0;      cout<<"輸入路徑與距離:"<<endl;      //讀入城市之間的距離    for(i=1;i<=m;i++)    {     cin>>a>>b>>c;      dis[a][b]=dis[b][a]=c; //無(wú)向圖，兩邊都記錄     }    for(i = 1; i <= n; i++)       x[i] = i;    backtrack(2);        cout<<"最佳路徑為:";    for (i=1;i<=n;i++)            cout<" --> ";    cout<<"1"<<endl;    cout<<"最短距離為:"<    return 0; }

?

代碼中有一些細(xì)節(jié)：

不同于最短路徑，這里我們把INF（即無(wú)路徑連通）與0（即自身）放在一起處理，因?yàn)樗麄兌疾恍枰猻wap。

我們用t==n，而不是t>=n，是為了防止數(shù)組下表越界。

?

然而，當(dāng)我們想用剪枝函數(shù)優(yōu)化時(shí)，發(fā)現(xiàn)其實(shí)沒什么好方法。。。

再一次說明了通過剪枝函數(shù)優(yōu)化是不容易的。（當(dāng)然，對(duì)TSP問題還有許多方法，針對(duì)這個(gè)問題老板也寫過很多文章哦，可以在公眾號(hào)內(nèi)查詢，老板賽高）

肆

簡(jiǎn)單總結(jié)

在總結(jié)之前，我們?cè)偬崽崂习?年前（好強(qiáng)！）寫的N皇后問題。

在那個(gè)問題中，老板沒有用子集樹或排序樹。因?yàn)楸揪?strong>不止這些方法。

但N皇后問題確實(shí)可以用這兩種數(shù)據(jù)結(jié)構(gòu)來(lái)寫。這里就不再寫了，再寫我就要死了。有興趣的盆友可以自行搜索。

?

那么，終于到了激動(dòng)人心的總結(jié)時(shí)間。（也就是完稿時(shí)間）

回溯法作為一種極暴力的搜索法，其時(shí)間復(fù)雜度是極高的，子集樹大概是2^n，排序樹大概是n！，所以處理大的問題不太給力。

但作為回報(bào)，它能給出真正的最優(yōu)解。

回溯法的子集樹和排序樹，可以處理兩類問題，求子集最優(yōu)和排序最優(yōu)。

想要利用剪枝函數(shù)優(yōu)化是非常困難的。（親身經(jīng)歷）

?

那么，本次總結(jié)就這樣水一水啦~~飄走~~

寫下最后這個(gè)TSP真是感慨萬(wàn)分啊！

在20多天前，我問老板：怎么學(xué)算法？我新手，不懂啊。你文章里題目太難了。

老板說：TSP很難嗎，小老弟？

當(dāng)時(shí)心態(tài)是絕望的(┬＿┬)

如今最起碼能用暴力法寫寫了，不容易，不容易

特此紀(jì)念~~~（公號(hào)私用，砍了）

這里是新來(lái)的工人小舟，

正走在努力學(xué)習(xí)編程的路上。

讓我們下次再見~

#

-The End-

文/怎么學(xué)都學(xué)不會(huì)C++的新手舟

版/怎么趕都趕不完作業(yè)的小白舟

碼/新來(lái)到程序猿聲的工人舟

審/這片工地的包工頭短短的路走走停停

#