廈門理工算法設計與分析(第五章)

第五章

回溯法2/7/20231計算機算法設計與分析計算機求解的過程求解過程可看成在狀態(tài)空間從初始狀態(tài)出發(fā)搜索目標狀態(tài)(解所在狀態(tài))的過程。狀態(tài)空間初始狀態(tài)目標狀態(tài)搜索可描述為：S0S1…Sn，S0為初態(tài)，Sn為終態(tài)?；蛘擀?S0)且φ(Sn)，這里ψ稱為初始條件，φ稱為終止條件。2/7/20232計算機算法設計與分析求解是狀態(tài)空間的搜索求解的過程可以描述為對狀態(tài)空間的搜索其中S0為初始狀態(tài)，不妨設Sni為終止狀態(tài)S0S11S12…S1k………………Sn1……Sni……SnmS0于是問題的求解就是通過搜索尋找出一條從初始狀態(tài)S0到終止狀態(tài)Sni的路徑。Sni2/7/20233計算機算法設計與分析幾種搜索方法狀態(tài)空間的搜索實際上是一種樹/DAG的搜索，常用的方法有：廣度優(yōu)先的搜索：深度優(yōu)先的搜索：啟發(fā)式的搜索：從初始狀態(tài)開始，逐層地進行搜索。從初始狀態(tài)開始，逐個分枝地進行搜索。從初始狀態(tài)開始，每次選擇最有可能達到終止狀態(tài)的結(jié)點進行搜索。2/7/20234計算機算法設計與分析三種搜索的比較理論上廣度優(yōu)先搜索與深度優(yōu)先搜索的時間復雜性都是指數(shù)級。但在實際上深度優(yōu)先搜索的時間復雜性要低，在空間復雜性更要低得多。廣度優(yōu)先搜索是一定能找到解；而深度優(yōu)先搜索在理論上存在找不到解的可能。啟發(fā)式搜索是最好優(yōu)先的搜索，若評價函數(shù)設計得好則能較快地找到解，降低時間復雜性；因而評價函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。另外評價函數(shù)本身的開銷也是很重要的。2/7/20235計算機算法設計與分析樹搜索的一般形式SearchTree(SpaceT){ok=0;L=T.initial;while(!ok||L≠){a=L.first;if(aisgoal)ok=1elseControl-put-in(L,Sons(a));}ok表示搜索結(jié)束。將初始狀態(tài)放入L。從L中取出第一個元素。若a是終態(tài)則結(jié)束。否則，將a的兒子們以某種控制方式放入L中。表L用來存放待考察的結(jié)點。2/7/20236計算機算法設計與分析三種搜索的不同之處樹的三種搜索方法的不同就在于它們對表L使用了不同控制方式：L是一個隊列L是一個棧L的元素按照某方式排序廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索其中，深度優(yōu)先搜索就是回溯法。2/7/20237計算機算法設計與分析遞歸回溯法的一般形式Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}Try(s+1)意味著按照這條分支繼續(xù)嘗試。Try(s+1)返回后，若不成功，則意味著這條分支失敗了。這時必須刪除原來記錄。2/7/20238計算機算法設計與分析迭代回溯法的一般形式先讓我們回顧解空間搜索的一般形式：SearchTree(SpaceT)//{Ok=0;L=T.initial;while(!Ok||L≠Φ){a=L.first;//從L中取出第一個元素

