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

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

backtrack(t+1);//對(duì)相應(yīng)的子樹(shù)進(jìn)行搜索}}12迭代回溯采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過(guò)程。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é)點(diǎn)處是否已得到問(wèn)題的可行解

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

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

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

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

if(cw>bestw)bestw=cw;

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

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

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

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

if(cw>bestw)bestw=cw;

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

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

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

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

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

if(cw>bestw){for(j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}return;}

//搜索子樹(shù)r-=w[i];

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

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

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

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

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

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

else

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

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

f,//完成時(shí)間和

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

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

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

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

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

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

QQQQ25解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：1)不同列：xixj2)不處于同一正、反對(duì)角線(xiàn)：|i-j||xi-xj|n后問(wè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層子樹(shù)

if(t>n)sum++;//到達(dá)葉子結(jié)點(diǎn)，方案增加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剪枝過(guò)程270-1背包問(wèn)題解空間：子集樹(shù)可行性約束函數(shù)：上界函數(shù)：例：n=4，c=7，p=[9,10,7,4]，w=[3,5,2,1]。分析：?jiǎn)挝恢亓績(jī)r(jià)值為[3,2,3.5,4]。先裝入4，再裝入3和1，剩余容量為1，只能裝入0.2的物品2。得到解x=[1,0.2,1,1]，最優(yōu)價(jià)值=22。雖不可行，但22為最優(yōu)值的上界。設(shè)r是當(dāng)前剩余物品價(jià)值的總和，cp是當(dāng)前價(jià)值，bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+r<=bestp時(shí)，可以剪去右子樹(shù)。

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

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

doublebound=cp;//以物品單位重量?jī)r(jià)值遞減序裝入物品

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

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

returnbound;}

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

if(i>n){//到葉子結(jié)點(diǎn)bestp＝cp;//當(dāng)前價(jià)值＝最優(yōu)價(jià)值return;}//搜索子樹(shù)if(cw+w[i]<=c){//進(jìn)入左子樹(shù)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)入右子樹(shù)}

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

例：下圖為一個(gè)有5個(gè)區(qū)域的地圖及其相應(yīng)的平面圖。這個(gè)地圖需要四種顏色來(lái)著色。圖：地圖和相應(yīng)的平面圖32圖的m著色問(wèn)題問(wèn)題描述：設(shè)無(wú)向連通圖G=(V,E)和m種顏色；如果這個(gè)圖G不是m可著色的，給出否定回答。如果這個(gè)圖可以m著色，找出不同的著色法。分析：用圖的鄰接矩陣a表示無(wú)向連通圖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）；頂點(diǎn)i所著顏色用x[i]表示（例：x[1]=1，x[2]=2，x[3]=3，x[4]=4，x[5]=1

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

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

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

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

for(intj=1;j<=