計(jì)算機(jī)算法設(shè)計(jì)與分析(王曉東)第5章 回溯法

1、12學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)理解回溯法的深度優(yōu)先搜索策略。掌握用回溯法解題的算法框架（1）遞歸回溯（2）迭代回溯（3）子集樹(shù)算法框架（4）排列樹(shù)算法框架3通過(guò)應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計(jì)策略。（1）裝載問(wèn)題；（2）批處理作業(yè)調(diào)度；（3）符號(hào)三角形問(wèn)題（4）n后問(wèn)題；（5）0-1背包問(wèn)題；（6）最大團(tuán)問(wèn)題；（7）圖的m著色問(wèn)題（8）旅行售貨員問(wèn)題（9）圓排列問(wèn)題（10）電路板排列問(wèn)題（11）連續(xù)郵資問(wèn)題4n有許多問(wèn)題，當(dāng)需要找出它的解集或者要求回答什么解是滿(mǎn)足某些約束條件的最佳解時(shí)，往往要使用回溯法。n回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合

2、數(shù)相當(dāng)大的問(wèn)題。n回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。5問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(x1,x2,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿(mǎn)足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿(mǎn)足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少

3、，搜索方法簡(jiǎn)單）。n=3時(shí)的0-1背包問(wèn)題用完全二叉樹(shù)表示的解空間6n擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱(chēng)為擴(kuò)展結(jié)點(diǎn)n活結(jié)點(diǎn):一個(gè)自身已生成但其兒子還沒(méi)有全部生成的節(jié)點(diǎn)稱(chēng)做活結(jié)點(diǎn)n死結(jié)點(diǎn):一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱(chēng)做死結(jié)點(diǎn)n深度優(yōu)先的問(wèn)題狀態(tài)生成法：如果對(duì)一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個(gè)兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對(duì)子樹(shù)C（以C為根的子樹(shù)）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個(gè)兒子（如果存在）n寬度優(yōu)先的問(wèn)題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)n回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問(wèn)題狀態(tài)，要不斷地利用限界函數(shù)(bounding fun

4、ction)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱(chēng)為回溯法7(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿(mǎn)足約束的子樹(shù)；用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n)。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2h(n

5、)或O(h(n)!)內(nèi)存空間。8nn=3, C=30, w=16, 15, 15, v=45, 25, 25ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45CCr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25n) output(x); else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x); else for (int i=0;in) output(x); else for (int i=t;i n) / 到達(dá)葉結(jié)

6、點(diǎn) 更新最優(yōu)解bestx,bestw; return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子樹(shù) backtrack(i + 1); r += wi; 15給定n個(gè)作業(yè)的集合J1,J2,Jn。每個(gè)作業(yè)必須先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時(shí)間為tji。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。所有作業(yè)在機(jī)器2上完成處理的時(shí)間和稱(chēng)為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問(wèn)題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。jittji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323這3個(gè)作

7、業(yè)的6種可能的調(diào)度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應(yīng)的完成時(shí)間和分別是19，18，20，21，19，19。易見(jiàn)，最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。16解空間：排列樹(shù)void Flowshop:Backtrack(int i) if (i n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f half)|(t*(t-1)/2-counthalf) return; i

