第5章 算法分析設(shè)計

第五章 回溯法

(Backtracking)1有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉鳎蚴且环N組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘?問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。n=3時的0-1背包問題用完全二叉樹表示的解空間3生成問題狀態(tài)的基本方法擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法4回溯法的基本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。5遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。voidbacktrack(intt){

if(t>n)output(x);

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}6迭代回溯采用樹的非遞歸深度優(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--;}}7子集樹與排列樹遍歷子集樹需O(2n)計算時間遍歷排列樹需要O(n!)計算時間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}8裝載問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。用回溯法設(shè)計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。9解空間：子集樹可行性約束函數(shù)(選擇當前元素)：上界函數(shù)(不選擇當前元素)：當前載重量cw+剩余集裝箱的重量r當前最優(yōu)載重量bestwvoidbacktrack(inti){//搜索第i層結(jié)點

if(i>n)//到達葉結(jié)點更新最優(yōu)解bestx,bestw;return;r-=w[i];

if(cw+w[i]<=c){//搜索左子樹

x[i]=1;cw+=w[i];

backtrack(i+1);cw-=w[i];}

if(cw+r>bestw){x[i]=0;//搜索右子樹

backtrack(i+1);}r+=w[i];}10批處理作業(yè)調(diào)度給定n個作業(yè)的集合{J1,J2,…,Jn}。每個作業(yè)必須先由機器1處理，然后由機器2處理。作業(yè)Ji需要機器j的處理時間為tji。對于一個確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機器j上完成處理的時間。所有作業(yè)在機器2上完成處理的時間和稱為該作業(yè)調(diào)度的完成時間和。批處理作業(yè)調(diào)度問題要求對于給定的n個作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時間和達到最小。tji機器1機器2作業(yè)121作業(yè)231作業(yè)323這3個作業(yè)的6種可能的調(diào)度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應(yīng)的完成時間和分別是19，18，20，21，19，19。易見，最佳調(diào)度方案是1,3,2，其完成時間和為18。11解空間：排列樹從n個作業(yè)的所有排列中找出具有最小完成時間和的作業(yè)調(diào)度。設(shè)開始時x=[1,..,n]是所給的n個作業(yè)，則相應(yīng)的排列樹由所有排列構(gòu)成。12voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}classFlowshop{friendFlow(int**,int,int[]);private:voidBacktrack(inti);int**M,//各作業(yè)所需的處理時間*x,//當前作業(yè)調(diào)度*bestx,//當前最優(yōu)作業(yè)調(diào)度*f2,//機器2完成處理時間

f1,//機器1完成處理時間

f,//完成時間和

bestf,//當前最優(yōu)值

n;//作業(yè)數(shù)};13最大團問題給定無向圖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的更大的空子圖中。G的最大獨立集是G中所含頂點數(shù)最多的獨立集。對于任一無向圖G=(V，E)其補圖G=(V1，E1)定義為：V1=V，且(u，v)E1當且僅當(u，v)E。U是G的最大團當且僅當U是G的最大獨立集。124531245314解空間：子集樹可行性約束函數(shù)：頂點i到已選入的頂點集中每一個頂點都有邊相連。上界函數(shù)：有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。15voidClique::Backtrack(inti){//計算最大團

if(i>n){//到達葉結(jié)點

for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//檢查頂點i與當前團的連接

intOK=1;for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i與j不相連

OK=0;break;}if(OK){//進入左子樹

x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//進入右子樹

x[i]=0;Backtrack(i+1);}}最大團問題的回溯算法backtrack所需的計算時間顯然為O(n2n)。1245316選擇合適的搜索順序，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點按度從小到大排序。這在某種意義上相當于給回溯法加入了啟發(fā)性。定義Si={vi,vi+1,...,vn}，依次求出Sn,Sn-1,...,S1的解。從而得到一個更精確的上界函數(shù)，若cn+Si<=max則剪枝。同時注意到：從Si+1到Si，如果找到一個更大的團，那么vi必然屬于找到的團，此時有Si=Si+1+1，否則Si=Si+1。因此只要max的值被更新過，就可以確定已經(jīng)找到最大值，不必再往下搜索了17圖的m著色給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。18解空間：完全m叉樹例如一個3著色問題，n元組(c1,c2,...,cn),ci={1,2,3}。其解空間為一棵完全三叉樹，3n個可能的著色（葉結(jié)點）約束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復無限界函數(shù)，因為該問題是判定性問題，不是最優(yōu)化問題19voidColor::Backtrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk){//檢查顏色可用性

for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}圖m可著色問題的解空間樹中內(nèi)結(jié)點個數(shù)是對于每一個內(nèi)結(jié)點，在最壞情況下，用ok檢查當前擴展結(jié)點的每一個兒子所相應(yīng)的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是20旅行售貨員問題

(TravellingSalesmanProblem某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費），他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程（或旅費）最小。設(shè)G=(V,E)是一個帶權(quán)圖，圖中各邊的費用為一正數(shù)。圖中的一條周游路線是包括V中的每個頂點在內(nèi)的一條回路。一條周游路線的費用是這條路線上所有邊的費用之和。TSP問題就是要在圖G中找出一條有最小費用的周游路線。123430620105421排列樹1，2，…，n的排列由x[1:n]的所有排列構(gòu)成當i=n時，即當前擴展結(jié)點是葉結(jié)點的父結(jié)點時檢測是否存在一條從x[n-1]到x[n]的邊和一條從x[n]到x[1]的邊，如果都存在則判斷該回路的費用是否優(yōu)于當前最優(yōu)回路的費用，如果是則更新當前最優(yōu)值和最優(yōu)解。當i<n時，即當前擴展結(jié)點位于第i-1層時若存在從x[i-1]到x[i]的邊，則x[1:i]構(gòu)成一條路徑，且當x[1:i]的費用小于當前最優(yōu)值時進入第i層，否則剪去響應(yīng)的子樹。22template<classType>voidTraveling<Type>::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j<=n;j++)//是否可進入x[j]子樹?if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[i]]<bestc||bestc==NoEdge)){//搜索子樹

Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];Backtrack(i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}算法backtrack在最壞情況下可能需要更新當前最優(yōu)解O((n-1)!)次，每次更新bestx需計算時間O(n)，從而整個算法的計算時間復雜性為O(n!)。23連續(xù)郵資問題假設(shè)某國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對于給定的n和m的值，給出郵票面值的最佳設(shè)計，使得可在1張信封上貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。例如，當n=2和m=3時，如果面值分別為1、4，則所能得到的最大連續(xù)郵資區(qū)間為1-6；如果面值分別為1、3，則所能得到的最大連續(xù)郵資區(qū)間為1-7。再如，當n=5和m=4時，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)區(qū)間是1到70。011:1~32342:4~63:4~74:4~624用n元組x[1:n]表示n種不同的郵票面值，并約定它們從小到