算法基礎(chǔ) chap5學習資料

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

X1=115121o75173133282623211383292419454035615651141196416303227252220234

X2=2341

3

41

241

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

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有詳細說明13回溯法的算法框架迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。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個元素的S中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為子集樹。通常有2n個葉子結(jié)點，結(jié)點總數(shù)為2n+1-1。遍歷子集樹需要Ω(2n)的計算時間。所給的問題是確定n個元素滿足某種性質(zhì)的排列時，相應的解空間樹稱為排列樹。通常有n!個葉子結(jié)點。遍歷排列樹需要Ω(n!)的計算時間。15回溯法的算法框架用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。16n后問題（5.5）算法設(shè)計解向量：(x1,x2,…,xn)，xi表示第i個皇后的列號。解空間：用完全n叉樹表示（n的n次方解空間）。顯約束：xi

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

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

即：|i-j|

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

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

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