第五章 回溯法搜索技術(shù)的相關(guān)概念回溯法的算法框架用回溯法解決問題實(shí)例回溯法的效率分析2搜索技術(shù)問題描述假定問題的解能表示成一個(gè)n-元組(X1,…,Xn)，其中Xi取自某個(gè)有窮集Si。所有這些n-元組構(gòu)成問題的解空間。假設(shè)集合Si的大小是mi，則可能的元組數(shù)為m=m1m2…mn。考慮兩類問題：存在性問題：求滿足某些條件的一個(gè)或全部元組，如果不存在這樣的元組，算法應(yīng)返回false；這些條件稱為約束條件。滿足約束條件的元組稱為問題的可行解。優(yōu)化問題：給定一組約束條件，在問題的可行解中求使某目標(biāo)函數(shù)達(dá)到最大（?。┲档脑M，即最優(yōu)解。解決這類問題的一般方法是搜索技術(shù)，即系統(tǒng)化的搜索解空間的技術(shù)，主要包括回溯法和分支限界法。3搜索技術(shù)實(shí)例1：8后問題在8×8的棋盤上放置8個(gè)皇后，使得這8個(gè)皇后不在同一行、同一列及同一斜角線上。QQQQQQQQ12345678123456784搜索技術(shù)8皇后問題可以表示成8-元組(x1,…,x8)，其中xi是放在第i行的皇后所在的列號(hào)。于是，解空間由88個(gè)8-元組組成。約束條件：xi≠xjforalli,j|xi-xj|≠|(zhì)j-i|約束條件之一為沒有兩個(gè)xi相同(即任意兩個(gè)皇后不在同一列上)。將其加入到元組的定義中，這時(shí)解空間的大小由88個(gè)元組減少到8!個(gè)元組。n-皇后問題只要可行解，不需要最優(yōu)解。5搜索技術(shù)狀態(tài)空間樹解空間的樹結(jié)構(gòu)稱為解空間樹，它是嘗試選擇元組的各個(gè)分量時(shí)產(chǎn)生的樹結(jié)構(gòu)。樹中的每個(gè)結(jié)點(diǎn)代表問題求解過程中的一個(gè)狀態(tài)，根節(jié)點(diǎn)到它的路徑代表對(duì)一些分量已作出的選擇。根到一個(gè)節(jié)點(diǎn)的路徑可以表示為(x(1),…,x(k))，也用這個(gè)元組標(biāo)識(shí)該節(jié)點(diǎn)。狀態(tài)空間樹的所有節(jié)點(diǎn)構(gòu)成問題求解的狀態(tài)空間。如果由根到節(jié)點(diǎn)S的那條路徑確定了解空間的一個(gè)元組,則稱S對(duì)應(yīng)的狀態(tài)為一個(gè)解空間狀態(tài)。如果一個(gè)解狀態(tài)代表的元組滿足約束條件稱其為可行解。6搜索技術(shù)4-皇后問題的解空間樹（4?。?，節(jié)點(diǎn)按深度優(yōu)先檢索編號(hào)12503418

X1=115121o75173133282623211383292419454035615651141196416303227252220234

X2=2341

3

41

241