if(aisgoal)Ok=1elseControl-put-in(L,Sons(a));}Ok表示是否找到解。表L存放待考察結(jié)點。對L的控制方式不同，則搜索方法也不同。在回溯法中，控制方式是棧。初始將根節(jié)點放入L中。2/7/20239計算機算法設計與分析迭代回溯法的一般形式先讓我們回顧解空間搜索的一般形式：SearchTree(SpaceT)//{Ok=0;L=T.initial;while(!Ok||L≠){a=L.first;if(aisgoal)Ok=1elseControl-put-in(L,Sons(a));}從L中取出第一個元素。在棧操作中就是彈出棧頂元素。在通常求解問題時，解是由逐個狀態(tài)構(gòu)成的。因此，這里還需要判斷狀態(tài)是否可接受，并進行紀錄路徑等工作。2/7/202310計算機算法設計與分析迭代回溯法的一般形式先讓我們回顧解空間搜索的一般形式：SearchTree(SpaceT)//{Ok=0;L=T.initial;while(!Ok||L≠){a=L.first;if(aisgoal)Ok=1elseControl-put-in(L,Sons(a));}若a可接收但未終止，則要將a的后繼壓入棧中。若要拋棄狀態(tài)a，當a是最后的兒子時，還需要消除原有的紀錄甚至回溯一步。2/7/202311計算機算法設計與分析如何判斷最后一個兒子？若只要遍歷解空間樹的結(jié)點，那么將各結(jié)點按棧方式控制便可實現(xiàn)深度為主搜索。在求解問題時，需要記錄解的路徑，在回溯時還需要刪除結(jié)點和修改相應信息。棧中結(jié)點應該分層次，而卻沒有區(qū)分其層次。這就增加了回溯判斷和操作的困難。怎么辦呢？2/7/202312計算機算法設計與分析如何判斷最后一個兒子？若只要遍歷解空間樹的結(jié)點，那么將各結(jié)點按棧方式控制便可實現(xiàn)深度為主搜索。在求解問題時，需要記錄解的路徑，在回溯時還需要刪除結(jié)點和修改相應信息。棧中結(jié)點應該分層次，而卻沒有區(qū)分其層次。這就增加了回溯判斷和操作的困難。采用一個簡潔有效的方法：設計一個末尾標記，每次壓棧時，先壓入末尾標記。2/7/202313計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若棧頂元素是末尾標記，說明這個路徑已經(jīng)到頭了，需要回溯一步?！痢聊┪?/7/202314計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a是可以接受的，則將a加入求解的路徑中。2/7/202315計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a是目標節(jié)點，則結(jié)束搜索并輸出求解的路徑。2/7/202316計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a不是目標節(jié)點且a有后繼，則將a的后繼壓入棧中。2/7/202317計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若a不是目標節(jié)點又沒有后繼，則將a從解的路徑中刪除。2/7/202318計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}注意：這里的L.Push-Sons(a)要先壓入末尾標記，然后再壓入后繼結(jié)點。2/7/202319計算機算法設計與分析用末尾標記的迭代回溯Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}a既不是目標又沒有后繼，則將a刪除。請注意Move-off與Backstep的區(qū)別。×2/7/202320計算機算法設計與分析Backastep與Move-offBackstep的動作：××末尾Move-off的動作：×非末尾Move-off需要做的只是刪除自身的記錄而轉(zhuǎn)向兄弟結(jié)點。而Backstep除此之外，還需要刪除父節(jié)點的記錄而轉(zhuǎn)向叔叔結(jié)點。2/7/202321計算機算法設計與分析迭代回溯法的一般形式Backtrack(TreeT){Ok=0;L.Push(T.root);while(!Ok||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){Ok=1;Output()}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}2/7/202322計算機算法設計與分析不可接受的結(jié)點破壞了解的相容條件的結(jié)點超出了狀態(tài)空間的范圍，或者說不滿足約束條件，的結(jié)點；評價值很差的結(jié)點，即已經(jīng)知道不可能獲得解的結(jié)點；已經(jīng)存在于被考察的路徑之中的結(jié)點，這種結(jié)點會造成搜索的死循環(huán)。2/7/202323計算機算法設計與分析N后問題要求在一個n×n的棋盤上放置n個皇后，使得她們彼此不受攻擊。按照國際象棋的規(guī)則，一個皇后可以攻擊與之同一行或同一列或同一斜線上的任何棋子。因此，N后問題等價于：要求在一個n×n的棋盤上放置n個皇后，使得任意兩個皇后不得在同一行或同一列或同一斜線上。2/7/202324計算機算法設計與分析用遞歸回溯法求N后問題Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}讓我們先回顧遞歸回溯法的一般形式：

2/7/202325計算機算法設計與分析用遞歸回溯法求N后問題Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}s為準備放置后的行數(shù)。候選者為0到n–1列。2/7/202326計算機算法設計與分析用遞歸回溯法求N后問題Try(s){

while

if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}j=–1;q=0;令列標志j為–1

