計(jì)算理論與算法分析設(shè)計(jì)：05-backtrack

搜索法

方法概述:搜索算法介紹搜索算法

(1)窮舉搜索(Exhaustive

Search)(2)盲目搜索(BlindSearch)-深度優(yōu)先(DFS)或回溯搜索

(Backtracking);-廣度優(yōu)先搜索(BFS);-分枝限界法(Branch&Bound);-博弈樹搜索(α-βSearch)(3)啟發(fā)式搜索(HeuristicSearch)-A*算法，B*，GA……2方法概述:搜索算法介紹（續(xù)）搜索空間的三種表示

-表序表示:搜索對(duì)象用線性表數(shù)據(jù)結(jié)構(gòu)表示;-顯式圖表示:搜索對(duì)象在搜索前就用圖(樹)的數(shù)據(jù)結(jié)構(gòu)表示;-隱式圖表示:除了初始結(jié)點(diǎn),其他結(jié)點(diǎn)在搜索過程中動(dòng)態(tài)生成.緣于搜索空間大,難以全部存儲(chǔ).3方法概述:搜索算法介紹（續(xù)）提高搜索效率的思考：隨機(jī)搜索

-上世紀(jì)70年代中期開始,國(guó)外一些學(xué)者致力于研究隨機(jī)搜索求解困難的組合問題,將隨機(jī)過程引入搜索;-選擇規(guī)則是隨機(jī)地從可選結(jié)點(diǎn)中取一個(gè),從而可以從統(tǒng)計(jì)角度分析搜索的平均性能;-隨機(jī)搜索的一個(gè)成功例子:n后問題.4組合爆炸一張充分大的普通紙對(duì)折40次：

高度超過5千座珠穆朗瑪峰一張充分大的普通紙對(duì)折50次：月地距離的128倍一個(gè)問題有n個(gè)變量,k個(gè)選擇,則遍歷空間的大小為kn并行處理也不可能克服和繞過組合爆炸；但并行處理可能是當(dāng)前提高求解規(guī)模的最好和現(xiàn)實(shí)的途徑。5世界紀(jì)錄:2^132011年，15名學(xué)生和教師利用長(zhǎng)度超過2英里=3218米的衛(wèi)生紙和MIT的無(wú)盡長(zhǎng)廊(無(wú)盡長(zhǎng)廊是連接MIT主建筑群的走廊，長(zhǎng)度為825英尺=251.46米，不用再擔(dān)心廁紙會(huì)被風(fēng)吹走)，創(chuàng)造了紙張連續(xù)對(duì)半折疊的新世界紀(jì)錄——13次，打破了2002年的舊記錄——12次。連續(xù)向同一方向?qū)φ?3次相當(dāng)于疊出8192（2^13）層。數(shù)學(xué)教師、廁紙折疊高手Tanton表示，這相當(dāng)于攀登珠穆朗瑪峰。6世界紀(jì)錄:2^137一、寬度優(yōu)先搜索法BreadthFirstSearch(BFS)寬度優(yōu)搜索法：逐層地對(duì)結(jié)點(diǎn)進(jìn)行擴(kuò)展。例：重排九宮問題：在3Х3的方格棋盤上放置分別標(biāo)有數(shù)字1，2，3，···，8的八張牌，初始狀態(tài)為S0，目標(biāo)狀態(tài)為St28314765S012384765St82834765S01283

1

4765223

8

47653283

476542836

4755832147652837

1465

23

8

476523

8

476528

43765283

4

576283

64

75283

6475678910111213832147652837

14651

23

8

4765234

876528

4

3765283

4

576283

641

75283

67541415218

32147658

13247652223283746

152837

146

52425123847651

2378

4652627StRoute:S0→3→8→16→26(St)9

