(算法分析設計）第5章回溯法

1、( (算法分析設計第算法分析設計第5 5章回溯法章回溯法7回溯法的根本思想 根本思想根本思想 在確定解空間的組織結構后，回溯法從開始結點在確定解空間的組織結構后，回溯法從開始結點根結點出發(fā)，以深度優(yōu)先方式搜索整個解空根結點出發(fā)，以深度優(yōu)先方式搜索整個解空間。這個開始結點成為活結點，同時也成為當前間。這個開始結點成為活結點，同時也成為當前的擴展結點。的擴展結點。 在當前擴展結點處，搜索向縱深方向移至一個新在當前擴展結點處，搜索向縱深方向移至一個新結點。這個新結點成為新的活結點，并成為擴展結點。這個新結點成為新的活結點，并成為擴展結點。結點。 如果在當前擴展結點處不能再向縱深方向移動，如果在當前擴

2、展結點處不能再向縱深方向移動，那么當前擴展結點就成為死結點。此時，應往回那么當前擴展結點就成為死結點。此時，應往回移動回溯到最近的活結點處，并使該結點成移動回溯到最近的活結點處，并使該結點成為當前的擴展結點。為當前的擴展結點。 回溯法按上述方式遞歸地在解空間中搜索，直到回溯法按上述方式遞歸地在解空間中搜索，直到找到所要求的解或解空間中無活結點為止。找到所要求的解或解空間中無活結點為止。8實例分析 n=3的的0-1背包問題背包問題 w=16,15,15 p=45,25,25 c=309解空間為：解空間為：(0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (

3、1,0,1), (1,1,0), (1,1,1)ABCDEFGHIJKLMNO10111111000000n=3的的0-1背包問題的解空間樹背包問題的解空間樹活結點&當前擴展結點BBB活結點死結點10ABCDEFGHIJKLMNO10111111000000當前唯一的活結點，也是當前的擴展結點假定沿縱深方向假定沿縱深方向進行搜索時，選進行搜索時，選擇先移至結點擇先移至結點B11ABCDEFGHIJKLMNO10111111000000結點A、B都是活結點，B是當前擴展結點說明：由于選中了w1，所以結點B處剩余背包容量為30-16=14，獲取的價值為45下一步向D移動，還是向E移動？12ABCD

4、EFGHIJKLMNO10111111000000分析：分析：由于移動到由于移動到D，說明需要將物品，說明需要將物品2放入背包，物放入背包，物品品2的體積為的體積為15，而背包目前的剩余容量為，而背包目前的剩余容量為1414移向結點移向結點K可行不增加容量可行不增加容量15ABCDEFGHIJKLMNO10111111000000分析：分析：由于從K結點無法再向縱深方向移動，因此，K結點成為死結點，回溯到上一個活結點E。（1，0，0）為一可行解）為一可行解16ABCDEFGHIJKLMNO10111111000000分析：分析：由于從E結點無法再向縱深方向移動，因此，E結點成為死結點，回溯到上

5、一個活結點B。17ABCDEFGHIJKLMNO10111111000000分析：分析：由于從B結點無法再向縱深方向移動，因此，B結點成為死結點，回溯到上一個活結點A。18ABCDEFGHIJKLMNO10111111000000向縱深移動到C19ABCDEFGHIJKLMNO10111111000000此時A、C為活結點C為當前擴展結點分析：分析：此時，背包的剩余容量為r=30，獲取的價值為0假定沿縱深方向進假定沿縱深方向進行搜索時，選擇先行搜索時，選擇先移至結點移至結點F20ABCDEFGHIJKLMNO10111111000000此時A、C、F為活結點F為當前擴展結點分析：分析：此時，背

6、包的剩余容量為r=30-15=15，獲取的價值為25移動方向：移動方向：L or M ？分析：分析：移向結點移向結點L、M都可行都在容量允許范圍內(nèi)都可行都在容量允許范圍內(nèi)21ABCDEFGHIJKLMNO10111111000000(0,1,1)為一可行解為一可行解22ABCDEFGHIJKLMNO10111111000000按上述規(guī)那么進行解空間搜索，直到所有的結點都成為死結點此時共獲得5個可行解：(1,0,0)，(0,1,1)，(0,1,0)，(0,0,1)，(0,0,0)其中(0,1,1)為最優(yōu)解23如何防止回溯法的無效搜索 防止無效搜索防止無效搜索 用約束函數(shù)在擴展結點處剪去不滿足約束

7、用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；的子樹； 見見0-1背包問題背包問題 用限界函數(shù)剪去得不到最優(yōu)解的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹； 見見TSP問題問題 以上兩類函數(shù)統(tǒng)稱為剪枝函數(shù)以上兩類函數(shù)統(tǒng)稱為剪枝函數(shù)24回溯法的主要步驟 主要步驟主要步驟 針對所給問題，定義問題的解空間；針對所給問題，定義問題的解空間； 確定易于搜索的解空間結構；確定易于搜索的解空間結構； 以深度優(yōu)先方式搜索解空間，并在搜索過以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)防止無效搜索。程中用剪枝函數(shù)防止無效搜索。25知識點 問題的解空間 回溯法的根本思想 遞歸回溯 迭代回溯 子集樹與排列樹26遞歸回

8、溯void backtrackbacktrack( int t) if(tn) output(x); elsefor(int i=f(n,t);i0) if(f(n,t)=g(n,t) for(int i=f(n,t);in) output(x); elsefor(int i=0;in) output(x); elsefor(int i=t;i59，所以舍棄該結點所以舍棄該結點。按上述搜索原那么，對整按上述搜索原那么，對整個排列樹進行遍歷，共找個排列樹進行遍歷，共找到條可能的周游路徑，到條可能的周游路徑，其中費用最少的周游路徑其中費用最少的周游路徑為為1-3-2-4-1其費用為其費用為2545

9、剪枝函數(shù)的引入 剪枝函數(shù)的引入剪枝函數(shù)的引入 目的：提高回溯法的搜索效率；目的：提高回溯法的搜索效率； 剪枝函數(shù)的設定：剪枝函數(shù)的設定： 采用當前的最短路徑為為標準，對采用當前的最短路徑為為標準，對于有個結點的于有個結點的TSP問題來說，假設當前問題來說，假設當前搜索第層搜索第層(1i25，所以舍棄該結點所以舍棄該結點。I為根為根的子樹不可能包含更優(yōu)的解，剪去。的子樹不可能包含更優(yōu)的解，剪去。按上述搜索原那么，對整按上述搜索原那么，對整個排列樹進行遍歷，共找個排列樹進行遍歷，共找到條可能的周游路徑，到條可能的周游路徑，其中費用最少的周游路徑其中費用最少的周游路徑為為1-3-2-4-1其費用為其

10、費用為2547#include #include const int n=4; /圖的頂點數(shù)class Travelingfriend int TSP(int an, int v);private:void Swap(int &, int &);void Backtrack(int i);int ann, /圖G的鄰接矩陣 cv, /當前費用 bestv; /當前最優(yōu)值 *x, /當前解 *bestx, / 當前最優(yōu)解;48void Traveling:Backtrack(int i)if (i+1n)if (axn-2xn-1 & axn-10 & cv+ axn-2xn-1+axn-10b

11、estv) / 比較當前的最優(yōu)解與當前獲得的解，當前解更優(yōu)那么替換for (int j=0; jn; j+) bestxj=xj;bestv = cv + axn-2xn-1 + axn-10;return;for (int j=i; jn; j+)/ 判斷是否可進入xj子樹，此處實現(xiàn)了剪枝if (axi-1xj & cv+axi-1xjbestv)/ 搜索子樹Swap(xi, xj);cv += axi-1xi;Backtrack(i+1);cv -= axi-1xi;Swap(xi, xj);49int TSP(int an, int v)/ 初始化Traveling Y;Y.x=new

12、int n;for (int i=0; in; i+) Y.xi=i;for (i=0; in; i+) /連接代價對稱for (int j=0; j=i; j+) Y.aij=Y.aji=aij;Y.cv=0;Y.bestv=100000; / Y.bestx=v;coutAdjacency Matrix of G:n;for (i=0; in; i+)for (int j=0; jn; j+) coutsetw(5)Y.aij;coutendl;Y.Backtrack(1);delete Y.x;return Y.bestv;50void main()int tn=0,30,6,5,4,1

13、0,20, vn=0,1,2,3;coutnBestv= TSP(t, v)nnPath = ;for (int i=0; in; i+) coutvi+1setw(4);coutv0+1endlendl;復雜度分析復雜度分析算法backtrack在最壞情況下可能需要更新當前最優(yōu)解O(n-1)!)次，每次更新bestx需計算時間O(n)，從而整個算法的計算時間復雜性為O(n!)。 51常用的TSP問題求解方案 常用的求解常用的求解TSP問題的方案問題的方案 遺傳算法 模擬退火 神經(jīng)網(wǎng)絡 并行算法52N皇后問題皇后問題53皇后問題 P129 皇后問題皇后問題 問題描述：在問題描述：在n*n格的棋

14、盤上放置彼此不受格的棋盤上放置彼此不受攻擊的個皇后。攻擊的個皇后。 按國際象棋規(guī)那么，皇后可以攻擊與之處按國際象棋規(guī)那么，皇后可以攻擊與之處于同一行或同一列或同一斜線上的棋子。于同一行或同一列或同一斜線上的棋子。54皇后問題 皇后問題皇后問題 大數(shù)學家高斯于大數(shù)學家高斯于1850年提出年提出 N. Wirth在在?程序程序=算算法法+數(shù)據(jù)結構數(shù)據(jù)結構?中給中給出了該問題的回溯算出了該問題的回溯算法法Pascal語言實現(xiàn)語言實現(xiàn) 可獲得個解，但可獲得個解，但實際上只有個不實際上只有個不同解考慮棋盤的對同解考慮棋盤的對稱性稱性55皇后問題的個不同解圖示說明圖示說明56其中一個可行解的圖示其中一個可

15、行解：x1 x2 x3 x4 x5 x6 x7 x81 5 8 6 3 7 2 4表示第個皇后被放在第行的第列上57算法設計 算法設計算法設計 用元組x1:n表示n皇后問題的解 xi表示皇后i放在第i行的第xi列上 用完全叉樹表示解空間用完全叉樹表示解空間 剪枝函數(shù)設計剪枝函數(shù)設計：對于兩個皇后A(i,j)、B(k,l) 兩個皇后不同行：i不等于k; 兩個皇后不同列：j不等于l; 兩個皇后不同一條斜線 |i-k|j-l|，即兩個皇后不處于同一條y=x+a或y=-x+a的直線上58實現(xiàn)遞歸算法bool Queen:Place(int k) for (int j=1;jn) sum+; else

16、for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); 59實現(xiàn)迭代算法void nQueen( int nn) n=nn; sum=0; x= new intn+1; for (int i=0;i0) xk+=1; while(xk=n) & !(place(k) xk+=1; /搜索可能的放置位置 if (xkn，表示算法搜索到葉結點 得到一個新的方案，當前找到的m可著色方案數(shù)加1； 當in時，表示當前擴展結點為解空間樹的內(nèi)部結點，該結點有xi=1,2,m共m個子結點 對該結點的每一個子結點，根據(jù)鄰接矩陣a和兩個頂點的著色，判斷其可行

17、性； 如果可行，繼續(xù)按深度優(yōu)先方式遞歸地對可行子樹進行搜索； 否那么，將以該子結點為根結點的子樹中的所有結點都設置為死結點，算法回溯到為活結點的最近的父結點處繼續(xù)按深度優(yōu)先方式進行搜索；剪枝函數(shù)剪枝函數(shù)69解向量：(x1, x2, , xn)表示頂點i所著顏色xi 可行性約束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復。類Coloring記錄解空間中結點信息void Color:Backtrack(int t) if (tn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (

18、Ok(t) Backtrack(t+1); xt=0; bool Color:Ok(int k)/ 檢查顏色可用性 for (int j=1;jn時，算法搜索到葉結點，得到新的圓排時，算法搜索到葉結點，得到新的圓排列方案并計算當前圓排列長度；列方案并計算當前圓排列長度； 如果小于當前的最優(yōu)解，那么將該解定為當如果小于當前的最優(yōu)解，那么將該解定為當前的最優(yōu)解；前的最優(yōu)解； 否那么，舍棄；否那么，舍棄； 當當in時，表示當前擴展結點為結空間樹的內(nèi)時，表示當前擴展結點為結空間樹的內(nèi)部結點，此時算法要選擇下一個要排列的圓，部結點，此時算法要選擇下一個要排列的圓，并計算相應的下界函數(shù)。并計算相應的下界函

19、數(shù)。 如果滿足下界約束小于設定的閾值，繼如果滿足下界約束小于設定的閾值，繼續(xù)按深度優(yōu)先方式遞歸地對相應子樹進行搜續(xù)按深度優(yōu)先方式遞歸地對相應子樹進行搜索；索； 否那么，剪去該子樹，算法回溯到為活結點否那么，剪去該子樹，算法回溯到為活結點的最近的父結點處繼續(xù)按深度優(yōu)先方式進行的最近的父結點處繼續(xù)按深度優(yōu)先方式進行搜索；搜索；76算法實現(xiàn)void Circle:Backtrack( int t) if(tn) compute();compute(); elsefor(int j=t;j=n;j+) Swap(rt,rj); float centerx= Center(t);Center(t); i

20、f(centerx+rt+r1min) /下界約束xt=centerx;Backtrack(t+1); Swap(rt,rj);已經(jīng)找到一個新的圓排列已經(jīng)找到一個新的圓排列方案，計算該方案的圓排方案，計算該方案的圓排列長度列長度計算當前所選擇的圓的圓心計算當前所選擇的圓的圓心橫坐標（取最小值返回）橫坐標（取最小值返回）77算法實現(xiàn)Float Circle:Center(int t) float temp=0; for(int j=1;jtemp) temp= valuex; 2)()(22jrtrjrtrjrtr242x記錄當前圓排列中各圓的圓心橫坐標78算法實現(xiàn)float Circle:Co

21、mpute(void) float low=0, high=0; for(int i=1;i=n;i+) if (xi-rihigh) high = xi+ri; if (high-lowmin) min = high low; low/high記錄當前圓排列中各圓的最左/右橫坐標79算法復雜性分析)!1( nO析圓排列的算法復雜性分80回溯法的效率分析回溯法的效率分析回溯法的效率分析影響回溯法效率的主要因素 產(chǎn)生xk的時間 滿足顯約束的xk值的個數(shù) 計算約束函數(shù)constrain的時間 計算上界函數(shù)bound的時間1. 滿足約束函數(shù)和上界函數(shù)約束的所有xk的個數(shù)好的約束函數(shù)可以明顯降低生成結

22、點的數(shù)量，但往往需要較大的計算量。在選擇約束函數(shù)時，通常采取在生成結點數(shù)和約束函數(shù)計算量之間取折衷。解空間的結構一旦選定，影響回溯法效解空間的結構一旦選定，影響回溯法效率的前三個因素就可以確定，剩下的就率的前三個因素就可以確定，剩下的就是考慮回溯過程中生成結點的個數(shù)。是考慮回溯過程中生成結點的個數(shù)。隨問題的具體內(nèi)容以及結點的隨問題的具體內(nèi)容以及結點的不同生成方式而變動不同生成方式而變動81對于許多問題而言，在搜索試探時選取xi的值順序是任意的。在其它條件相當?shù)那疤嵯拢尶扇≈底钌俚脑谄渌鼦l件相當?shù)那疤嵯?，讓可取值最少的xi優(yōu)先優(yōu)先。從圖中關于同一問題的2棵不同解空間樹，可以體會到這種策略的潛力

23、。圖(a)中，從第1層剪去1棵子樹，那么從所有應當考慮的3元組中一次消去12個3元組。對于圖(b)，雖然同樣從第1層剪去1棵子樹，卻只從應當考慮的3元組中消去8個3元組。前者的效果明顯比后者好。(a)(b)82存在的困難 存在的困難存在的困難 對回溯法在解具體問題時所產(chǎn)生的結點對回溯法在解具體問題時所產(chǎn)生的結點數(shù)的估計數(shù)的估計 即使對兩個非常相近的實例，其產(chǎn)生的即使對兩個非常相近的實例，其產(chǎn)生的結點數(shù)也會存在很大的差異結點數(shù)也會存在很大的差異 可參考性不理想可參考性不理想 解決的方法：概率方法解決的方法：概率方法83用概率方法估計將產(chǎn)生的接點數(shù) 用概率方法估計將產(chǎn)生的結點數(shù)用概率方法估計將產(chǎn)生的結點數(shù) 主要思想主要思想 在解空間樹上產(chǎn)生一條隨機路徑，然后沿該路徑估算解空間中滿足約束條件的結點樹m。 直到延伸到葉節(jié)點或所有子節(jié)點都不滿足約束條件為止84public int estimate( int n )public int estimate( int n ) int m=