，q表示未成功。(未成功且還有候選者){(!q&&j<n){列數(shù)不到n就還有候選者。挑選下一個候選者next；列數(shù)加一即為next。j++;2/7/202327計算機算法設計與分析用遞歸回溯法求N后問題Try(s){

while

if記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}j=–1;q=0;(!q&&j<n){j++;(next可接受){放置后各后都安全，便可接受。用函數(shù)Safe(s,j)進行位置(s,j)是否安全的判斷。(Safe(s,j)){2/7/202328計算機算法設計與分析用遞歸回溯法求N后問題Try(s){

while

if

if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}j=–1;q=0;(!q&&j<n){j++;記下該行后的位置(列數(shù))。用函數(shù)Record(s,j)記下位置(s,j)。(Safe(s,j)){記錄next；Record(s,j);2/7/202329計算機算法設計與分析用遞歸回溯法求N后問題Try(s){

while

if

ifelseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}j=–1;q=0;(!q&&j<n){j++;n行后都放完就成功了。

q賦值為1，表示已經(jīng)完成，退出循環(huán)。(Safe(s,j)){Record(s,j);(滿足成功條件){成功并輸出結(jié)果}(s=

=n–1){q=1;Output();}2/7/202330計算機算法設計與分析用遞歸回溯法求N后問題Try(s){

while

if

ifelseTry(s+1);ifreturnj=–1;q=0;(!q&&j<n){j++;(Safe(s,j)){Record(s,j);(s=

=n–1){q=1;Output();}未完成，放s+1行。(不成功)刪去next的記錄;}}不成功，刪去后在該行的位置。(!q)Move-off(s,j);}}}成功與否}q}2/7/202331計算機算法設計與分析用遞歸回溯法求N后問題Try(s){

while

if

ifelseTry(s+1);ifreturnj=–1;q=0;(!q&&j<n){j++;(Safe(s,j)){Record(s,j);(s==n–1){q=1;Output();}q}(!q)Move-off(s,j);}}}現(xiàn)在便得到了求N后的回溯程序。2/7/202332計算機算法設計與分析求解N后問題中的數(shù)據(jù)表示數(shù)組B[n]表示棋盤。若B[i]=j，0≤i,j＜n，表示棋盤的第i行第j列上有皇后。數(shù)組C[j]=1表示第j列上無皇后，0≤j＜n。數(shù)組D[k]=1表示第k條下行對角線(↘)上無皇后。這里k=i+j，0≤k≤2(n–1)。0123450123452/7/202333計算機算法設計與分析求解N后問題中的數(shù)據(jù)表示數(shù)組B[n]表示棋盤。若B[i]=j，0≤i,j＜n，表示棋盤的第i行第j列上有皇后。數(shù)組C[j]=1表示第j列上無皇后，0≤j＜n。數(shù)組D[k]=1表示第k條下行對角線(↘)上無皇后。這里k=i+j，0≤k≤2(n–1)。數(shù)組U[k]=1表示第k條上行對角線(↗)上無皇后。這里k=i–j，–n+1≤k≤n–1。0123450123452/7/202334計算機算法設計與分析求解N后問題中的子程序Record(s,j){k=s–j+n–1;B[s]=j;C[j]=0;D[s+j]=0;U[k]=0;}Move-off(s,j){k=s–j+n–1;B[s]=-1;C[j]=1;D[s+j]=1;U[k]=1;}Safe(s,j){k=s–j+n–1;if(C[j]==1&&U[k]==1&&D[s+j]==1)returntrueelsereturnfalse;}此處k是上行對角線的下標，為什么要進行這樣一個計算呢？2/7/202335計算機算法設計與分析求解N后問題的主程序N-Queens(){intB[n],C[n],D[2n–1],U[2n–1];for(j=0,j<n;j++){B[j]=-1;C[j]=1;U[2j]=1;U[2j+1]=1;D[2j]=1;D[2j+1]=1;}try(0);Output(B);}將數(shù)組B[],C[],U[]和D[]都賦予初值。從第一行開始遞歸2/7/202336計算機算法設計與分析N后問題的迭代程序先看看迭代回溯法的一般形式：2/7/202337計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||L≠){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}L.Push(T.root);(aisthelastmark)Backastep();迭代從第一行(行號為0）開始，將第一行的0～n–1列和n壓入棧中，這里n作為末尾標記。2/7/202338計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||L≠){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}L.Push(T.root);(aisthelastmark)Backastep();i=0;L.Push(n,

0,1,2,…);棧指針p<0，即棧為空。a是末尾標記則回溯。p>=0)2/7/202339計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}(aisthelastmark)Backastep();i=0;L.Push(n,0,1,2,…);(a=

=n)Backastep;回溯需要退回一行，即i–

–;同時刪除該行的原紀錄。2/7/202340計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseif(aisgood){Record(a);if(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a=

=0)Backastep;(a==n){i–

–;a=B[i];Move-off(i,a);}若置放后的位置是安全的，則是好的位置?，F(xiàn)設有謂詞safe(i,a)表示第i行第a列是安全的位置。2/7/202341計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n)

{i–

–;a=B[i];Move-off(i,a);}(Safe(i,a))

{Record(i,a);如果safe(i,a)，則放下后，即Record(a)。2/7/202342計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n){i–

–;a=B[i];Move-off(i,a);}(Safe(i,a)){Record(i,a);如果到了第n行，則成功。(i=

=n–1)2/7/202343計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n){i–

–;a=B[i];Move-off(i,a);}(Safe(i,a)){Record(i,a);(i=

=n–1){i++;L.Push(n,

0,1,2,…);}}}}