優(yōu)點(diǎn)：只要問題有解，用寬度優(yōu)先搜索法一定可以得到解，而且得到的是路徑最短的解。缺點(diǎn)：盲目性較大。當(dāng)目標(biāo)結(jié)點(diǎn)距離初始結(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用結(jié)點(diǎn)，搜索效率低。10二、深度優(yōu)先搜索法DepthFirstSearch(DFS)深度優(yōu)搜索法：縱深地對(duì)結(jié)點(diǎn)進(jìn)行擴(kuò)展。11St2834765S01283

14765223

8476511283

4765283

6475832147652837

1465

23

8

476523

8

476528

43765283

4

576283

64

75283

64753713832147652837

14651

23

8

4765234

876528

4

3765283

4

576283

641

75283

6754488

32147658

132476556283746

152837

146

5910123847651

2378

4651412So:l→11→12→13→14:St12搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)結(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但如果目標(biāo)結(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無(wú)窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的。13（二）、有界深度優(yōu)先搜索法解決深度優(yōu)先搜索不完備的問題，引入搜索深度的界限（設(shè)為dm），當(dāng)搜索深度達(dá)到了深度界限，而尚未出現(xiàn)目標(biāo)結(jié)點(diǎn)，就換一個(gè)分支進(jìn)行搜索。14

1234515回溯法

回溯法既帶有系統(tǒng)性又帶有跳躍性的搜索算法。在包含問題所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(系統(tǒng)性)

算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，判斷該結(jié)點(diǎn)為根的子樹是否包含問題的解(跳躍性)如果肯定不包含，則跳過以該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。

這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。17問題的解空間18問題的解向量：回溯法希望一個(gè)問題的解能夠表示成一個(gè)n元式(x1,x2,…,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿足問題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。n=3時(shí)的0-1背包問題用完全二叉樹表示的解空間有三種結(jié)點(diǎn)：解空間樹：根結(jié)點(diǎn)（搜索的起點(diǎn)）中間結(jié)點(diǎn)（非終端結(jié)點(diǎn)）葉結(jié)點(diǎn)（終端結(jié)點(diǎn)），葉結(jié)點(diǎn)為解向量搜索過程就是找一個(gè)或一些特別的葉結(jié)點(diǎn)。19－從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以DFS搜索整個(gè)解空間。－開始結(jié)點(diǎn)成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處向縱深方向移至一個(gè)新結(jié)點(diǎn)，并成為一個(gè)新的活結(jié)點(diǎn)，也成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。－如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向擴(kuò)展，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。－此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)；直至找到一個(gè)解或全部解。方法概述20start??deadenddeadend??deadend?success!deadend算法的基本步驟1）針對(duì)問題，定義問題的解空間（對(duì)解進(jìn)行編碼）；2）確定易于搜索的解空間組織結(jié)構(gòu)（按樹或圖組織解）；3）以深度優(yōu)先方式搜索解空間，搜索過程中裁減掉死結(jié)點(diǎn)的子樹提高搜索效率。21常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。二類常見的解空間樹①子集樹：當(dāng)所給的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹葉結(jié)點(diǎn)數(shù)2n，總結(jié)點(diǎn)數(shù)2n+1，遍歷時(shí)間為Ω(2n)如0-1背包②排列樹：當(dāng)所給問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹葉結(jié)點(diǎn)數(shù)n!，遍歷時(shí)間為Ω(n!)如TSP問題方法概述22子集樹與排列樹0-1背包問題含有2n個(gè)葉結(jié)點(diǎn)旅行商問題含有(n-1)!個(gè)葉結(jié)點(diǎn)問：每個(gè)樹的葉結(jié)點(diǎn)數(shù)目是多少？23例[0-1背包]：n=3,w=(16,15,15),v=(45,25,25),c=30(1)定義解空間：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)}(2)構(gòu)造解空間樹：(1,1,1)AHIDJKEBLMFNOGC10101010101010(1,1,0)(1,0,1)(1,0,0)(0,1,1)(0,1,0)(0,0,1)(0,0,0)24n=3,w=(16,15,15),v=(45,25,25),c=30(3)從A出發(fā)按DFS搜索：AHIDJKEBLMFNOGC10101010101010455025250可行解:(1,0,0)(0,1,1)(0,1,0)(0,0,1)(0,0,0)殺死結(jié)點(diǎn)解值:最優(yōu)解L=(0,1,1),最優(yōu)值為5025(1)定義解空間：X={12341,12431,13241,13421,14231,14321}(2)構(gòu)造解空間樹：(3)從A出發(fā)按DFS搜索整棵樹：26例[TSP問題]：求從頂點(diǎn)1出發(fā)，最后回到頂點(diǎn)1的最短路線。最優(yōu)解：13241，14231成本：25用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。顯式地存儲(chǔ)整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間27回溯算法的一般框架子集樹回溯算法

