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

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

3、的擴(kuò)展結(jié)點(diǎn)。在完成對(duì)子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個(gè)兒子（如果存在） 寬度優(yōu)先的問題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn) 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法,5,遞歸回溯,回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。 void backtrack (int t) if (tn) output(x); else for (int

4、 i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,6,迭代回溯,采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過程。 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) ,其中，n表示葉子所在的層，t 是當(dāng)前層；f(n,t)，g(n,t)分別表示當(dāng)前擴(kuò)展結(jié)點(diǎn)起始編號(hào)和終止編號(hào),constraint(t)、bound(t)是當(dāng)前擴(kuò)展結(jié)點(diǎn)的

5、約束函數(shù)和限界函數(shù)；h(i)是第i個(gè)可選值； solution(t)判斷是否得到問題的可行解。,7,子集樹與排列樹,遍歷子集樹需O(2n)計(jì)算時(shí)間,遍歷排列樹需要O(n!)計(jì)算時(shí)間,void backtrack (int 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(

6、t+1); swap(xt, xi); ,8,裝載問題,有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且,裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。 容易證明，如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿； (2)將剩余的集裝箱裝上第二艘輪船。 將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價(jià)于以下特殊的0-1背包問題。,用回溯法設(shè)計(jì)解裝載問題的O(2n)計(jì)算時(shí)間算法。在某些情況下該算法優(yōu)于動(dòng)

7、態(tài)規(guī)劃算法。,9,裝載問題,解空間：子集樹 可行性約束函數(shù)(選擇當(dāng)前元素)： 上界函數(shù)(不選擇當(dāng)前元素)： 當(dāng)前載重量cw+剩余集裝箱的重量r當(dāng)前最優(yōu)載重量bestw,private static void backtrack (int i) / 搜索第i層結(jié)點(diǎn) if (i n) / 到達(dá)葉結(jié)點(diǎn) 更新最優(yōu)解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; ,10,批處理作業(yè)調(diào)度,給定n個(gè)作業(yè)的集合J1,J2,Jn。每個(gè)作業(yè)必須先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)

8、Ji需要機(jī)器j的處理時(shí)間為tji。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。所有作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。 批處理作業(yè)調(diào)度問題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。,這3個(gè)作業(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。易見，最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。,11,批處理作業(yè)調(diào)度,解空間：排列樹,private static void backtrack(int i) if (i

9、n) for (int j = 1; j f1)?f2i-1:f1)+mxj2; f+=f2i; if (f bestf) MyMath.swap(x,i,j); backtrack(i+1); MyMath.swap(x,i,j); f1-=mxj1; f-=f2i; ,public class FlowShop static int n, / 作業(yè)數(shù) f1, / 機(jī)器1完成處理時(shí)間 f, / 完成時(shí)間和 bestf; / 當(dāng)前最優(yōu)值 static int m; / 各作業(yè)所需的處理時(shí)間 static int x; / 當(dāng)前作業(yè)調(diào)度 static int bestx; / 當(dāng)前最優(yōu)作業(yè)調(diào)度

10、static int f2; / 機(jī)器2完成處理時(shí)間,12,符號(hào)三角形問題,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,下圖是由14個(gè)“+”和14個(gè)“-”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“-”。,在一般情況下，符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)三角形問題要求對(duì)于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+”和“-”的個(gè)數(shù)相同。,13,符號(hào)三角形問題,解向量：用n元組x1:n表示符號(hào)三角形的第一行。 可行性約束函數(shù)：當(dāng)前符號(hào)三角形所包含的“+”個(gè)數(shù)與“-”個(gè)數(shù)均不超過n*(n+1)/4 無解的

11、判斷：n*(n+1)/2為奇數(shù),private static void backtrack (int t) if (counthalf)|(t*(t-1)/2-counthalf) return; if (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; ,+ + - + - + + +

12、- - - - + - + + + - - + + - - + - - - +,復(fù)雜度分析 計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有 O(2n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號(hào)三角形問題的回溯算法所需的計(jì)算時(shí)間為 O(n2n)。,14,n后問題,在nn格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在nn格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。,15,解向量：(x1, x2, , xn) 顯約束：xi=1,2, ,n 隱約束： 1)不同列：xixj 2)不處于同一正、反對(duì)角線：|

13、i-j|xi-xj|,n后問題,private static boolean 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背包問題,解空間：子集樹 可行性約束函數(shù)： 上界函數(shù)：,private static double bound(int i) / 計(jì)算上界 double cleft = c - cw; / 剩余容量 double bound = cp; / 以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i = n ,17,最