只要沒到第n行，則總是有后繼的。2/7/202344計算機算法設計與分析N后問題的迭代程序Backtrack(TreeT){Ok=0;while(!Ok||p>=0){a=L.Pop();ifelseifif(aisgoal){Ok=1;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}i=0;L.Push(n,0,1,2,…);(a==n){i–

–;a=B[i];Move-off(i,a);}(Safe(i,a)){Record(i,a);{i++;L.Push(n,0,1,2,…);}}}}

于是就得到了N后問題的迭代程序。注：這里的幾個子程序與遞歸程序中的完全相同。(i=

=n–1)請同學們自己考慮棧的操作。2/7/202345計算機算法設計與分析迭代回溯解N后問題的主程序N-Queens(n){intB[n],C[n],D[2n–1],U[2n–1];T[n2];for(j=0,j<n;j++){B[j]=-1;C[j]=1;U[2j]=1;U[2j+1]=1;D[2j]=1;D[2j+1]=1;}intp=–1;//棧初始化為空//Backtrack(n,B);}T[]為棧，最多能有n2個候選者。2/7/202346計算機算法設計與分析N后問題的時間復雜性如果只要找出N后問題的一個解，那么這是一個求路徑的問題。求路徑：只需要找到一條路徑便可以得到解。設每個狀態(tài)有k個后繼，其搜索樹為K叉樹，其結(jié)點總數(shù)為kn+1–1，遍歷的時間為O(kn)，這里n為找到解的路徑長度。N后問題的路徑深度為n，可選擇的后繼有n個，所以時間復雜性為O(nn)。2/7/202347計算機算法設計與分析旅行售貨員問題TSP：某售貨員到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條路線，經(jīng)過每個城市一遍最后回到駐地的路線，使得總的路程(或總旅費)最小。設G=(V,E)是一個帶權(quán)圖。圖中各邊的費用(權(quán)值)為正。圖中一條周游路線是包括V中所有頂點的回路。一條周游路線的費用是該路線上所有邊的費用之和。所謂旅行售貨員問題就是要在圖G中找出一條最小費用的周游路線。2/7/202348計算機算法設計與分析考慮TSP的遞歸回溯算法Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}線路上第s個結(jié)點只需依次考察n–1個結(jié)點，即for(i=2;i<=n;i++)下一個候選就是i。2/7/202349計算機算法設計與分析考慮TSP的遞歸回溯算法Try(s){

if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}for(i=2;i<=n;i++){結(jié)點i尚未在路線中且總耗費值不大。就是將結(jié)點i放入路線中并修改耗費值2/7/202350計算機算法設計與分析考慮TSP的遞歸回溯算法Try(s){

if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}for(i=2;i<=n;i++){if(Accept(i)){Record(s,i)；s==n-1若新線路更好，就用新線路取代老線路。2/7/202351計算機算法設計與分析考慮TSP的遞歸回溯算法Try(s){

elseTry(s+1);

if(不成功)刪去next的記錄;}}return成功與否}for(i=2;i<=n;i++){if(Accept(i)){Record(s,i)；if(s==n-1){if(better)TakeNewPath();無所謂成功與否，因為每條周游路線都要進行比較。2/7/202352計算機算法設計與分析考慮TSP的遞歸回溯算法Try(s){

elseTry(s+1);Move-off(s,i)}return}

for(i=2;i<=n;i++){if(Accept(i)){Record(s,i)；if(s==n-1){if(better)TakeNewPath();2/7/202353計算機算法設計與分析TSP的遞歸回溯算法Try(s){for(i=2;i<=n;i++)if(Accept(i)){Record(s,i)；if(s==n-1)if(better)TakeNewPath();elseTry(s+1);Move-off(s,i)}return}現(xiàn)在便得到了TSP問題的遞歸回溯算法的程序。2/7/202354計算機算法設計與分析求解TSP的數(shù)據(jù)結(jié)構(gòu)數(shù)組C[n][n]存放個城市間的費用值。數(shù)組P[n]記錄已經(jīng)找到的費用最小的周游路線，C為其相應的費用，C初值為∞。數(shù)組N[n]記錄目前正在尋找的周游路線，NC為其相應的費用；若NC+C[N[n]][1]小于C，則路線N更佳，于是P[]=N[]，C=NC+C[N[n]][1]。若結(jié)點next不是N中已有結(jié)點，且C大于NC+C[N[i]][next]，則結(jié)點next可接受。2/7/202355計算機算法設計與分析TSP的遞歸程序TryTry(s){for(i=2;i<=n;i++)if(Accept(i)){Record(s,i)；if(s==n-1)if(better)TakeNewPath();elseTry(s+1);Move-off(s,i)}return}2/7/202356計算機算法設計與分析TSP的遞歸程序TryTry(s){for(i=2;i<=n;i++)ifRecord(s,i)；if(s==n-1)if(better)TakeNewPath();elseTry(s+1);Move-off(s,i)}return}(C–NC>C[N[s]][i]

&&T[i]){數(shù)組T[]表示結(jié)點i尚未被選2/7/202357計算機算法設計與分析TSP的遞歸程序TryTry(s){for(i=2;i<=n;i++)ifRecord(s,i)；if(s==n-1)ifelseTry(s+1);Move-off(s,i)}return}(C>NC+C[N[n]][1])TakeNewPath();(C–NC>C[N[s]][i]

&&T[i]){耗散值更小，則更好。2/7/202358計算機算法設計與分析Try中的子程序Record(s,i);{NC=NC+C[N[s]][i];T[i]=0;N[s+1]=i;}Move-off(s,i);{NC=NC–C[N[s]][i];T[i]=1;N[s+1]=0;}TakeNewPath(){for(i=1;i<=n;i++)P[i]=N[i];C=NC+C[N[n]][1];}2/7/202359計算機算法設計與分析遞歸回溯求TSP的主程序TSP(n,C[n][n]){for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1}NC=0；C=∞;N[1]=1;T[1]=0;Try(1);Output(P)；}2/7/202360計算機算法設計與分析考慮TSP的迭代程序為了便于迭代程序中回溯的判斷，我們將城市結(jié)點編號為1~n，用編號0作為末尾的標記。先回顧一下采用末尾標記的迭代回溯法：2/7/202361計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){unfinish=true;L.Push(T.root);while(unfinish||L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal){unfinish=false;Output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}要比較所有路徑，無需此句。2/7/202362計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){L.Push(T.root);while(L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}初始化后壓入第一個結(jié)點。2/7/202363計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);

while(L≠){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}j為棧指針。2/7/202364計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(L.size()>0){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}若棧不空。2/7/202365計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(aisthelastmark)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}末尾標記為0。2/7/202366計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0)Backastep();elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}末尾標記為0。2/7/202367計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}回溯：刪除第j個結(jié)點，然后j––。2/7/202368計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(aisgood){Record(a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}a不在路線中且新增后的費用仍低。2/7/202369計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(T[a]&&C–NC>C[N[j]][a]){Record(j,a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}已經(jīng)n個結(jié)點且新路線的費用更低。這個判斷不再需要了。2/7/202370計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(T[a]&&C–NC>C[N[i]][a]){Record(j,a);if(aisgoal)Output();elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}已經(jīng)n個結(jié)點且新路線的費用更低。2/7/202371計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){

j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(j–1,N[j]);j––;}elseif(T[a]&&C–NC>C[N[i]][a]){Record(N[j],a);if(j==n

-1){if(C>NC+C[a][1])

{TakeNewPath();}Move-off(j,a);}

else

{j++;L.Push-Sons(a)}}}