voidBacktrack(intt)//搜索到樹的第t層

{//由第t層向第t+1層擴(kuò)展，確定x[t]的值if(t>n)output(x);//葉結(jié)點(diǎn)是可行解，輸出解

elsewhile(allXt){//Xt為當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有可能取值集合，例如0和1

x[t]=Xt中第i個(gè)值;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}執(zhí)行時(shí)：Backtrack(1)//從1擴(kuò)展并回溯28節(jié)點(diǎn)可行，則探索下一深度當(dāng)前節(jié)點(diǎn)取遍所有可能，即探索樹下一深度回溯算法的一般框架（續(xù)）排列樹回溯算法

voidBacktrack(intt)//搜索到樹的第t層

{//由第t層向第t+1層擴(kuò)展，確定x[t]的值if(t>n)output(x);//葉結(jié)點(diǎn)是可行解，輸出解

else//已經(jīng)探索到第t個(gè)元素，需要調(diào)整后面至n的元素排序fori=tton{//對(duì)后續(xù)節(jié)點(diǎn)，每個(gè)試一次swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);swap(x[t],x[i]);}}29恢復(fù)到初始排序，便于回溯針對(duì)第t個(gè)節(jié)點(diǎn)，依次將它與后繼所有節(jié)點(diǎn)進(jìn)行置換，即遍歷新次序是有價(jià)值的5.2裝載問題有一批共n個(gè)集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為wi，且∑wi≤C1+C2裝載問題要求確定是否有一個(gè)合理的裝載方案可將這些集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。如何利用貪心算法合理的裝載方案？n=3,C1=C2=50,w=[10,40,40]n=3,C1=C2=50,w=[20,40,40]30問題分析容易證明，如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。31將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近C1。由此可知，裝載問題等價(jià)于特殊的0-1背包問題。32解空間：子集樹對(duì)于當(dāng)前擴(kuò)展節(jié)點(diǎn)Z，對(duì)于箱子i，有x[i]=1：左子樹，代表選中x[i]=0：右子樹，代表不選可行性約束函數(shù)(選擇當(dāng)前元素)：記當(dāng)前載重量為cw若cw+w[i]<=c1，左子樹可選擇右子樹總是可以選，因?yàn)椴辉黾又亓?3限界函數(shù)：用于剪去不含最優(yōu)解的子樹，從而提高算法在平均情況下的運(yùn)行效率。設(shè)Z是解空間樹第i層上的當(dāng)前擴(kuò)展結(jié)點(diǎn)，cw是當(dāng)前載重量，R是剩余集裝箱的重量，besetW是當(dāng)前最優(yōu)載重量，則當(dāng)

cw+R≤bestW時(shí)，剪去Z的右子樹34裝載問題算法描述voidbacktrack(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];}35練習(xí):子集和問題問題給定由n個(gè)不同正整數(shù)組成的集合W={wi}，和正整數(shù)M，求W中所有和等于M的子集的集合。例如n=5,M=20,

W={8,4,9,7,3}

365.3批處理作業(yè)調(diào)度問題描述給定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í)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。37實(shí)例分析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。則最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。38122321133+6+10算法設(shè)計(jì)從n個(gè)作業(yè)的所有排列中找出最小完成時(shí)間和的最小調(diào)度問題，所以批處理作業(yè)調(diào)度問題的解空間是一顆排列樹。39批處理作業(yè)調(diào)度40解空間：排列樹voidFlowshop::Backtrack(inti){if(i>n){//到達(dá)葉結(jié)點(diǎn)，判斷并更新最優(yōu)解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){//僅考慮有更優(yōu)可能選擇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è)所需的處理時(shí)間*x,//當(dāng)前作業(yè)調(diào)度*bestx,//當(dāng)前最優(yōu)作業(yè)調(diào)度*f2,//機(jī)器2完成處理時(shí)間

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

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

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

n;//作業(yè)數(shù)};算法效率解空間：排列樹復(fù)雜性：在最壞情況下，整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為T(n)=O(n!)。415.4符號(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ù)相同。425.4符號(hào)三角形問題解向量：用n元組x[1:n]表示三角形第一行，其中x[i]=1代表“+”，x[i]=0代表“-”解空間：子集數(shù)，且為二叉樹遞推生成：x[1:i]確定一個(gè)子三角；x[i+1]的結(jié)果只需多考慮一條斜邊三角形包含符合個(gè)數(shù)：n*(n+1)/2|+|=|-|=n*(n+1)/4故當(dāng)“+”或“-”超過n*(n+1)/4，可剪枝n*(n+1)/2為奇數(shù)時(shí)，肯定不滿足43++-+-+++----+-+++--++--+---+5.4符號(hào)三角形問題privatestaticvoidbacktrack(intt){

if((count>half)||(t*(t-1)/2-count>half))return;

if(t>n)sum++;//到達(dá)葉節(jié)點(diǎn)，找到一個(gè)解

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;}}44++-+-+++----+-+++--++--+---+count:“+”個(gè)數(shù)half：總符號(hào)數(shù)/2sum：達(dá)標(biāo)三角形個(gè)數(shù)p：符合三角形內(nèi)容從第二行起遞推擴(kuò)展子三角，計(jì)算”+”號(hào)個(gè)數(shù)剪除不可能分枝算法效率解空間：子集樹復(fù)雜性：計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有O(2n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號(hào)三角形問題的回溯算法所需的計(jì)算時(shí)間為O(n2n)。455.5n后問題

例（4后問題）設(shè)有一4*4的棋盤，把4個(gè)皇后放在棋盤上，要求滿足下列兩個(gè)條件：1）任意兩個(gè)皇后不在同一行上和同一列上；2）任意兩個(gè)皇后不在同一條對(duì)角線上；問有多少種放法？若用窮舉法，先不考慮這兩個(gè)條件，則有種方案。C(16,4)=182046設(shè)第i行放置第i個(gè)皇后，xi表示皇后i所處的列數(shù)，這樣4后問題的全部解向量可以寫成(x1,x2,x3,x4)的形式。顯式約束條件是xi={1，2，3，4}1≤i≤4若只考慮顯式約束條件，則解空間是由44=256個(gè)四元組組成。隱式條件有兩個(gè)：兩個(gè)皇后不在同一列上和不在同一對(duì)角線上。471238134691114165710121517x1=118192429202225273032212326283133x1=2x2=2x3=3x4=4344242334232

這棵排列樹僅考慮了條件1）。這棵樹也叫做該問題的解空間。結(jié)點(diǎn)的編號(hào)是按深度優(yōu)先給出的。樹中的分支代表著解向量(x1,x2,x3,x4)的分量xi的取值。從根到葉子的所有路徑組成解空間。則有種方案。4!=2448QQХХQQQХХХХQQХQХХХХQQХ12347568109x1=1x2=23424233BBBBB4912347568109x1=1x2=23424233BBBBB111213141516x1=2BB1341350n后問題顯約束：xi=1,2,…,n隱約束：不同列：xixj不處于同一正、反對(duì)角線：|i-j||xi-xj|

如何判斷是否處于對(duì)角線：有y1=f(x1)，y2=f(x2)斜率(x1-x2)/(y1-y2)=1|xi-xj|=|i-j|51n后問題算法：判斷能否放置一個(gè)新棋子//在第k行的列位置x[k]是否可放置boolplace(intx[],intk)

{inti;

for(i=1;i<k;i++)

if((x[i]==x[k]))||abs(x[i]-x[k])==abs(i-k)))