14、大團(tuán)問題,給定無向圖G=(V，E)。如果UV，且對(duì)任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。 如果UV且對(duì)任意u，vU有(u，v)E，則稱U是G的空子圖。G的空子圖U是G的獨(dú)立集當(dāng)且僅當(dāng)U不包含在G的更大的空子圖中。G的最大獨(dú)立集是G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。 對(duì)于任一無向圖G=(V，E)其補(bǔ)圖G=(V1，E1)定義為：V1=V，且(u，v)E1當(dāng)且僅當(dāng)(u，v)E。,U是G的最大團(tuán)當(dāng)且僅當(dāng)U是G的最大獨(dú)立集。,18,最大團(tuán)問題,解空間：子集樹 可行性約束函數(shù)：頂點(diǎn)i到已選入的頂點(diǎn)集中每

15、一個(gè)頂點(diǎn)都有邊相連。 上界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。,private static void backtrack(int i) if (i n) / 到達(dá)葉結(jié)點(diǎn) for (int j = 1; j bestn) / 進(jìn)入右子樹 xi = 0; backtrack(i + 1); ,復(fù)雜度分析 最大團(tuán)問題的回溯算法backtrack所需的計(jì)算時(shí)間顯然為O(n2n)。,19,進(jìn)一步改進(jìn)算法的建議,選擇合適的搜索順序，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。 定義Si=vi,vi+1,

16、.,vn，依次求出Sn,Sn-1,.,S1的解。從而得到一個(gè)更精確的上界函數(shù)，若cn+Si=max則剪枝。同時(shí)注意到：從Si+1到Si，如果找到一個(gè)更大的團(tuán)，那么vi必然屬于找到的團(tuán)，此時(shí)有Si=Si+1+1，否則Si=Si+1。因此只要max的值被更新過，就可以確定已經(jīng)找到最大值，不必再往下搜索了。,20,圖的m著色問題,給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問題是圖的m可著色判定問題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m

17、的問題稱為圖的m可著色優(yōu)化問題。,21,解向量：(x1, x2, , xn)表示頂點(diǎn)i所著顏色xi 可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。,圖的m著色問題,private static void backtrack(int t) if (tn) sum+; else for (int i=1;i=m;i+) xt=i; if (ok(t) backtrack(t+1); private static boolean ok(int k) / 檢查顏色可用性 for (int j=1;j=n;j+) if (akj ,復(fù)雜度分析 圖m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是 對(duì)于每一個(gè)內(nèi)結(jié)

18、點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是,思考：圖的m著色問題與圖的最大團(tuán)問題有何關(guān)系，你能否利用這個(gè)關(guān)系改進(jìn)最大團(tuán)問題的上界？,22,旅行售貨員問題,解空間：排列樹,private static void backtrack(int i) if (i = n) if (axn - 1xn Float.MAX_VALUE ,復(fù)雜度分析 算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O(n-1)!)次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。,23,圓排列問題,給定n個(gè)大小

19、不等的圓c1,c2,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排列。例如，當(dāng)n=3，且所給的3個(gè)圓的半徑分別為1，1，2時(shí)，這3個(gè)圓的最小長(zhǎng)度的圓排列如圖所示。其最小長(zhǎng)度為,24,圓排列問題,private static float center(int t) / 計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo) float temp=0; for (int j=1;jtemp) temp=valuex; return temp; ,private static void compute() / 計(jì)算當(dāng)前圓排列的長(zhǎng)度 float low

20、=0, high=0; for (int i=1;ihigh) high=xi+ri; if (high-lowmin) min=high-low; ,private static void backtrack(int t) if (tn) compute(); else for (int j = t; j = n; j+) MyMath.swap(r, t, j); float centerx=center(t); if (centerx+rt+r1min) /下界約束 xt=centerx; backtrack(t+1); MyMath.swap(r, t, j); ,復(fù)雜度分析 由于算法

21、backtrack在最壞情況下可能需要計(jì)算O(n!)次當(dāng)前圓排列長(zhǎng)度，每次計(jì)算需O(n)計(jì)算時(shí)間，從而整個(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è)就夠了。,25,連續(xù)郵資問題,假設(shè)國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，在1張信封上可貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。,例如，當(dāng)n=5和m=4時(shí)，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。,26,連續(xù)郵資問題,解向量：用n元組x1:n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是惟一的選擇。 可行性約束函數(shù)：已選定x1:i-1，最大連續(xù)郵資區(qū)間是1:r，接下來xi的可取值范圍是xi-1+1:r+1。,如何確定r的值？ 計(jì)算X1:i的最大連續(xù)郵資區(qū)間在本算法中被頻繁使用到，因此勢(shì)必要找到一個(gè)高效的方法?？紤]到直接遞歸的求解復(fù)雜度太高，我們不妨嘗試計(jì)算用不超過m張面值為x1:i的郵票貼出郵資k