23X3=31143423243443423243413x4=1…………7搜索技術(shù)搜索算法搜索算法通過展開解空間樹來找所求的解。用以下術(shù)語描述展開狀態(tài)空間樹的各種方法：活結(jié)點(diǎn)：已展開一個(gè)以上子節(jié)點(diǎn)，但所有子結(jié)點(diǎn)尚未全部產(chǎn)生的結(jié)點(diǎn)。死結(jié)點(diǎn)：被限界或已展開了所有子結(jié)點(diǎn)的結(jié)點(diǎn)。E-結(jié)點(diǎn)(擴(kuò)展結(jié)點(diǎn))：當(dāng)前正在展開子結(jié)點(diǎn)的結(jié)點(diǎn)（某刻唯一）。深度優(yōu)先展開方法：一個(gè)E-結(jié)點(diǎn)C展開自己的一個(gè)子結(jié)點(diǎn)R后，就讓結(jié)點(diǎn)R成為E-結(jié)點(diǎn)，當(dāng)完成R的所有子樹的搜索后，讓C重新成為E-結(jié)點(diǎn)，繼續(xù)展開C的子結(jié)點(diǎn)(如果存在)。這種方法相當(dāng)于對(duì)解空間樹做深度優(yōu)先搜索，稱為深度優(yōu)先展開方法。廣度優(yōu)先展開方法：在當(dāng)前E-結(jié)點(diǎn)處，先展開自己的所有子結(jié)點(diǎn)，然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)E-結(jié)點(diǎn)。8搜索技術(shù)剪枝使用啟發(fā)式的剪枝技術(shù)能使搜索算法只展開解空間樹的一部分，降低了搜索的開銷。剪枝函數(shù)從分析約束條件或某種啟發(fā)式得到。剪枝函數(shù)必須計(jì)算簡(jiǎn)單。9搜索技術(shù)搜索方式回溯法：加剪枝的深度優(yōu)先展開方法稱為回溯法。分枝限界法：以廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方式搜索解空間樹。10回溯法的算法框架回溯法回溯法是能避免不必要搜索的搜索法。適用于解一些組合數(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)先策略搜索?；厮莘ǎ簽榱吮苊馍赡切┎豢赡墚a(chǎn)生最優(yōu)解的問題狀態(tài)，要不斷地利用剪枝函數(shù)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。11回溯法的算法框架回溯法的基本步驟針對(duì)所給問題，定義問題的解空間；相當(dāng)于找出進(jìn)行窮舉的搜索范圍確定易于搜索的解空間結(jié)構(gòu)；一般是形成解空間樹以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹（一定不是可行解）；用限界函數(shù)剪去得不到最優(yōu)解的子樹（一定不是最優(yōu)解）。12回溯法的算法框架遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。voidbacktrack(intt)//t：遞歸深度，如何調(diào)用函數(shù)完成整個(gè)遞歸？{

if(t>n)output(x);//n：遞歸深度閾值

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}P118有詳細(xì)說明13回溯法的算法框架迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過程。voiditerativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){

if(solution(t))output(x);

elset++;}}

elset--;}}P118的說明14回溯法的算法框架子集樹與排列樹所給的問題是從n個(gè)元素的S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。通常有2n個(gè)葉子結(jié)點(diǎn)，結(jié)點(diǎn)總數(shù)為2n+1-1。遍歷子集樹需要Ω(2n)的計(jì)算時(shí)間。所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。通常有n!個(gè)葉子結(jié)點(diǎn)。遍歷排列樹需要Ω(n!)的計(jì)算時(shí)間。15回溯法的算法框架用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。16n后問題（5.5）算法設(shè)計(jì)解向量：(x1,x2,…,xn)，xi表示第i個(gè)皇后的列號(hào)。解空間：用完全n叉樹表示（n的n次方解空間）。顯約束：xi

xj，不同列。隱約束：設(shè)兩個(gè)皇后(i,xi)，(j,xj)在同一斜線上，則有： i–j

=xi–xj(斜率為1)或者i-j=xj-xi(斜率為-1)

即：|i-j|

|xi-xj|。因此，約束條件不同斜線可以轉(zhuǎn)化為：|i-j|