8、f (tn) sum+; else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; + + - + - + + - - - - +- + + + - - + + - - + - - - +復(fù)雜度分析復(fù)雜度分析計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有 O(2n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號(hào)三角形問(wèn)題的回溯算

9、法所需的計(jì)算時(shí)間為 O(n2n)。19在nn格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線(xiàn)上的棋子。n后問(wèn)題等價(jià)于在nn格的棋盤(pán)上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線(xiàn)上。1 2 3 4 5 6 7 812345678QQQQQQQQ20解向量：(x1, x2, , xn)顯約束：xi=1,2, ,n隱約束： 1)不同列：xi xj 2)不處于同一正、反對(duì)角線(xiàn)：|i-j| |xi-xj|bool Queen:Place(int k) for (int j=1;jn) sum+; else for (int i=1;i=n

10、;i+) xt=i; if (Place(t) Backtrack(t+1); 21解空間：子集樹(shù)可行性約束函數(shù)：上界函數(shù)：11cxwniiitemplateTypep Knap:Bound(int i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿(mǎn)背包 if (i n) / 到達(dá)葉結(jié)點(diǎn) for (int j = 1; j = n; j+) bestxj = xj; bestn =

11、cn; return; / 檢查頂點(diǎn) i 與當(dāng)前團(tuán)的連接 int OK = 1; for (int j = 1; j bestn) / 進(jìn)入右子樹(shù) xi = 0; Backtrack(i+1);復(fù)雜度分析復(fù)雜度分析最大團(tuán)問(wèn)題的回溯算法backtrack所需的計(jì)算時(shí)間顯然為O(n2n)。1245324選擇合適的搜索順序，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。定義Si=vi,vi+1,.,vn，依次求出Sn,Sn-1,.,S1的解。從而得到一個(gè)更精確的上界函數(shù)，若cn+Sin) sum+; for (int i=1;

12、i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (Ok(t) Backtrack(t+1); Xt=0; bool Color:Ok(int k)/ 檢查顏色可用性 for (int j=1;j=n;j+) if (akj=1)&(xj=xk) return false; return true;復(fù)雜度分析復(fù)雜度分析圖m可著色問(wèn)題的解空間樹(shù)中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是對(duì)于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是10niim)() 1/(

13、) 1()(10nnniinmOmmnmmnm27解空間：排列樹(shù)templatevoid Traveling:Backtrack(int i) if (i = n) if (axn-1xn != NoEdge & axn1 != NoEdge & (cc + axn-1xn + axn1 bestc | bestc = NoEdge) for (int j = 1; j = n; j+) bestxj = xj; bestc = cc + axn-1xn + axn1; else for (int j = i; j = n; j+) / 是否可進(jìn)入xj子樹(shù)? if (axi-1

14、xj != NoEdge & (cc + axi-1xi bestc | bestc = NoEdge) / 搜索子樹(shù) Swap(xi, xj); cc += axi-1xi; Backtrack(i+1); cc -= axi-1xi; Swap(xi, xj); 復(fù)雜度分析復(fù)雜度分析算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O(n-1)!)次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑，對(duì)應(yīng)于1,2，,n的一個(gè)全排列。 根節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，其余節(jié)點(diǎn)分支數(shù)不同，第一層有n-1個(gè)節(jié)點(diǎn)，第二層有n-2個(gè)節(jié)點(diǎn)。

15、第n-1層有一個(gè)節(jié)點(diǎn)。這樣的樹(shù)成為排列樹(shù)。28給定n個(gè)大小不等的圓c1,c2,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問(wèn)題要求從n個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排列。例如，當(dāng)n=3，且所給的3個(gè)圓的半徑分別為1，1，2時(shí)，這3個(gè)圓的最小長(zhǎng)度的圓排列如圖所示。其最小長(zhǎng)度為24229float Circle:Center(int t)/ 計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo) float temp=0; for (int j=1;jtemp) temp=valuex; return temp;void Circle:Compute(void)/ 計(jì)算當(dāng)前圓排列的長(zhǎng)度 f

16、loat low=0, high=0; for (int i=1;i=n;i+) if (xi-rihigh) high=xi+ri; if (high-lown) Compute(); else for (int j = t; j = n; j+) Swap(rt, rj); float centerx=Center(t); if (centerx+rt+r1min) /下界約束 xt=centerx; Backtrack(t+1); Swap(rt, rj); 復(fù)雜度分析復(fù)雜度分析由于算法backtrack在最壞情況下可能需要計(jì)算O(n!)次當(dāng)前圓排列長(zhǎng)度，每次計(jì)算需O(n)計(jì)算時(shí)間，從而

17、整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n+1)!) 上述算法尚有許多改進(jìn)的余地。例如，象1,2,n-1,n和n,n-1, ,2,1這種互為鏡像的排列具有相同的圓排列長(zhǎng)度，只計(jì)算一個(gè)就夠了，可減少約一半的計(jì)算量。另一方面，如果所給的n個(gè)圓中有k個(gè)圓有相同的半徑，則這k個(gè)圓產(chǎn)生的k!個(gè)完全相同的圓排列，只計(jì)算一個(gè)就夠了。 30假設(shè)國(guó)家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問(wèn)題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，在1張信封上可貼出從郵資1開(kāi)始，增量為1的最大連續(xù)郵資區(qū)間。例如，當(dāng)n=5和m=4時(shí)，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大

18、連續(xù)郵資區(qū)間是1到70。31解向量：用n元組x1:n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是唯一的選擇?？尚行约s束函數(shù)：已選定x1:i-1，最大連續(xù)郵資區(qū)間是1:r，接下來(lái)xi的可取值范圍是xi-1+1:r+1。如何確定r的值？計(jì)算X1:i的最大連續(xù)郵資區(qū)間在本算法中被頻繁使用到，因此勢(shì)必要找到一個(gè)高效的方法。考慮到直接遞歸的求解復(fù)雜度太高，我們不妨嘗試計(jì)算用不超過(guò)m張面值為x1:i的郵票貼出郵資k所需的最少郵票數(shù)yk。通過(guò)yk可以很快推出r的值。事實(shí)上，yk可以通過(guò)遞推在O(n)時(shí)間內(nèi)解決：for (int j=0; j= xi-2*(m-1);j+) if (yjm) for (int k=1;k=m-yj;k+) if (yj+kyj+xi-1*k) yj+xi-1*k=yj+k; while (yrmaxint) r+;32通過(guò)前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴(lài)于以下因素：(1)產(chǎn)生xk的時(shí)間；(2)滿(mǎn)足顯約束的xk值的個(gè)數(shù)；(3)計(jì)算約束函數(shù)constraint的時(shí)間；(4)計(jì)算上界函數(shù)bound的時(shí)間；(5)滿(mǎn)足約束函數(shù)