第5章回溯法第1頁回溯法學(xué)習(xí)重點(diǎn)理解回溯法深度優(yōu)先搜索策略掌握用回溯法解題算法框架（1）遞歸回溯（2）迭代回溯（3）子集樹算法框架（4）排列樹算法框架通過應(yīng)用范例學(xué)習(xí)回溯法設(shè)計(jì)策略（1）裝載問題（2）批處理作業(yè)調(diào)度（3）符號(hào)三角形問題（4）n后問題（5）0-1背包問題（6）最大團(tuán)問題（7）圖m著色問題（8）旅行售貨員問題（9）圓排列問題（10）電路板排列問題（11）連續(xù)郵資問題第2頁回溯法有許多問題，當(dāng)需要找出它解集或者要求回答什么解是滿足某些約束條件最佳解時(shí)，往往要使用回溯法?；厮莘ɑ咀龇ㄊ撬阉?，或是一種組織得井井有條，能避免無須要搜索窮舉式搜索法。這種辦法適用于解某些組合數(shù)相稱大問題?；厮莘ㄔ趩栴}解空間樹中，按深度優(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頁問題解空間問題解向量：回溯法希望一種問題解能夠表達(dá)成一種n元式(x1,x2,…,xn)形式。顯約束：對(duì)分量xi取值限定。隱約束：為滿足問題解而對(duì)不一樣分量之間施加約束。解空間：對(duì)于問題一種實(shí)例，解向量滿足顯式約束條件所有多元組，組成了該實(shí)例一種解空間。注意：同一種問題能夠有多種表達(dá)，有些表達(dá)辦法更簡(jiǎn)單，所需表達(dá)狀態(tài)空間更?。ù娣帕可伲阉鬓k法簡(jiǎn)單）。n=3時(shí)0-1背包問題用完全二叉樹表達(dá)解空間第4頁生成問題狀態(tài)基本辦法擴(kuò)展結(jié)點(diǎn):一種正在產(chǎn)生兒子結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn):一種本身已生成但其兒子還沒有所有生成節(jié)點(diǎn)稱做活結(jié)點(diǎn)死結(jié)點(diǎn):一種所有兒子已經(jīng)產(chǎn)生結(jié)點(diǎn)稱做死結(jié)點(diǎn)深度優(yōu)先問題狀態(tài)生成法：假如對(duì)一種擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它一種兒子C，就把C當(dāng)做新擴(kuò)展結(jié)點(diǎn)。在完成對(duì)子樹C（以C為根子樹）窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R下一種兒子（假如存在）寬度優(yōu)先問題狀態(tài)生成法：在一種擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它始終是擴(kuò)展結(jié)點(diǎn)回溯法：為了避免生成那些不也許產(chǎn)生最佳解問題狀態(tài)，要不停地利用限界函數(shù)(boundingfunction)來處死那些事實(shí)上不也許產(chǎn)生所需解活結(jié)點(diǎn)，以減少問題計(jì)算量。具有限界函數(shù)深度優(yōu)先生成法稱為回溯法第5頁回溯法基本思想(1)針對(duì)所給問題，定義問題解空間；(2)確定易于搜索解空間構(gòu)造；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束子樹；用限界函數(shù)剪去得不到最優(yōu)解子樹。用回溯法解題一種顯著特性是在搜索過程中動(dòng)態(tài)產(chǎn)生問題解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到目前擴(kuò)展結(jié)點(diǎn)途徑。假如解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)最長途徑長度為h(n)，則回溯法所需計(jì)算空間一般為O(h(n))。而顯式地存放整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。第6頁遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸辦法實(shí)現(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);}}第7頁迭代回溯采取樹非遞歸深度優(yōu)先遍歷算法，可將回溯法表達(dá)為一種非遞歸迭代過程。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--;}}第8頁子集樹與排列樹遍歷子集樹需O(2n)計(jì)算時(shí)間

