算法設(shè)計與分析

1第5章回溯法學(xué)習(xí)要點理解回溯法的深度優(yōu)先策略掌握用回溯法解題的算法框架子集樹算法框架排列樹算法框架通過范例學(xué)習(xí)回溯法的設(shè)計策略裝載問題，符號三角形，n后問題，0－1背包問題，圖著色問題23問題的解空間應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個最優(yōu)解。問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。例：n=3時的0-1背包問題用完全二叉樹表示的解空間4回溯法有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一結(jié)點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。圖：深度優(yōu)先搜索5狀態(tài)空間相關(guān)概念問題狀態(tài)：樹中的每一個結(jié)點確定所求解問題的一個問題狀態(tài)。狀態(tài)空間：由根結(jié)點到其他結(jié)點的所有路徑確定了這個問題的狀態(tài)空間。擴(kuò)展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴(kuò)展結(jié)點?；罱Y(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點。死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點。例：n=3時的0-1背包問題用完全二叉樹表示的狀態(tài)空間樹問題的解狀態(tài)結(jié)點問題的狀態(tài)結(jié)點6回溯法深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴(kuò)展結(jié)點F，一旦產(chǎn)生了它的一個兒子S，就把S當(dāng)做新的擴(kuò)展結(jié)點。在完成對子樹S（以S為根的子樹）的窮盡搜索之后，將F重新變成擴(kuò)展結(jié)點，繼續(xù)生成F的下一個兒子（如果存在）。寬度優(yōu)先的問題狀態(tài)生成法：在一個擴(kuò)展結(jié)點變成死結(jié)點之前，它一直是擴(kuò)展結(jié)點。回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先問題狀態(tài)生成法稱為回溯法。FS7回溯法的基本問題在解空間中，問題的求解就是搜索。搜索的基本問題是：（1）搜索過程是否一定能找到一個解；（2）搜索過程是否能終止運行或是會陷入一個死循環(huán)；（3）當(dāng)搜索過程找到解時，找到的是否是最佳解；（4）搜索過程的時間與空間復(fù)雜性如何。8回溯法的基本思想回溯法的基本步驟：(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：(1)用約束函數(shù)在擴(kuò)展結(jié)點處剪去不滿足約束的子樹；(2)用限界函數(shù)剪去得不到最優(yōu)解的子樹。0-1背包問題例：n=3,C=30,w={16,15,15},v={45,25,25}擴(kuò)展A，先到達(dá)B結(jié)點Cr=Cr-w1=14，V=V+v1=45此時A、B為活結(jié)點，B成為當(dāng)前擴(kuò)展結(jié)點擴(kuò)展B，先到達(dá)DCr<w2，D導(dǎo)致一個不可行解，回溯到B再擴(kuò)展B到達(dá)EE可行，此時A、B、E是活結(jié)點，E成為新的擴(kuò)展結(jié)點擴(kuò)展E，先到達(dá)JCr<w3，J導(dǎo)致一個不可行解，回溯到E再次擴(kuò)展E到達(dá)K由于K是葉結(jié)點，即得到一個可行解x=(1,0,0)，V=45K不可擴(kuò)展，成為死結(jié)點，返回到EE沒有可擴(kuò)展結(jié)點，成為死結(jié)點，返回到BB沒有可擴(kuò)展結(jié)點，成為死結(jié)點，返回到AA再次成為擴(kuò)展結(jié)點，擴(kuò)展A到達(dá)CCr=30，V=0，活結(jié)點為A、C，C為當(dāng)前擴(kuò)展結(jié)點擴(kuò)展C，先到達(dá)FCr=Cr-w2=15，V=V+v2=25，此時活結(jié)點為A、C、F，F(xiàn)成為當(dāng)前擴(kuò)展結(jié)點擴(kuò)展F，先到達(dá)LCr=Cr-w3=0，V=V+v3=50L是葉結(jié)點，且50>45，皆得到一個可行解x=(0,1,1)，V=50L不可擴(kuò)展，成為死結(jié)點，返回到F9再擴(kuò)展F到達(dá)MM是葉結(jié)點，且25<50，不是最優(yōu)解，M不可擴(kuò)展，成為死結(jié)點，返回到FF沒有可擴(kuò)展結(jié)點，成為死結(jié)點，返回到C再擴(kuò)展C到達(dá)GCr=30，V=0，活結(jié)點為A、C、G，G為當(dāng)前擴(kuò)展結(jié)點擴(kuò)展G，先到達(dá)N，N是葉結(jié)點，且25<50，不是最優(yōu)解，又N不可擴(kuò)展，返回到G再擴(kuò)展G到達(dá)O，O是葉結(jié)點，且0<50，不是最優(yōu)解，又O不可擴(kuò)展，返回到GG沒有可擴(kuò)展結(jié)點，成為死結(jié)點，返回到CC沒有可擴(kuò)展結(jié)點，成為死結(jié)點，返回到AA沒有可擴(kuò)展結(jié)點，成為死結(jié)點，算法結(jié)束，最優(yōu)解X=(0,1,1)，最優(yōu)值V=50。旅行售貨員問題問題描述：某售貨員要到若干城市去推銷商品，一直各城市之間的路程，他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到住地的路線，使總的路程最短。該問題是一個NP完全問題，有(n-1)!條可選路線。最優(yōu)解(1,3,2,4,1)，最優(yōu)值是25。1011遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。voidbacktrack(intt)//t表示當(dāng)前擴(kuò)展結(jié)點在解空間樹中的深度{if(t>n)output(x);//已經(jīng)搜索至葉子結(jié)點，輸出可行解x

elsefor(inti=f(n,t);i<=g(n,t);i++){//f(n,t)和g(n,t)表示當(dāng)前擴(kuò)展結(jié)點處未搜索過的子樹的起始和終止編號x[t]=h(i);//h(i)表示當(dāng)前擴(kuò)展結(jié)點處x[t]的第i個可選值if(constraint(t)&&bound(t))//constraint(t)和bound(t)表示當(dāng)前擴(kuò)展結(jié)點處的約束函數(shù)和限界函數(shù)

backtrack(t+1);//對相應(yīng)的子樹進(jìn)行搜索}}12迭代回溯采用樹的非遞歸深度優(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))//solution(t)判斷在當(dāng)前擴(kuò)展結(jié)點處是否已得到問題的可行解

output(x);//當(dāng)前擴(kuò)展結(jié)點處x[1:t]是問題的可行解，輸出可行解x

elset++;//當(dāng)前擴(kuò)展結(jié)點處x[1:t]只是問題的部分解，縱深繼續(xù)搜索}}

elset--;//約束函數(shù)和限界函數(shù)都不滿足則回溯}}13子集樹與排列樹算法框架遍歷子集樹需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]);}}0-1背包問題旅行售貨員問題14裝載問題問題描述：有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近c1。由此可知，裝載問題等價于以下特殊的0-1背包問題。用回溯法設(shè)計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法（O(min{c1，2n})）。15裝載問題解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：當(dāng)前載重量cw，當(dāng)前最優(yōu)載重量bestw,集裝箱重量數(shù)組為w[]privatestaticvoidbacktrack(inti){//搜索第i層結(jié)點

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

if(cw>bestw)bestw=cw;

//更新最優(yōu)解bestw;return;}if(cw+w[i]<=c){//搜索左子樹,x[i]=1cw+=w[i];

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

backtrack(i+1);//搜索右子樹}時間復(fù)雜性：O(2n)，空間復(fù)雜性：O(n)16裝載問題解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：剪枝當(dāng)前載重量cw+剩余集裝箱的重量r當(dāng)前最優(yōu)載重量bestwprivatestaticvoidbacktrack(inti){//搜索第i層結(jié)點

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

if(cw>bestw)bestw=cw;

//更新最優(yōu)解bestw;return;}//搜索子樹r-=w[i];

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

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

if(cw+r>bestw){//搜索右子樹backtrack(i+1);}r+=w[i];}時間復(fù)雜性：O(2n)17裝載問題構(gòu)造最優(yōu)解：x紀(jì)錄從根到當(dāng)前結(jié)點的路徑，bestx紀(jì)錄當(dāng)前最優(yōu)解privatestaticvoidbacktrack(inti){//搜索第i層結(jié)點

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

if(cw>bestw){for(j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}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];}裝載問題的非遞歸回溯算法見書本p12518批處理作業(yè)調(diào)度問題描述：給定n個作業(yè)的集合{J1,J2,…,Jn}。每個作業(yè)必須先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時間為tji。對于一個確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時間。所有作業(yè)在機(jī)器2上完成處理的時間和稱為該作業(yè)調(diào)度的完成時間和。批處理作業(yè)調(diào)度問題要求對于給定的n個作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時間和達(dá)到最小。tji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323作業(yè)1作業(yè)2作業(yè)3完成時間和：F21+F22+F23=3+6+10=1919批處理作業(yè)調(diào)度tji機(jī)器1機(jī)器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。作業(yè)1作業(yè)3作業(yè)2完成時間和：F21+F23+F22=3+7+8=18批處理作業(yè)調(diào)度排列樹20批處理作業(yè)調(diào)度解空間：排列樹privatestaticvoidbacktrack(inti)//第i層{if(i>n){//搜索至葉子結(jié)點

for(intj=1;j<=n;j++)bestx[j]=x[j];//第j個調(diào)度作業(yè)序號x[j]值賦給當(dāng)前最佳作業(yè)調(diào)度bestx[j]；bestf=f；//bestf為當(dāng)前最小完成時間和}

else

for(intj=i;j<=n;j++){//j從i到n遍歷f1+=m[x[j]][1];//當(dāng)前作業(yè)x[j]在機(jī)器M1上完成處理的時間f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];//M2上的完成處理時間(i層作業(yè))=max{f1，i-1層作業(yè)在M2的處理時間}+當(dāng)前作業(yè)x[j]在M2上的處理時間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];}}publicclassFlowShop//記錄結(jié)點信息staticintn,//作業(yè)數(shù)

f1,//機(jī)器1完成處理時間

f,//完成時間和

bestf;//當(dāng)前最優(yōu)值

staticint[][]m;//各作業(yè)所需的處理時間

staticint[]x;//當(dāng)前作業(yè)調(diào)度

staticint[]bestx;//當(dāng)前最優(yōu)作業(yè)調(diào)度

staticint[]f2;//機(jī)器2完成處理時間21約束函數(shù)顯約束：對解向量中分量xi的取值限定。裝載問題的顯約束：隱約束：？？？隱約束：為滿足問題的解而對不同分量xi之間施加的約束。22n后問題問題描述：在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ23n后問題分析1234567812345678QQQQQQQQ例：n=8八皇后問題解向量：（x1，x2，……xn）n元組，x[i]表示皇后i放在棋盤的第i行的第x[i]列。顯約束：x[i]取值范圍為1,2,3……n。隱約束：隱約束轉(zhuǎn)化為顯約束：1.n*n格棋盤看做是二維方陣，行號從上向往下，列號從左往右編號為1,2,3…n。2.左上角到右下角的主對角線及其平行線（斜率為-1）上，“行號-列號”的值相等。3.左下角到右上角的主對角線及其平行線（斜率為+1）上，“行號+列號”的值相等。4.若有兩個皇后，（i，j）和（k，l）表示其位置，若i-j=k-l或者i+j=k+l，則說明兩個皇后處于同一斜線上。即若i-k=j-l和i-k=l-j（|i-k|=|j-l|成立），表明兩個皇后位于同一斜線上。1)不同列：x［i］x［j］；2)不處于同一正、反對角線。24n后問題分析

回溯法分析：首先把第一個皇后放到棋盤上，由于第一個皇后有n列可以放，因此可擴(kuò)展出n種情況，先選其中一列放下這個皇后。然后開始放第二個皇后。同樣，第二個皇后也有n列可以放，因此也能擴(kuò)展出n種情況，但是第二個皇后可能會和第一個皇后發(fā)生攻擊，而一旦攻擊就不必要往下擴(kuò)展第三個皇后；若沒有發(fā)生攻擊，則繼續(xù)放第三個皇后。以此類推，直到n個皇后全部都放下后，即得到一組可行的解。擴(kuò)展全部完成后，就得到了結(jié)果。12341234

QQQQ25解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：1)不同列：xixj2)不處于同一正、反對角線：|i-j||xi-xj|n后問題

privatestaticbooleanplace(intk){//判斷是否與當(dāng)前皇后沖突

for(intj=1;j<k;j++)

if((Math.abs(k-j)==Math.abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;

returntrue;}privatestaticvoidbacktrack(intt){//搜索第t層子樹

if(t>n)sum++;//到達(dá)葉子結(jié)點，方案增加1。

elsefor(inti=1;i<=n;i++){x[t]=i;//列的取值有1到n種情況

if(place(t))backtrack(t+1);//不與當(dāng)前沖突，深入下一層，繼續(xù)}}12341234

QQQQ26例n＝4剪枝過程270-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：例：n=4，c=7，p=[9,10,7,4]，w=[3,5,2,1]。分析：單位重量價值為[3,2,3.5,4]。先裝入4，再裝入3和1，剩余容量為1，只能裝入0.2的物品2。得到解x=[1,0.2,1,1]，最優(yōu)價值=22。雖不可行，但22為最優(yōu)值的上界。設(shè)r是當(dāng)前剩余物品價值的總和，cp是當(dāng)前價值，bestp是當(dāng)前最優(yōu)價值。當(dāng)cp+r<=bestp時，可以剪去右子樹。

思路：將剩余物品按照其單位重量價值從高到低排序，然后依次裝入，直到裝不下，再裝入該物品的一部分而裝滿，因此得到的價值就是右子樹的上界。上界函數(shù)：更優(yōu)化的？280-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：privatestaticdoublebound(inti){//計算上界

doublecleft=c-cw;//剩余容量

doublebound=cp;//以物品單位重量價值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];bound+=p[i];//p[i]為物品i的價值i++;}//裝滿背包

if(i<=n)bound+=p[i]/w[i]*cleft;

returnbound;}

注：bound計算當(dāng)前結(jié)點處的上界，以判斷是否將右子樹剪去，進(jìn)入左子樹不需要計算上界，其上界與父結(jié)點相同。290-1背包問題解空間：子集樹可行性約束函數(shù)：上界函數(shù)：bound(inti)遞歸搜索：Privatestaticvoidbacktrack（inti）｛

if(i>n){//到葉子結(jié)點bestp＝cp;//當(dāng)前價值＝最優(yōu)價值return;}//搜索子樹if(cw+w[i]<=c){//進(jìn)入左子樹cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(bound(i+1)>bestp)backtrack(i+1);//進(jìn)入右子樹}

復(fù)雜度分析計算上界需要O(n)時間，最壞情況下O()個右兒子結(jié)點需要計算上界，因此算法backtrack需要的計算時間是O(n).30圖的m著色問題圖的m可著色判定問題：給定無向連通圖G=(E,V)和m種不同的顏色。用這m種顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。圖的m可著色優(yōu)化問題：若一個圖最少需要m種顏色才能使圖G中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。圖：地圖和相應(yīng)的平面圖31圖的m著色問題四色猜想：在一個平面或者球面上的任何地圖能夠只用四種顏色來著色，使得相鄰的國家在地圖上著不同顏色。假設(shè)每個國家在地圖上是單連通域；假設(shè)2個國家相鄰是指這2個國家有一段長度不為0的公共邊界，不僅僅是有一個公共點，這樣的地圖容易用平面圖表示。地圖上的每個區(qū)域相應(yīng)于平面圖中一個頂點，2個區(qū)域在地圖上相鄰，在平面圖中相應(yīng)的2個頂點之間有一條邊相鄰。

例：下圖為一個有5個區(qū)域的地圖及其相應(yīng)的平面圖。這個地圖需要四種顏色來著色。圖：地圖和相應(yīng)的平面圖32圖的m著色問題問題描述：設(shè)無向連通圖G=(V,E)和m種顏色；如果這個圖G不是m可著色的，給出否定回答。如果這個圖可以m著色，找出不同的著色法。分析：用圖的鄰接矩陣a表示無向連通圖G。若(i,j)屬于圖G的邊集E，則a[i][j]=1，否則a[i][j]=0（例：

a[1][2]=1，a[1][5]=0）；整數(shù)1,2，…m表示m種不同顏色（例：黃=1，綠=2，紫=3，紅=4）；頂點i所著顏色用x[i]表示（例：x[1]=1，x[2]=2，x[3]=3，x[4]=4，x[5]=1

）。圖：地圖和相應(yīng)的平面圖33圖的m著色問題問題描述：設(shè)無向連通圖G=(V,E)和m種顏色；如果這個圖G不是m可著色的，給出否定回答。如果這個圖可以m著色，找出不同的著色法。解向量：(x1,x2,…,xn)表示頂點i所著顏色x[i]。解空間：高為n+1的完全m叉樹。解空間樹的第i層中每一個結(jié)點都有m個兒子；每個兒子相應(yīng)于x[i]的m個可能的著色之一。圖：n=3，m=3問題的解空間樹例：下圖為n=3，m=3的問題的解空間樹。黃=1，綠=2，紫=334解向量：(x1,x2,…,xn)表示頂點i所著顏色x[i]?？尚行约s束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復(fù)。圖的m著色問題privatestaticvoidbacktrack(intt){//搜索第t層子樹

if(t>n)sum++;//搜索至葉子結(jié)點，得到m著色方案，sum為著色方案數(shù)

elsefor(inti=1;i<=m;i++){x[t]=i;//當(dāng)前擴(kuò)展結(jié)點有m個兒子結(jié)點

if(ok(t))backtrack(t+1);//對每個兒子進(jìn)行ok剪枝，可行則深入子樹搜索}}privatestaticbooleanok(intk){//檢查顏色可用性

for(intj=1;j<=