算法分析與設(shè)計(jì)第5章課件

1第5章回溯法學(xué)習(xí)要點(diǎn)理解回溯法的深度優(yōu)先搜尋策略駕馭用回溯法解題的算法框架1）遞歸回溯2）迭代回溯3）子集樹算法框架4）排列樹算法框架通過應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計(jì)策略1）裝載問題；2）批處理作業(yè)調(diào)度；3）n后問題；4）0-1背包問題；5）最大團(tuán)問題；6）旅行售貨員問題2引言有很多問題，當(dāng)須要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要運(yùn)用回溯法?；厮莘ǖ幕咀龇ㄊ撬褜?，或是一種組織得井井有條的、能避開不必要搜尋的窮舉式搜尋法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)動身搜尋解空間樹。算法搜尋至解空間樹的隨意一點(diǎn)時(shí)，先推斷該結(jié)點(diǎn)是否包含問題的解：假如確定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜尋，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，接著按深度優(yōu)先策略搜尋。35.1回溯法的算法框架本節(jié)介紹回溯法算法框架的有關(guān)問題：一、問題的解空間二、回溯法的基本思想三、遞歸回溯四、迭代回溯五、子集樹與排列樹4一、問題的解空間應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個(gè)(最優(yōu))解。問題的解向量：回溯法希望一個(gè)問題的解能夠表示成一個(gè)n元式(x1,x2,…,xn)的形式。解空間：對于問題的一個(gè)實(shí)例，解向量滿足約束條件的全部多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。留意：同一個(gè)問題可以有多種表示，有些表示方法更簡潔，所需表示的狀態(tài)空間更?。ù鎯α可?，搜尋方法簡潔）。例如，對于有n種可選物品的0-1背包問題，其解空間由長度為n的0-1向量組成。n=3時(shí)的0-1背包問題用完全二叉樹表示的解空間5二、回溯法的基本思想回溯法的基本步驟：(1)針對所給問題，定義問題的解空間；(2)確定易于搜尋的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜尋解空間，并在搜尋過程中用剪枝函數(shù)避開無效搜尋。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。關(guān)于困難性：用回溯法解題的一個(gè)顯著特征是在搜尋過程中動態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。6生成問題狀態(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)生成法：假如對一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個(gè)兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對子樹C（以C為根的子樹）的窮盡搜尋之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，接著生成R的下一個(gè)兒子（假如存在）7示例10-1背包問題n=3,C=30,w={16,15,15},v={45,25,25}ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45CCr=30，V=0DCr<w2不可行解JCr<w3不可行解KCr=14V=45x=(1,0,0)HIECr=14V=45Lw3=15，v3=25Cr=0，V=5050>45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25<50不是最優(yōu)解8示例2旅行售貨員問題問題描述：某售貨員要到若干城市去推銷商品，已知各城市之間的路程，他要選定一條從駐地動身，經(jīng)過每個(gè)城市一遍，最終回到住地的路途，使總的路程最短。該問題是一個(gè)NP完全問題，有(n-1)!條可選路途最優(yōu)解(1,3,2,4,1)，最優(yōu)值251234206305410ABCDEFGHIJKLMNOPQ12343443423224239三、遞歸回溯回溯法對解空間作深度優(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);}}f(n,t)，g(n,t)：表示當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜尋過的子樹的起始編號和終止編號。10四、迭代回溯接受樹的非遞歸深度優(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--; } }11五、子集樹與排列樹子集樹需O(2n)計(jì)算時(shí)間

voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}排列樹需O(n!)計(jì)算時(shí)間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])}}125.2裝載問題一、問題描述二、問題分析三、算法設(shè)計(jì)四、算法描述13一、問題描述有一批共n個(gè)集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為wi，且∑wi≤C1+C2裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。假如有，找出一種裝載方案。簡潔證明，假如一個(gè)給定裝載問題有解，則接受下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上其次艘輪船。14二、問題分析將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價(jià)于以下特殊的0-1背包問題。15三、算法設(shè)計(jì)解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量CW+剩余集裝箱的重量R≤當(dāng)前最優(yōu)載重量BestW用回溯法設(shè)計(jì)解裝載問題的O(2n)計(jì)算時(shí)間算法。在某些狀況下該算法優(yōu)于動態(tài)規(guī)劃算法。16四、算法描述//搜尋第i層結(jié)點(diǎn)voidbacktrack(inti){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];}175.3批處理作業(yè)調(diào)度一、問題描述二、實(shí)例分析三、算法描述18一、問題描述給定n個(gè)作業(yè)的集合{J1,J2,…,Jn}。每個(gè)作業(yè)必需先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji須要機(jī)器j的處理時(shí)間為tji。對于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。全部作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問題要求對于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。19二、實(shí)例分析這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。20三、算法描述voidFlowshop::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];}}解空間：排列樹困難性：T(n)=O(n!)215.5n后問題一、問題描述二、問題分析三、算法描述22一、問題描述在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后。依據(jù)國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。23二、問題分析解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱隱束：1)不同列：xi≠xj2)不處于同一正、反對角線：|i-j|≠|(zhì)xi-xj|24三、算法描述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);}}5.60-1背包問題voidbacktrack(inti){if(i>n)//到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解bestx,bestp;return;r-=w[i];if(cw+w[i]<=c){//進(jìn)入左子樹x[i]=1;cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp){//進(jìn)入右子樹x[i]=0;backtrack(i+1);}}解空間：子集樹可行性約束函數(shù)：∑wixi≤C上界函數(shù)：Bound()算法：略26上界函數(shù)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;}27作業(yè)有一0-1背包問題實(shí)例，n=4,c=7,w=[3,5,2,1],P=[9,10,7,4],畫出這一實(shí)例由Knapsack算法實(shí)際生成的那部分狀態(tài)空間樹。并給出最優(yōu)解。285.7最大團(tuán)問題一、基本概念二、問題分析三、算法描述四、進(jìn)一步改進(jìn)29一、基本概念完全子圖：給定無向圖G=(V，E)。假如UV，且對隨意u，vU有(u，v)E，則稱U是G的完全子圖。團(tuán)：G的完全子圖U是G的團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團(tuán)：是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。123451234530二、問題分析解空間：子集樹可行性約束函數(shù)：頂點(diǎn)i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。上界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。困難度分析：最大團(tuán)問題的回溯算法backtrack所需的計(jì)算時(shí)間明顯為O(n2n)。31三、算法描述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;}

intOK=1;//檢查頂點(diǎn)i與當(dāng)前團(tuán)的連接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);}}32四、進(jìn)一步改進(jìn)選擇合適的搜尋依次，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜尋之前可以將頂點(diǎn)按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。335.8圖的m著色問題一、基本概念二、問題分析三、算法描述四、困難性分析34一、基本概念給定無向連通圖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的問題稱為圖的m可著色優(yōu)化問題。35二、問題分析解向量：(x1,x2,…,xn)表示頂點(diǎn)i所著顏色x[i]可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。36三、算法描述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;}37四、困難性分析圖m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是∑mi(0≤i≤n-1)。對于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞狀況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是∑mi(mn)=nm(mn-1)/(m-1)=O(nmn)(0≤i≤n-1)385.9旅行售貨員問題voidBacktrack(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{//是否可進(jìn)入x[j]子樹?for(intj=i;j<=n;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);