遍歷排列樹需要O(n!)計(jì)算時(shí)間

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]);}}第9頁裝載問題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2輪船，其中集裝箱i重量為wi，且裝載問題要求確定是否有一種合理裝載方案可將這個(gè)集裝箱裝上這2艘輪船。假如有，找出一種裝載方案。容易證明，假如一種給定裝載問題有解，則采取下面策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡也許裝滿；(2)將剩下集裝箱裝上第二艘輪船。將第一艘輪船盡也許裝滿等價(jià)于選用全體集裝箱一種子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價(jià)于下列特殊0-1背包問題。用回溯法設(shè)計(jì)解裝載問題O(2n)計(jì)算時(shí)間算法。在某些情況下該算法優(yōu)于動(dòng)態(tài)規(guī)劃算法。第10頁裝載問題解空間：子集樹可行性約束函數(shù)(選擇目前元素)：上界函數(shù)(不選擇目前元素)：目前載重量cw+剩下集裝箱重量r

目前最優(yōu)載重量bestwprivatestaticvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)if(i>n)//達(dá)到葉結(jié)點(diǎn)更新最優(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];}第11頁批處理作業(yè)調(diào)度給定n個(gè)作業(yè)集合{J1,J2,…,Jn}。每個(gè)作業(yè)先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j處理時(shí)間為tji。對(duì)于一種確定作業(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á)成最小。tji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323這3個(gè)作業(yè)6種也許調(diào)度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所對(duì)應(yīng)完成時(shí)間和分別是19，18，20，21，19，19。易見，最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。第12頁批處理作業(yè)調(diào)度解空間：排列樹privatestaticvoidbacktrack(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){MyMath.swap(x,i,j);backtrack(i+1);MyMath.swap(x,i,j);}f1-=m[x[j]][1];f-=f2[i];}}publicclassFlowShopstaticintn,//作業(yè)數(shù)f1,//機(jī)器1完成處理時(shí)間f,//完成時(shí)間和bestf;//目前最優(yōu)值staticint[][]m;//各作業(yè)所需處理時(shí)間staticint[]x;//目前作業(yè)調(diào)度staticint[]bestx;//目前最優(yōu)作業(yè)調(diào)度staticint[]f2;//機(jī)器2完成處理時(shí)間第13頁符號(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ù)相同。第14頁符號(hào)三角形問題解向量：用n元組x[1:n]表達(dá)符號(hào)三角形第一行?？尚行约s束函數(shù)：目前符號(hào)三角形所包括“+”個(gè)數(shù)與“-”個(gè)數(shù)均不超出n*(n+1)/4無解判斷：n*(n+1)/2為奇數(shù)voidTriangle::Backtrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}Backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}++-+-+++----+-+++--++--+---+復(fù)雜度分析計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有O(2n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號(hào)三角形問題回溯算法所需計(jì)算時(shí)間為O(n2n)。第15頁n后問題在n×n格棋盤上放置彼此不受襲擊n個(gè)皇后。按照國際象棋規(guī)則，皇后能夠襲擊與之處于同一行或同一列或同一斜線上棋子。n后問題等價(jià)于在n×n格棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ第16頁解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：1)不一樣列：xi

xj2)不處于同一正、反對(duì)角線：|i-j|

|xi-xj|n后問題boolQueen::Place(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}第17頁0-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//計(jì)算上界Typewcleft=c-cw;//剩下容量Typepb=cp;

//以物品單位重量價(jià)值遞減序裝入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}

//裝滿背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}第18頁最大團(tuán)問題給定無向圖G=(V，E)。假如U

V，且對(duì)任意u，v

U有(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)。假如U

V且對(duì)任意u，v