|xi-xj|?？尚行约s束place剪去不滿足上述約束條件的子樹。17n后問題遞歸回溯privatebooleanPlace(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}privatestaticvoidBacktrack(intt){if(t>n)sum++;//sum為當(dāng)前可行方案數(shù)elsefor(inti=1;i<=n;i++){ //一行中的n個(gè)放置位置x[t]=i;if(Place(t))Backtrack(t+1);}}18n后問題迭代回溯privatestaticvoidbacktrack(){x[1]=0;intk=1; /*k：搜索深度,行號(hào)*/while(k>0){ x[k]=x[k]+1; /*在當(dāng)前列加1的位置開始搜索*/while((x[k]<=n)&&(!place(x,k))) /*當(dāng)前列位置是否滿足條件*/x[k]=x[k]+1; /*不滿足條件,繼續(xù)搜索下一列位置*/if(x[k]<=n){ /*存在滿足條件的列*/if(k==n)sum++; /*是最后一個(gè)皇后,完成搜索*/else{k=k+1;x[k]=0;}/*不是,則處理下一行的皇后*/}else{ /*x[k]>n,已判斷完n列,均沒有滿足條件*/k=k–1; /*回溯到前一行*/}}}19n后問題算法分析運(yùn)行時(shí)間取決于所訪問結(jié)點(diǎn)個(gè)數(shù)c，每訪問一個(gè)結(jié)點(diǎn)，就調(diào)用一次place函數(shù)計(jì)算約束方程。place函數(shù)循環(huán)體的執(zhí)行次數(shù)，最多n-1次。因此，總次數(shù)為O(n)。結(jié)點(diǎn)個(gè)數(shù)是動(dòng)態(tài)生成的，對(duì)不同實(shí)例，具有不確定性。一般可由n的多項(xiàng)式確定。在4叉完全樹中，結(jié)點(diǎn)總數(shù)有40＋41＋42＋43＋44＝341個(gè)，回溯法處理時(shí)，c=27，約為前者的8%。實(shí)際模擬表明，當(dāng)n=8時(shí)，被訪問的結(jié)點(diǎn)數(shù)與結(jié)點(diǎn)總數(shù)之比約為1.5%。20n后問題4皇后問題包含顯約束條件的解空間樹21裝載問題（5.2）問題描述有一批共n個(gè)集裝箱要裝上兩艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且有：裝載問題要求確定是否有一個(gè)合理的裝載方案可將這些集裝箱裝上這兩艘輪船。可能裝不下？例：當(dāng)n=3，c1=c2=50，w=[10,40,40]時(shí)，可將貨箱1,2裝到第一艘船上，貨箱3裝到第二艘船上。如果w=[20,40,35]，則無法將貨箱全部裝走。當(dāng)集裝箱總重量為c1+c2時(shí)，等價(jià)于子集和問題，當(dāng)c1=c2且集裝箱總重量為2c1時(shí)，等價(jià)于劃分問題。22裝載問題裝載策略如果一個(gè)裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。首先將第一艘輪船盡可能裝滿；將剩余的集裝箱裝上第二艘輪船。證明設(shè)可行解在第一艘船裝入W1（≤c1）重量，在第二艘船裝入W2（≤c2）重量；設(shè)最大化第一艘船的裝船量為M1，則W1≤M1；而剩下的集裝箱重量之和＝總重量（W1+W2）－M1≤總重量－W1＝W2，剩下的集裝箱一定能裝入第二艘船。23裝載問題將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近c(diǎn)1。由此可知，裝載問題等價(jià)于以下特殊的0-1背包問題（wi=vi）。可以用動(dòng)態(tài)規(guī)劃求解，時(shí)間復(fù)雜度為O(min{nc,2n})?？梢杂没厮莘ㄇ蠼?，時(shí)間復(fù)雜度為O(2n)，在某些情況下優(yōu)于動(dòng)態(tài)規(guī)劃算法。24裝載問題回溯算法設(shè)計(jì)子集樹：左子結(jié)點(diǎn)表示x(i)=1，右子結(jié)點(diǎn)表示x(i)=0。cw記錄當(dāng)前結(jié)點(diǎn)相應(yīng)的裝載重量，bestw記錄當(dāng)前已經(jīng)獲得的最大裝載重量。剪枝函數(shù)約束函數(shù)：cw＋w(i)>c1，則殺死該左子結(jié)點(diǎn)。右子結(jié)點(diǎn)如何處理？右子結(jié)點(diǎn)的cw值與擴(kuò)展結(jié)點(diǎn)的cw值相等，因此，展開右子結(jié)點(diǎn)時(shí)，不檢查約束函數(shù)。限界函數(shù)：設(shè)r為未裝的貨箱的總重量，如cw+r<=bestw，則停止展開該結(jié)點(diǎn)，即剪去右子樹。左子結(jié)點(diǎn)如何處理？左子結(jié)點(diǎn)和父結(jié)點(diǎn)有相同的cw+r值，所以，展開左子結(jié)點(diǎn)時(shí)，不檢查限界函數(shù)。25裝載問題搜索過程：設(shè)x=(x(1),…,x(k-1))為當(dāng)前E結(jié)點(diǎn)；展開左子結(jié)點(diǎn)：如果cw+w(k)>c1，則停止展開該左子結(jié)點(diǎn)，r←r-w(k)，并展開右子結(jié)點(diǎn)；否則，x(k)←1，cw←cw+w(k)，r←r-w(k)，并令(x(1),…,x(k))為E結(jié)點(diǎn)；展開右子結(jié)點(diǎn)：如果cw+r≤bestw，則停止展開該右子結(jié)點(diǎn)，并回溯到最近的一個(gè)活結(jié)點(diǎn)；否則，令x(k)=0,(x(1),…,x(k))為E結(jié)點(diǎn)。回溯：從i=k-1開始，找x(i)=1的第一個(gè)i；修改cw和r的值：cw←cw-w(i)(最后的),r←r+w(i)(每次的i)。26裝載問題k=n時(shí)，x=(x(1),…,x(n-1))，cw+w(n)>c1，則左子結(jié)點(diǎn)是不可行結(jié)點(diǎn)，考慮右子結(jié)點(diǎn)：如果cw+r=cw>bestw，bestw←cw，x(n)←0；否則cw+r=cw<=bestw，右子結(jié)點(diǎn)被限界，回溯。cw+w(n)≤c1，則左子結(jié)點(diǎn)是可行結(jié)點(diǎn)：cw←cw+w(n)，如果cw>bestw，bestw←cw，x(n)←1；否則cw<=bestw，左子結(jié)點(diǎn)不含最優(yōu)解，同時(shí)右子結(jié)點(diǎn)也不可能有最優(yōu)解，回溯。bestw初始值為-∞在搜索解空間樹時(shí)，只要其左兒子節(jié)點(diǎn)是一個(gè)可行節(jié)點(diǎn)，搜索就進(jìn)入其左子樹。當(dāng)右子樹有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹搜索；否則將右子樹剪去。27裝載問題例：假定n=4，w=[8,6,2,3]，c1=12。狀態(tài)空間樹：裝載問題的解空間樹，未顯示葉結(jié)點(diǎn)28裝載問題遞歸過程展開的狀態(tài)空間樹：在進(jìn)入左、右子樹，遞歸進(jìn)入下一層之前，加入輸出cw和r的語句，輸出結(jié)果如下：ABKJE

110cw=0cw=8cw=8cw=10cw=801bestw=10bestw=110XYw=[8,6,2,3]，c1=12。290-1背包問題（5.6）算法描述與裝載問題類似，是一個(gè)優(yōu)化問題，因此不僅可以使用約束函數(shù)，而且可以使用限界函數(shù)做剪枝函數(shù)。子集樹：左子結(jié)點(diǎn)表示x(i)=1，右子結(jié)點(diǎn)表示x(i)=0。剪枝函數(shù)：約束函數(shù)：cw+wk≥M限界函數(shù)：cp+r≤bestpcw：到當(dāng)前節(jié)點(diǎn)時(shí)，已裝入背包的重量cp：到當(dāng)前節(jié)點(diǎn)時(shí)，已裝入背包的價(jià)值WK：當(dāng)前節(jié)點(diǎn)所要判斷物品（K）的重量M：背包所能容忍的最大重量r：當(dāng)前剩余物品（還未判斷取舍的物品）的價(jià)值和bestp：當(dāng)前已獲得的最優(yōu)價(jià)值（可行解，但不一定是最優(yōu)解）0-1背包問題1.上界是界線，越接近理論界線越有意義。r是當(dāng)前剩余物品（還未判斷取舍）的價(jià)值和,cp+r是否還有比2方法更接近理論界線的求上界方法？確定右子樹中解的上界將剩余物品按單位重量?jī)r(jià)值非遞增排序，依次在剩余背包中裝入物品，直到無法全部裝入某物品時(shí)，裝入該物品的一部分將背包填滿，此時(shí)對(duì)應(yīng)的價(jià)值是右子樹中解的上界。cp+r’300-1背包問題對(duì)于0-1背包問題的一個(gè)實(shí)例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。這4個(gè)物品的單位重量?jī)r(jià)值分別為[3,2,3.5,4]。以物品單位重量?jī)r(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝0.2的物品2。由此得一個(gè)解為[1,0.2,1,1]，其相應(yīng)價(jià)值為22。盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最優(yōu)值的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過22。對(duì)于相同背包，相同物品，背包問題的最優(yōu)解不小于0-1背包問題的最優(yōu)解。310-1背包問題對(duì)某一節(jié)點(diǎn)來說，剩余背包容量裝剩余物品，也可得到一個(gè)價(jià)值上界。cp+r’用這樣一個(gè)小的價(jià)值上界代替2計(jì)算出的價(jià)值上界，有什么好處？對(duì)某一節(jié)點(diǎn)，根據(jù)2方法，cp+r>bestp對(duì)某一節(jié)點(diǎn)，根據(jù)3方法，cp+r’<=bestp減掉更多子樹，提高搜索速度320-1背包問題2算法框架331)預(yù)處理：各物品按單位重量?jī)r(jià)值降序排序，重量放于數(shù)組w[]，價(jià)值放于數(shù)組p[]2)回溯算法Privatestaticvoidbacktrack(inti){ if(i>n){//reachtheleafnode bestp=cp; return;} //searchthesubtree if(cw+w[i]<=c){//entertheleftsubtree cw+=w[i];cp+=p[i]; backtrack(i+1); cw-=w[i];cp-=p[i];} if(bound(i+1)>bestp) backtrack(i+1); //entertherightsubtree}Privatestaticdoublebound(inti){Doublecleft=c-cw;doublebound=cp;//以單位重量?jī)r(jià)值遞減順序裝入while(i<=n&&w[i]<=cleft){ cleft-=w[i];bound+=p[i];i++}//裝滿背包If(i<=n) bound+=p[i]*cleft/w[i];returnbound;}340-1背包問題3.實(shí)例：n=8,M=110,W=[1,11,21,23,33,43,45,55],P=[11,21,31,33,43,53,55,65]圖中未用字母標(biāo)識(shí)的末端結(jié)點(diǎn)表示被剪枝的結(jié)點(diǎn)，可以不畫在圖中。圖中圈內(nèi)數(shù)字表示結(jié)點(diǎn)的重量和價(jià)值，圈外的數(shù)字表示其上界值。35旅行售貨員問題（5.9） 旅行商問題（Hamiltoniancircuit）某售貨員要到若干個(gè)城市去推銷商品。已知各個(gè)城市之間的路程（或旅費(fèi)）。他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一遍，最后回到駐地的路線，使得總的路程（或總旅費(fèi)）最小。用一個(gè)帶權(quán)圖G＝(V,E)來表示，頂點(diǎn)代表城市，邊表示城市之間的道路。圖中各邊所帶的權(quán)即是城市間的路程（或旅費(fèi)）。36旅行售貨員問題用1，2，…，n代表n個(gè)頂點(diǎn)，一個(gè)周游i1,i2…,in,i1用數(shù)組(i1,i2…,in)表示，它是旅行商問題的一個(gè)可行解。如果可行解的前k-1個(gè)分量x1,x2…,xk-1已經(jīng)確定,則判定x1,x2…,xk-1,xk能否形成一條路徑，只需做k-1次比較： xk≠x1,xk≠x2…,xk≠xk-1 構(gòu)成旅行商問題的顯性約束條件，可直接用在減小解空間樹。用w(i,j)記邊(i,j)的權(quán)值，cl記當(dāng)前路徑x1,x2…,xk-1的長(zhǎng)度，即旅行商問題求解使cl(k=n)取最小值的解。37旅行售貨員問題算法描述解空間：排列樹遞歸回溯算法中，i=n時(shí)，當(dāng)前擴(kuò)