1、1,有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。,回溯法,2,問題的解空間,問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,xn)的形式。 顯約束：對分量xi

2、的取值限定。 隱約束：為滿足問題的解而對不同分量之間施加的約束。 解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。,注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。,n=3時的0-1背包問題用完全二叉樹表示的解空間,3,生成問題狀態(tài)的基本方法,擴展結點:一個正在產(chǎn)生兒子的結點稱為擴展結點 活結點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結點 死結點:一個所有兒子已經(jīng)產(chǎn)生的結點稱做死結點 深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結點。在完成對

3、子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子（如果存在） 寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結點變成死結點之前，它一直是擴展結點 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實際上不可能產(chǎn)生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法,4,回溯法的基本思想,(1)針對所給問題，定義問題的解空間； (2)確定易于搜索的解空間結構； (3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。,常用剪枝函數(shù)： 用約束函數(shù)在擴展結點處剪去不滿足

4、約束的子樹； 用限界函數(shù)剪去得不到最優(yōu)解的子樹。,用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n)。而顯式地存儲整個解空間則需要O(2h(n)或O(h(n)!)內(nèi)存空間。,5,遞歸回溯,回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。,void backtrack (int t) if (tn) output(x); else for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if

5、 (constraint(t) /t：遞歸深度；n：解空間樹的高度；f,g：當前擴展節(jié)點未搜索過節(jié)點的起始和終止編號；c,b：約束函數(shù)和限界函數(shù),6,迭代回溯,采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。,void iterativeBacktrack () int t=1; while (t0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,7,子集樹與排列樹,遍歷子集樹需O(2n)計算時間,遍歷排列樹需要O(n!)計算時間,void backtrack (in

6、t t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (legal(t) backtrack(t+1); ,void backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); ,8,裝載問題,有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且,裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果

7、有，找出一種裝載方案。 容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿； (2)將剩余的集裝箱裝上第二艘輪船。 將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。,用回溯法設計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。,9,裝載問題,解空間：子集樹 可行性約束函數(shù)(選擇當前元素)： 上界函數(shù)(不選擇當前元素)： 當前載重量cw+剩余集裝箱的重量r當前最優(yōu)載重量bestw,void backtrack (int i) /

8、搜索第i層結點 if (i n) / 到達葉結點 更新最優(yōu)解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; ,10,批處理作業(yè)調度,給定n個作業(yè)的集合J1,J2,Jn。每個作業(yè)必須先由機器1處理，然后由機器2處理。作業(yè)Ji需要機器j的處理時間為tji。對于一個確定的作業(yè)調度，設Fji是作業(yè)i在機器j上完成處理的時間。所有作業(yè)在機器2上完成處理的時間和稱為該作業(yè)調度的完成時間和。 批處理作業(yè)調度問題要求對于給定的n個作業(yè)，制定最佳作業(yè)調度方案，使其完成時間和達到最

9、小。,這3個作業(yè)的6種可能的調度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應的完成時間和分別是19，18，20，21，19，19。易見，最佳調度方案是1,3,2，其完成時間和為18。,11,批處理作業(yè)調度,解空間：排列樹,void Flowshop:Backtrack(int i) if (i n) for (int j = 1; j f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; ,cla

10、ss Flowshop friend Flow(int*, int, int ); private: void Backtrack(int i); int *M, / 各作業(yè)所需的處理時間 *x, / 當前作業(yè)調度 *bestx, / 當前最優(yōu)作業(yè)調度 *f2, / 機器2完成處理時間 f1, / 機器1完成處理時間 f, / 完成時間和 bestf, / 當前最優(yōu)值 n; / 作業(yè)數(shù);,12,符號三角形問題,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”

11、，2個異號下面都是“-”。,在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。,13,符號三角形問題,解向量：用n元組x1:n表示符號三角形的第一行。 可行性約束函數(shù)：當前符號三角形所包含的“+”個數(shù)與“-”個數(shù)均不超過n*(n+1)/4 無解的判斷：n*(n+1)/2為奇數(shù),void Triangle:Backtrack(int t) if (counthalf)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;i+)

12、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; ,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,復雜度分析 計算可行性約束需要O(n)時間，在最壞情況下有 O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為 O(n2n)。,14,n后問題,在nn格的棋盤上放置彼

13、此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在nn格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。,15,解向量：(x1, x2, , xn) 顯約束：xi=1,2, ,n 隱約束： 1)不同列：xixj 2)不處于同一正、反對角線：|i-j|xi-xj|,n后問題,bool Queen:Place(int k) for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); ,16,0-1背包問題,解空

14、間：子集樹 可行性約束函數(shù)： 上界函數(shù)：,template Typep Knap:Bound(int i) / 計算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價值遞減序裝入物品 while (i = n ,17,最大團問題,給定無向圖G=(V，E)。如果UV，且對任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數(shù)最多的團。 如果UV且對任意u，vU有(u，v)E，則稱U是G的空子圖。G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子

15、圖中。G的最大獨立集是G中所含頂點數(shù)最多的獨立集。 對于任一無向圖G=(V，E)其補圖G=(V1，E1)定義為：V1=V，且(u，v)E1當且僅當(u，v)E。,U是G的最大團當且僅當U是G的最大獨立集。,18,最大團問題,解空間：子集樹 可行性約束函數(shù)：頂點i到已選入的頂點集中每一個頂點都有邊相連。 上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。,void Clique:Backtrack(int i) / 計算最大團 if (i n) / 到達葉結點 for (int j = 1; j bestn) / 進入右子樹 xi = 0; Backtrack(i+1); ,復

16、雜度分析 最大團問題的回溯算法backtrack所需的計算時間顯然為O(n2n)。,19,圖的m著色問題,給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。,20,解向量：(x1, x2, , xn)表示頂點i所著顏色xi 可行性約束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復。,圖的m著色問題,void Color:Backtrack(int

17、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 (Ok(t) Backtrack(t+1); bool Color:Ok(int k) / 檢查顏色可用性 for (int j=1;j=n;j+) if (akj=1) ,復雜度分析 圖m可著色問題的解空間樹中內(nèi)結點個數(shù)是 對于每一個內(nèi)結點，在最壞情況下，用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是,21,旅行售貨員問題,解空間：排列樹,templat

18、e void Traveling:Backtrack(int i) if (i = n) if (axn-1xn != NoEdge ,復雜度分析 算法backtrack在最壞情況下可能需要更新當前最優(yōu)解O(n-1)!)次，每次更新bestx需計算時間O(n)，從而整個算法的計算時間復雜性為O(n!)。,22,圓排列問題,給定n個大小不等的圓c1,c2,cn，現(xiàn)要將這n個圓排進一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個圓的所有排列中找出有最小長度的圓排列。例如，當n=3，且所給的3個圓的半徑分別為1，1，2時，這3個圓的最小長度的圓排列如圖所示。其最小長度為,23,圓排列

19、問題,float Circle:Center(int t) / 計算當前所選擇圓的圓心橫坐標 float temp=0; for (int j=1;jtemp) temp=valuex; return temp; ,void Circle:Compute(void) / 計算當前圓排列的長度 float low=0, high=0; for (int i=1;ihigh) high=xi+ri; if (high-lowmin) min=high-low; ,void Circle:Backtrack(int t) if (tn) Compute(); else for (int j = t;

20、 j = n; j+) Swap(rt, rj); float centerx=Center(t); if (centerx+rt+r1min) /下界約束 xt=centerx; Backtrack(t+1); Swap(rt, rj); ,復雜度分析 由于算法backtrack在最壞情況下可能需要計算O(n!)次當前圓排列長度，每次計算需O(n)計算時間，從而整個算法的計算時間復雜性為O(n+1)!),上述算法尚有許多改進的余地。例如，象1,2,n-1,n和n,n-1, ,2,1這種互為鏡像的排列具有相同的圓排列長度，只計算一個就夠了，可減少約一半的計算量。另一方面，如果所給的n個圓中有k

21、個圓有相同的半徑，則這k個圓產(chǎn)生的k!個完全相同的圓排列，只計算一個就夠了。,24,連續(xù)郵資問題,假設國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對于給定的n和m的值，給出郵票面值的最佳設計，在1張信封上可貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。,例如，當n=5和m=4時，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。,25,連續(xù)郵資問題,解向量：用n元組x1:n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是唯一的選擇。 可行性約束函數(shù)：已選定x1:i-1，最大連續(xù)郵資區(qū)間是1:r，接下來xi的