returnFALSE;

i←i+1;}

returnTRUE;

}

52n后遞歸算法voidnqueens(intn,intx[])

{//由第k層向k+1層擴(kuò)展，確定x[k]的值

if(k>n)thenprintf(x[]);else{fori=1ton{x[k]=i;if(Place(x[],k))Backtrack(k+1);}

}

}53n后非遞歸算法voidnqueens(intn,intx[])

{intk=1;x[1]=0;

while(k>0){

x[k]=x[k]+1;//試驗(yàn)第k行的下一個(gè)未考察列

while(x[k]<=n)&&(!place(x,k)))

x[k]=x[k]+1;

if(x[k]<=n){//說明第k行有位置可放入

if(k==n)break;//n行全部考察結(jié)束

else{k=k+1;x[k]=0;}//下一行

}

else{x[k]=0;k=k-1;}//無(wú)法放入，退一行

}

}54n后問題555.60-1背包問題：裝載問題法比較裝載問題求最大重量0-1背包求最大價(jià)值解空間：子集樹1走左子樹，0走右子樹可行性約束函數(shù)當(dāng)前載重cw，價(jià)值cpcw+w[i]<=c，左子樹可選擇右子樹總是可以選，因?yàn)椴辉黾又亓肯藿绾瘮?shù)：cp+r<=bestp，減去右子樹565.60-1背包問題解空間：子集樹1走左子樹，0走右子樹改進(jìn)的限界函數(shù)：Bound()假設(shè)物品可拆分，利用貪心思想，求剩余空間裝滿對(duì)應(yīng)的最大價(jià)值按單位重量?jī)r(jià)值從大到小排序進(jìn)行選擇570-1背包問題Bound(inti){//計(jì)算價(jià)值的上界，故效率更高

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

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

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包，假設(shè)物品可拆分

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}58voidbacktrack(inti){//搜索第i層結(jié)點(diǎn)

if(i>n)//到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解bestx,bestp;return;if(cw+w[i]<=c){//搜索左子樹

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

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

if(bound(i+1)>bestp){x[i]=0;//搜索右子樹

backtrack(i+1);}}59載重量50，物體5,15,25,27,30，價(jià)值12,30,44,46,50。已按單位價(jià)值排好序605.7最大團(tuán)問題完全子圖：給定無(wú)向圖G=(V，E)。如果UV，且對(duì)任意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)。61例子12354{1,2}是G的一個(gè)大小為2的完全子圖，它不是團(tuán)。因?yàn)樗贕的更大的完全子圖{1,2,5}之中。{1,2,5},{1,4,5},{2,3,5}分別是G的最大團(tuán)。G的最大團(tuán)？62基本概念空子圖：如果UV且對(duì)任意u，vU有(u，v)E，則稱U是G的空子圖。12354{2,4}是G的一個(gè)空子圖。63基本概念(續(xù))獨(dú)立集：G的空子圖U是G的獨(dú)立集當(dāng)且僅當(dāng)U不包含在G的更大的空子圖中。G的最大獨(dú)立集：是G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。12354{2,4}是G的一個(gè)最大獨(dú)立子集。64基本概念(續(xù))補(bǔ)圖：對(duì)于任一無(wú)向圖G=(V，E)其補(bǔ)圖=(V1，E1)定義為：V1=V，且(u，v)E1當(dāng)且僅當(dāng)(u，v)E。123541235465例子12354{1，2}是的一個(gè)空子圖，不是的獨(dú)立集，因?yàn)樗诘目兆訄D{1,2,5}中。{1,2,5}是的最大獨(dú)立集。66基本概念(續(xù))U是G的最大團(tuán)當(dāng)且僅當(dāng)U是的最大獨(dú)立集。67問題分析解空間：子集樹可行性約束函數(shù)：頂點(diǎn)i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。限界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能找到更大的團(tuán)。68voidClique::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);}}69復(fù)雜度分析復(fù)雜度分析最大團(tuán)問題的回溯算法backtrack所需的計(jì)算時(shí)間為O(n2