2/7/202372計算機算法設計與分析考慮TSP的迭代程序Backtrack(TreeT){j=1;N[j]=1;L.Push-Sons(1);while(j>0){a=L.Pop();if(a==0){Move-off(N[j–1],N[j]);j––;}elseif(T[a]&&C–NC>C[N[i]][a]){Record(N[j],a);if(s==n){if(C>NC+C[a][1])

{TakeNewPath();Move-off(N[j],a);}}else{j++;L.Push-Sons(a)}}}

這就是TSP的迭代程序。2/7/202373計算機算法設計與分析迭代回溯求TSP的主程序TSP(n,C[n][n]){for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1}NC=0；C=∞;N[1]=1;T[1]=0;Backtrack(n,C);Output(P)；}2/7/202374計算機算法設計與分析求解TSP的時間復雜性顯然TSP是一個求排列的問題。求排列：確定n個元素的滿足某種性質(zhì)的排列。其搜索樹稱為排列樹，通常有n!個葉結(jié)點，因此遍歷排列樹需要時間為O(n!)。所以TSP問題的時間復雜性為O(n!)2/7/202375計算機算法設計與分析用回溯法解0-1背包問題類似于TSP，用一個數(shù)組P[n]存放目前取得的最優(yōu)解，用變量V表示其價值；再用一個數(shù)組N[n]來產(chǎn)生新的解，用變量NV表示其價值，用變量W表示當前重量。如果新解更優(yōu)，則替代原來的最優(yōu)解，否則就丟棄新解。然后回溯尋找下一個新解。為此，我們先回顧一下回溯法的一般遞歸算法：2/7/202376計算機算法設計與分析用回溯法解0-1背包問題Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}考察的第s個物品2/7/202377計算機算法設計與分析用回溯法解0-1背包問題Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}只考慮兩種情況，選或不選，即for(i=0;i<2;i++)下個候選是i。2/7/202378計算機算法設計與分析用回溯法解0-1背包問題Try(s){

for(i=0;i<2;i++){

if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}令Accept(s)判斷s可接受令Record(s)記錄s2/7/202379計算機算法設計與分析用回溯法解0-1背包問題Try(s){

for(i=0;i<2;i++){if(Accept(s){Record(s,i)if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}物體s可放入背包中將物體s放入背包中2/7/202380計算機算法設計與分析用回溯法解0-1背包問題Try(s){

for(i=0;i<2;i++){if(Accept(s){Record(s,i)

if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}增加物體s未超過背包容量。if(W+w[s]*i<=C){2/7/202381計算機算法設計與分析用回溯法解0-1背包問題Try(s){

for(i=0;i<2;i++){

if(W+w[s]*i<=C){Record(s,i)

if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}將物體s放入背包中即將s放入背包中并修改權(quán)重與容量。N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}2/7/202382計算機算法設計與分析用回溯法解0-1背包問題Try(s){

for(i=0;i<2;i++){

if(W+w[s]*i<=C){

N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}

if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}將物體s放入背包中即將s放入背包中并修改權(quán)重與容量。2/7/202383計算機算法設計與分析用回溯法解0-1背包問題Try(s){

for(i=0;i<2;i++){

if(W+w[s]*i<=C){

N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}

if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}s==n2/7/202384計算機算法設計與分析用回溯法解0-1背包問題Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}for(i=0;i<2;i++){(Accept(s){Record(s,i)(s==n)s=

=n{if(better)TakeNewChoice();}2/7/202385計算機算法設計與分析用回溯法解0-1背包問題Try(s){做挑選候選者的準備；while(未成功且還有候選者){挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}for(i=0;i<2;i++){(Accept(s){Record(s,i)(s==n){if(better)TakeNewChoice();}這里無論成功與否都要繼續(xù)考察Move-off(s,i);}return}“記錄”的逆操作2/7/202386計算機算法設計與分析用回溯法解0-1背包問題Try(s){for(i=0;i<2;i++)if(Accept(i)){Record(s,i)；