U有(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ú)立集。1245312453第19頁最大團(tuán)問題解空間：子集樹可行性約束函數(shù)：頂點(diǎn)i到已選入頂點(diǎn)集中每一種頂點(diǎn)都有邊相連。上界函數(shù)：有足夠多可選擇頂點(diǎn)使得算法有也許在右子樹中找到更大團(tuán)。voidClique::Backtrack(inti){//計(jì)算最大團(tuán)if(i>n){//達(dá)到葉結(jié)點(diǎn)for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//檢查頂點(diǎn)i與目前團(tuán)連接intOK=1;for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i與j不相連OK=0;break;}if(OK){//進(jìn)入左子樹x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//進(jìn)入右子樹x[i]=0;Backtrack(i+1);}}復(fù)雜度分析最大團(tuán)問題回溯算法backtrack所需計(jì)算時(shí)間顯然為O(n2n)。12453第20頁深入改善選擇合適搜索次序，能夠使得上界函數(shù)更有效發(fā)揮作用。例如在搜索之前能夠?qū)㈨旤c(diǎn)按度從小到大排序。這在某種意義上相稱于給回溯法加入了啟發(fā)性。定義Si={vi,vi+1,...,vn}，依次求出Sn,Sn-1,...,S1解。從而得到一種更精確上界函數(shù)，若cn+Si<=max則剪枝。同步注意到：從Si+1到Si，假如找到一種更大團(tuán)，那么vi必然屬于找到團(tuán)，此時(shí)有Si=Si+1+1，不然Si=Si+1。因此只要max值被更新過，就能夠確定已經(jīng)找到最大值，無須再往下搜索了。第21頁圖m著色問題給定無向連通圖G和m種不一樣顏色。用這些顏色為圖G各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊2個(gè)頂點(diǎn)著不一樣顏色。這個(gè)問題是圖m可著色判定問題。若一種圖最少需要m種顏色才能使圖中每條邊連接2個(gè)頂點(diǎn)著不一樣顏色，則稱這個(gè)數(shù)m為該圖色數(shù)。求一種圖色數(shù)m問題稱為圖m可著色優(yōu)化問題。第22頁解向量：(x1,x2,…,xn)表達(dá)頂點(diǎn)i所著顏色xi可行性約束函數(shù)：頂點(diǎn)i與已著色相鄰頂點(diǎn)顏色不反復(fù)。圖m著色問題voidColor::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;}復(fù)雜度分析圖m可著色問題解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是對(duì)于每一種內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查目前擴(kuò)展結(jié)點(diǎn)每一種兒子所對(duì)應(yīng)顏色可用性需耗時(shí)O(mn)。因此，回溯法總時(shí)間花費(fèi)是第23頁旅行售貨員問題解空間：排列樹template<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++)//是否可進(jìn)入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]);}}}復(fù)雜度分析算法backtrack在最壞情況下也許需要更新目前最優(yōu)解O((n-1)!)次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法計(jì)算時(shí)間復(fù)雜性為O(n!)。第24頁圓排列問題給定n個(gè)大小不等圓c1,c2,…,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一種矩形框中，且要求各圓與矩形框底邊相切。圓排列問題要求從n個(gè)圓所有排列中找出有最小長度圓排列。例如，當(dāng)n=3，且所給3個(gè)圓半徑分別為1，1，2時(shí)，這3個(gè)圓最小長度圓排列如圖所示。其最小長度為第25頁圓排列問題floatCircle::Center(intt){//計(jì)算目前所選擇圓圓心橫坐標(biāo)floattemp=0;for(intj=1;j<t;j++){floatvaluex=x[j]+2.0*sqrt(r[t]*r[j]);if(valuex>temp)temp=valuex;}returntemp;}voidCircle::Compute(void){//計(jì)算目前圓排列長度floatlow=0;high=0;for(inti=1;i<=n;i++){if(x[i]-r[i]<low)low=x[i]-r[i];if(x[i]+r[i]>high)high=x[i]+r[i];}if(high-low<min)min=high-low;}voidCircle::Backtrack(intt){if(t>n)Compute();elsefor(intj=t;j<=n;j++){Swap(r[t],r[j]);floatcenterx=Center(t);if(centerx+r[t]+r[1]<min){//下界約束x[t]=centerx;Backtrack(t+1);}Swap(r[t],r[j]);}}復(fù)雜度分析由于算法backtrack在最壞情況下也許需要計(jì)算O(n!)次目前圓排列長度，每次計(jì)算需O(n)計(jì)算時(shí)間，從而整個(gè)算法計(jì)算時(shí)間復(fù)雜性為O((n+1)!)上述算法尚有許多改善余地。例如，象1,2,…,n-1,n和n,n-1,…,2,1這種互為鏡像排列具有相同圓排列長度，只計(jì)算一種就夠了，可減少約二分之一計(jì)算量。另一方面，假如所給n個(gè)圓中有k個(gè)圓有相同半徑，則這k個(gè)圓產(chǎn)