《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第10章-搜索策略

第十章搜索策略搜索策略是從問題的解空間中搜索問題解的方法，本章將介紹兩種常見的搜索算法：回溯法和分支界限法?；厮莘ɑ厮莘ǖ膽?yīng)用分支界限法分支界限法的應(yīng)用一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法，它在包含問題所有解的空間樹中按照深度優(yōu)先的策略從根結(jié)點(diǎn)出發(fā)搜索解空間樹?；厮莘ɑ厮莘ɑ厮莘ㄔ谇髥栴}所有的解時(shí)，需要回溯到樹根，且在解空間樹中的所有結(jié)點(diǎn)全部搜索完成后結(jié)束。當(dāng)僅求問題的任意一個(gè)解時(shí)，只需要搜索到問題的一個(gè)解就可以結(jié)束。算法思想對(duì)解空間中任意一個(gè)結(jié)點(diǎn)，判斷該結(jié)點(diǎn)是否不包含問題的解：不包含，則跳過以該結(jié)點(diǎn)為根的子樹系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯；包含，則進(jìn)入該子樹并繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。問題的解空間問題的解空間與解空間樹解空間由長度為n的0-1向量組成，該解空間包含了對(duì)變量的所有可能的0-1賦值。樹根代表了在查找解之前的初始狀態(tài)。樹的第一層節(jié)點(diǎn)代表了對(duì)解的第二個(gè)分量所做的選擇，以此類推。如果一個(gè)部分構(gòu)造樹（子樹）仍然有可能導(dǎo)致一個(gè)完全解，我們說這個(gè)部分分解在樹中的相應(yīng)節(jié)點(diǎn)是有希望的，否則說是沒希望的。葉子要么代表沒希望的，要么代表算法找到完全解。

問題的解空間0-1背包問題（n種物品）【例1】當(dāng)n?=?3時(shí)，其解空間是：

{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),

(1,1,0),(1,1,1)}0-1背包問題的解空間樹從根到葉路徑上編碼即解空間元素若取W=（16,15,15），P=（40,25,25），C=30時(shí)間復(fù)雜度：O(2n)回溯策略的基本思想基本思想(1)

當(dāng)前結(jié)點(diǎn)成為活結(jié)點(diǎn)及擴(kuò)展結(jié)點(diǎn)；(2)

從當(dāng)前擴(kuò)展結(jié)點(diǎn)向縱深方向搜索并移至一個(gè)新結(jié)點(diǎn)，這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)及當(dāng)前的擴(kuò)展結(jié)點(diǎn)；(3)

若當(dāng)前擴(kuò)展結(jié)點(diǎn)不能向縱深移動(dòng)則成死結(jié)點(diǎn)，回溯至最近的活結(jié)點(diǎn)—成為當(dāng)前擴(kuò)展結(jié)點(diǎn)；(4)遞歸搜索，直至找到所要求的解或解空間中已無活結(jié)點(diǎn)時(shí)為止。

從開始結(jié)點(diǎn)(根結(jié)點(diǎn))出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間：回溯策略的基本思想(1)

從根結(jié)點(diǎn)A開始搜索（唯一的活結(jié)點(diǎn)及當(dāng)前擴(kuò)展結(jié)點(diǎn)）。(2)從結(jié)點(diǎn)A沿縱深方向先移至結(jié)點(diǎn)B或結(jié)點(diǎn)C(以先選結(jié)點(diǎn)B為例)，此時(shí)A和B是活結(jié)點(diǎn)，結(jié)點(diǎn)B成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。由于選取了w0，因此在結(jié)點(diǎn)B處剩余背包容量r?=?14，獲取的價(jià)值為45。(3)從結(jié)點(diǎn)B可移至結(jié)點(diǎn)D或結(jié)點(diǎn)E，由于移至結(jié)點(diǎn)D至少需要的背包容量為w1?=?15，而當(dāng)前僅有的剩余容量r?=?14，因此移到結(jié)點(diǎn)D將導(dǎo)致一個(gè)不可行解；而移到結(jié)點(diǎn)E不需要背包容量，因而是可行的，此時(shí)結(jié)點(diǎn)E成為新的擴(kuò)展結(jié)點(diǎn)，在結(jié)點(diǎn)E處，r?=?14，獲取的價(jià)值為45。(4)

這時(shí)結(jié)點(diǎn)A、B和E是活結(jié)點(diǎn)。從結(jié)點(diǎn)E可移到結(jié)點(diǎn)J或結(jié)點(diǎn)K，類似地，移到結(jié)點(diǎn)J導(dǎo)致一個(gè)不可行的解，而移到結(jié)點(diǎn)K是可行的，于是結(jié)點(diǎn)K成為新的擴(kuò)展結(jié)點(diǎn)。(5)由于K是葉子結(jié)點(diǎn)，因此得到一個(gè)可行的解，即x?=?(1,0,0)，獲得的價(jià)值為45。同理可獲得其他可行解，從其中選擇一個(gè)最優(yōu)解作為問題最終解?！纠?】n?=?3的0-1背包問題。

設(shè)w={16,15,15}，v={45,25,25}，c=30分析：回溯策略的基本思想運(yùn)用回溯法解題的關(guān)鍵要素有以下三點(diǎn)(1)針對(duì)給定的問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。遞歸和迭代回溯voidBackTrace(intt){

if(t>n)Output(x);

else for(inti=f(n,t);i<=g(n,t);i++){ x[t]=h(i);

if(Constraint(t)&&Bound(t))

BackTrace(t+1); }}

//BackTrace可用遞歸函數(shù)實(shí)現(xiàn)回溯法，遞歸函數(shù)模板如下：說明：t表示遞歸深度，即當(dāng)前擴(kuò)展結(jié)點(diǎn)在解空間樹的深度；n控制遞歸深度，即解空間樹的高度。當(dāng)t＞n時(shí)，算法已搜索到一個(gè)葉子結(jié)點(diǎn)，此時(shí)函數(shù)Output(x)對(duì)得到的可行解x進(jìn)行記錄或輸出處理。用f(n,t)和g(n,t)分別表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過的子樹的起始編號(hào)和終止編號(hào)；h(i)表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處x[t]?的第i個(gè)可選值；函數(shù)Constraint(t)和Bound(t)分別表示當(dāng)前擴(kuò)展結(jié)點(diǎn)處的約束函數(shù)和限界函數(shù)。遞歸和迭代回溯voidIterativeBackTrace(void){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--;

}}//IterativeBackTrace迭代回溯算法模板如下：說明：Solution(t)判斷在當(dāng)前擴(kuò)展結(jié)點(diǎn)處是否已得到問題可行解，若其返回值為真，則表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處x[1:t]是問題一個(gè)可行解；否則表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處x[1:t]只是問題的一個(gè)部分解，還需向縱深方向繼續(xù)搜索。子集樹與排列樹voidBackTrace(intt){if(t>n)Output(x);

else

for(inti=0;i<=n;i++){ x[t]=i; if(Contraint(t)&&Bound(t)) BackTrace(t+1);

}}//BackTrace子集樹當(dāng)給定的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。例：n個(gè)物品的0-1背包問題所對(duì)應(yīng)的解空間樹是一棵子集樹?；厮莘ㄋ阉髯蛹瘶涞囊话闼惴枋鋈缦拢鹤蛹瘶渑c排列樹voidBackTrace(intt){

if(t>n)Output(x);

else

for(inti=0;i<=n;i++){

Swap(x[t],x[i]);

if(Contraint(t)&&Bound(t)) BackTrace(t+1);

Swap(x[t],x[i]);

}}//BackTrace排列樹給定的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，對(duì)應(yīng)的解空間樹稱為排列樹?；厮莘ㄋ阉髋帕袠涞囊话闼惴枋鋈缦拢夯厮莘ǖ膽?yīng)用給定一個(gè)無向圖G=(V,E)，如果UV，且對(duì)任意u,v∈U有(u,v)∈E，則稱U是G的一個(gè)完全子圖。G的完全子圖U是G的一個(gè)團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中；G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。

子集?{1,2}?是G的一個(gè)大小為2的完全子圖，它不是一個(gè)團(tuán)，原因是它包含于G的更大完全子圖?{1,2,5}?中；而?{1,2,5}?是G的一個(gè)最大團(tuán)。同理，完全子圖

{1,4,5}和?{2,3,5}?也是G的最大團(tuán)。最大團(tuán)問題問題描述回溯法的應(yīng)用給定一個(gè)無向圖G=(V,E)，如果UV，且對(duì)任意u,v∈U有(u,v)∈E，則稱U是G的一個(gè)完全子圖。G的完全子圖U是G的一個(gè)團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中；G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。

(a)和(b)是兩個(gè)互為補(bǔ)圖的無向圖，{2,4}是G的一個(gè)空子圖，也是G的最大獨(dú)立集。而{1,2}是G'?的空子圖，但它不是G'?的獨(dú)立集，原因是它包含在G'的空子圖{1,2,5}中?？兆訄D{1,2,5}是G'?的最大獨(dú)立集。注：若U是G的最大團(tuán)當(dāng)且僅當(dāng)U是G'的最大獨(dú)立集?；厮莘ǖ膽?yīng)用算法設(shè)計(jì)無向圖G的最大團(tuán)和最大獨(dú)立集問題都可以用回溯法在時(shí)間復(fù)雜度為O(n2n)以內(nèi)解決，且都可以看做圖G的頂點(diǎn)集V的子集選取問題，因此可以用子集樹表示問題的解空間。設(shè)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z位于解空間樹的第i層，在進(jìn)入左子樹前，必須確認(rèn)從頂點(diǎn)i到已選擇進(jìn)入的頂點(diǎn)集之中每個(gè)頂點(diǎn)都有邊相連；在進(jìn)入右子樹前，必須確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。回溯法的應(yīng)用int**a;//圖G的鄰接矩陣intn;//圖G的頂點(diǎn)數(shù)int*x; //當(dāng)前解int*bestx;//當(dāng)前最優(yōu)解intcn;//當(dāng)前頂點(diǎn)數(shù)intbestn;//當(dāng)前最大頂點(diǎn)數(shù)voidBackTrace(inti){ if(i>n){ for(intj=1;j<=n;j++) bestx[j]=x[j];bestn=cn; return;

}

//檢查頂點(diǎn)i與當(dāng)前團(tuán)是否連接 ….…//見下頁回溯法的應(yīng)用

//檢查頂點(diǎn)i與當(dāng)前團(tuán)是否連接 intOK=1;

for(intj=1;j<i;j++) if(x[j]&&a[i][j]==0){//i與j不相連 OK=0;break;

}

if(OK){

x[i]=1;cn++;BackTrace(i+1);x[i]=0;cn--;

}

if(cn+ni>bestn){

x[i]=0;BackTrace(i+1);

}}intMaxClique(int**a,intv[],intn){

cn=0;bestn=0;bestx=v;BackTrace(1);

returnbestn;}回溯法的應(yīng)用問題描述給定一個(gè)無向連通圖G和m種不同的顏色，用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)染一種顏色，那么是否存在一種著色方案使得相鄰頂點(diǎn)不重色。若一個(gè)圖至少需要m種顏色才能使圖中任何相鄰頂點(diǎn)不重色，則m稱為該圖的色數(shù)。注：如果一個(gè)圖的所有頂點(diǎn)和邊都能用某種方式畫在一個(gè)平面上且沒有任何兩條邊相交，則稱這個(gè)圖為平面圖。圖的m著色問題求一個(gè)圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題?；厮莘ǖ膽?yīng)用鄰接矩陣a表示無向連通圖G=(V,E)，若(i,j)∈E，則a[i][j]=1；否則a[i][j]=0。用整數(shù)1～m表示m種不同顏色，頂點(diǎn)i所染的顏色用x[i]?表示，因此該問題的解向量可表示為x[1:n]。問題的解空間可表示為一棵高度為n+1的完全m叉樹，解空間樹的第i(1≤i≤n)層中的每一個(gè)結(jié)點(diǎn)都有m個(gè)孩子，其中每個(gè)孩子對(duì)應(yīng)于x[i]?的m種可能的著色之一；第n?+?1層結(jié)點(diǎn)均為葉子結(jié)點(diǎn)。算法設(shè)計(jì)n?=?3和m=3時(shí)問題的解空間樹回溯法的應(yīng)用求解圖的m可著色問題的過程就是遍歷解空間樹的過程，并在遍歷過程中記錄所有可行的著色方案，遍歷過程是向前搜索和回溯兩個(gè)過程的綜合，以期望獲得所有可能的解(著色方案)。//N-圖的頂點(diǎn)數(shù)//M-可用的顏色數(shù)//a-圖的鄰接矩陣//x-當(dāng)前的解//sum-可m著色的方案數(shù)#defineN20#defineM5intsum,p[N+1],*x,**a[N+1][N+1];sum=0;x=p;回溯法的應(yīng)用voidmColoring(){

for(inti=0;i<=N;i++)p[i]=0;

BackTrace(1);}voidBackTrace(intt){if(t>N){

sum++;

for(inti=1;i<=N;i++)printf("%d''",x[i]);

printf("\n");

}

else{ for(inti=1;i<=N;i++){

[t]=i;

if(OK(t))BackTrace(t+1);

}

}}時(shí)間復(fù)雜度O(nmn)回溯法的應(yīng)用intOK(intt){

for(inti=1;i<=N;i++)

if((a[t][i]==1)&&(x[i]==x[t]))

return0;

return1;}(1)遞歸函數(shù)BackTrace(1)實(shí)現(xiàn)整個(gè)解空間回溯搜索，BackTrace(i)搜索解空間中的第i層子樹。說明：(3)i≤n時(shí)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z是解空間中的一個(gè)內(nèi)部結(jié)點(diǎn)，該結(jié)點(diǎn)有x[i]=1,2,3,…,m共m個(gè)孩子結(jié)點(diǎn)，由函數(shù)OK檢查其可行性，并以深度優(yōu)先的方式遞歸地對(duì)可行子樹進(jìn)行搜索，或剪去不可行子樹。(2)i＞n時(shí)表示該算法已搜索到一個(gè)葉子結(jié)點(diǎn)，得到新的m著色方案?；厮莘ǖ膽?yīng)用設(shè)某旅行售貨員要到多個(gè)城市推銷商品，已知各城市之間的路程(旅費(fèi))，現(xiàn)在為其設(shè)計(jì)一條售貨路線，要求從某駐地出發(fā)經(jīng)過每個(gè)城市一遍，最后又回到駐地，且使總的路程(旅費(fèi))最小。旅行售貨員問題問題描述設(shè)G=(V,E)是一個(gè)帶權(quán)圖，其中，各條邊的權(quán)(費(fèi)用)為正整數(shù)；每一條周游路線是包含V中所有頂點(diǎn)的一條回路；一條周游路線的費(fèi)用是該回路上所有邊的權(quán)之和。所謂旅行售貨員問題就是要在圖G中找出一條有最小費(fèi)用的周游路線。問題形式描述：回溯法的應(yīng)用算法設(shè)計(jì)旅行售貨員問題的解空間樹是一棵排列樹，根據(jù)排列樹的遞歸算法模板，可得到如下算法：//n-圖的頂點(diǎn)數(shù)；//a[n+1][n+1]-圖的鄰接矩陣；//x[n]-當(dāng)前解；//bestx[n+1]-當(dāng)前最優(yōu)解；//cc-當(dāng)前費(fèi)用；//bestc-當(dāng)前最優(yōu)值；//NoEdge-無邊標(biāo)記；voidBackTrace(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];}

}回溯法的應(yīng)用

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]];

BackTrace(i+1);

cc

=a[x[i

1]][x[i]];

Swap(x[i],x[j]);

}

}}voidTravelRoute(){for(inti=1;i<=n;i++)x[i]=i;//初始化bestc=NoEdge; cc=0;

BackTrace(2);}回溯法的應(yīng)用(1)

遞歸函數(shù)BackTrace中，當(dāng)i=n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹的葉子結(jié)點(diǎn)的雙親結(jié)點(diǎn)，此時(shí)算法檢測(cè)圖G是否存在兩條邊：一條從頂點(diǎn)x[n-1]到x[n]的邊和一條從頂點(diǎn)x[n]到頂點(diǎn)x[1]的邊。如果這兩條邊都存在，則找到了一條旅行售貨員回路，此時(shí)算法還需要判斷這條回路的費(fèi)用是否優(yōu)于已經(jīng)找到的當(dāng)前最優(yōu)回路的費(fèi)用bestc，如果是，則必須更新當(dāng)前最優(yōu)值bestc和當(dāng)前最優(yōu)解bestx。說明：(2)當(dāng)i＜n時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹的第i-1層，圖G中存在從頂點(diǎn)x[i-1]?到頂點(diǎn)x[i]的邊時(shí)，x[1:i]構(gòu)成圖G的一條路徑，且當(dāng)x[1:i]的費(fèi)用小于當(dāng)前最優(yōu)值時(shí)算法進(jìn)入排列樹的第i層；否則將剪去相應(yīng)的子樹。算法中的變量cc記錄當(dāng)前路徑x[1:i]?的費(fèi)用。上述整個(gè)算法的時(shí)間復(fù)雜度為O(n!)分支界限法解題目標(biāo)不同：分支界限法的解題目標(biāo)是找出解空間樹T中滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找一個(gè)使目標(biāo)函數(shù)值極大或極小的解，即某種意義下的最優(yōu)解；而回溯法的解題目標(biāo)是找出T中滿足約束條件的所有解。在解空間樹T上的搜索方式不同：回溯法以深度優(yōu)先方式搜索T；而分支界限法以廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方式搜索T。分支界限法是一種在問題的解空間樹T上搜索問題解的算法分支界限法與回溯法的區(qū)別分支界限法在每一個(gè)活結(jié)點(diǎn)處計(jì)算函數(shù)值(限界)，并根據(jù)已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間中有最優(yōu)解的分支推進(jìn)，以便盡快找出一個(gè)最優(yōu)解。搜索策略在擴(kuò)展結(jié)點(diǎn)處生成其所有的孩子結(jié)點(diǎn)(分支)，然后再從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)；分支界限法以廣度優(yōu)先或最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹分支界限法常見解空間樹(1)每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)，一次性產(chǎn)生其所有孩子結(jié)點(diǎn)；孩子結(jié)點(diǎn)中導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的結(jié)點(diǎn)被舍棄，其余結(jié)點(diǎn)被加入活結(jié)點(diǎn)表。然后從活結(jié)點(diǎn)表中取當(dāng)前擴(kuò)展結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)。(2)重復(fù)上述結(jié)點(diǎn)的擴(kuò)展過程，直至找到所需的解或活結(jié)點(diǎn)表空時(shí)為止。子集樹和排列樹基本思想分支界限法活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)的方法(1)一般隊(duì)列方法。一般隊(duì)列方法是將活結(jié)點(diǎn)表組織成一般隊(duì)列，并按隊(duì)列中結(jié)點(diǎn)先進(jìn)先出的原則選取下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。(2)優(yōu)先級(jí)隊(duì)列方法。優(yōu)先級(jí)隊(duì)列方法是將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先級(jí)隊(duì)列，并按優(yōu)先級(jí)隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)來選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。分支界限法【例2】n?=?3時(shí)的0-1背包問題。設(shè)w={16,15,15},p={45,25,25},c=30，其解空間樹如圖：分支界限法搜索解空間樹的方法與解空間樹的廣度優(yōu)先遍歷算法極為相似，唯一不同之處是分支界限法不搜索以不可行結(jié)點(diǎn)為根的子樹。分支界限法一般隊(duì)列分支界限法：用隊(duì)列存放活結(jié)點(diǎn)表；算法從根結(jié)點(diǎn)開始，初始時(shí)活結(jié)點(diǎn)隊(duì)列為空，結(jié)點(diǎn)A是當(dāng)前活結(jié)點(diǎn)；結(jié)點(diǎn)A的兩個(gè)孩子B和C都是可行結(jié)點(diǎn)，故將結(jié)點(diǎn)B和結(jié)點(diǎn)C入隊(duì)，并且舍棄當(dāng)前擴(kuò)展結(jié)點(diǎn)A；在活結(jié)點(diǎn)隊(duì)列中取出活結(jié)點(diǎn)B作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，擴(kuò)展結(jié)點(diǎn)B有兩個(gè)孩子D和E，由于結(jié)點(diǎn)D是不可行結(jié)點(diǎn)故舍棄，結(jié)點(diǎn)E是可行結(jié)點(diǎn)故入隊(duì)；再從活結(jié)點(diǎn)隊(duì)列中取出結(jié)點(diǎn)C作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，繼續(xù)上述計(jì)算，直至活結(jié)點(diǎn)隊(duì)列空為止，算法終止。該算法搜索得到的最優(yōu)值是50。分支界限法分支界限法與回溯法的區(qū)別求解目標(biāo)不同回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。搜索方式的不同回法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先（最大效益）的方式搜索解空間樹。分支界限法的應(yīng)用分支限界法：每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程?；厮莘ǎ寒?dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問題的解。如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去；如果該結(jié)點(diǎn)不包含問題的解，則逐層向其祖先結(jié)點(diǎn)回溯。對(duì)擴(kuò)展節(jié)點(diǎn)的擴(kuò)展方式不同對(duì)存儲(chǔ)空間的要求不同

分支限界法的存儲(chǔ)空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。分支界限法的應(yīng)用裝載問題問題描述設(shè)有n個(gè)集裝箱，計(jì)劃將其裝上兩艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且。那么是否有一個(gè)合理的裝載方案，可將n個(gè)集裝箱裝上這兩艘輪船。問題分析當(dāng)時(shí)，裝載問題等價(jià)于子集和問題；當(dāng)c1=c2，且

時(shí)，裝載問題就等價(jià)于劃分問題。分支界限法的應(yīng)用采用下面的策略可以得到一個(gè)最優(yōu)裝載方案：算法設(shè)計(jì)(1)將第一艘輪船盡可能地裝滿；(2)

將剩余的集裝箱裝到第二艘輪船上。第一艘輪船盡可能地裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中的集裝箱重量之和最接近c(diǎn)1。由此可知，裝載問題等價(jià)于以下特殊的0-1背包問題：裝載問題是一個(gè)子集選取問題，其解空間樹是一棵子集樹分支界限法的應(yīng)用一般隊(duì)列分支界限法voidMaxLoading(intw[],intc,intn){

intlayer,Ew,bestw,wt;

layer=1;Ew=0;bestW=0;//初始化

InitQueue(Q);

//初始化隊(duì)列，解空間樹中的根結(jié)點(diǎn)入隊(duì)

add(Q,Ew);

add(Q,

1)；

//搜索子集解空間樹

while(!QueueIsEmpty(Q)){ delete(Q,Ew); //此時(shí)的Ew為0

if(Ew==1){

if(IsEmpty(Q))break;

add(Q,

1);

delete(Q,Ew);

layer++;

}分支界限法的應(yīng)用

//檢查左孩子結(jié)點(diǎn)

wt=Ew+w[layer];

if(wt<=c){//可行結(jié)點(diǎn)

x[layer]=1;

if(wt>bestw)bestw=wt;

if(layer<n)add(Q,wt);

}

add(Q,Ew); //右孩子結(jié)點(diǎn)總是可行的

}//while}說明：MaxLoading函數(shù)完成對(duì)解空間的分支界限搜索；隊(duì)列Q用于存儲(chǔ)活結(jié)點(diǎn)；Q中的Ew表示每個(gè)活結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前載重量。分支界限法voidEnQueue(Q,intwt,int&bestw,intn){

//將活結(jié)點(diǎn)加入Q隊(duì)列

if(i==n){ if(wt>bestw)

//可行葉子結(jié)點(diǎn)

bestw=wt;}

else{

//非葉子結(jié)點(diǎn)

add(Q,wt)；}}說明：函數(shù)EnQueue將活結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列Q中。該函數(shù)檢查i是否等于n，如果i=n，則表示當(dāng)前活結(jié)點(diǎn)為葉子結(jié)點(diǎn)，因葉子結(jié)點(diǎn)不會(huì)進(jìn)一步擴(kuò)展，因此不必將其加入到活結(jié)點(diǎn)隊(duì)列，此時(shí)檢查該葉子結(jié)點(diǎn)所表示的可行解是否優(yōu)于當(dāng)前最優(yōu)解，并適時(shí)更新當(dāng)前最優(yōu)解；否則當(dāng)前活結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)，應(yīng)加入到活結(jié)點(diǎn)隊(duì)列中。分支界限法的應(yīng)用算法改進(jìn)設(shè)bestw是當(dāng)前最優(yōu)解，Ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)對(duì)應(yīng)的重量，r是剩余集裝箱的重量。若Ew?+?r≤bestw，則可以將擴(kuò)展結(jié)點(diǎn)所對(duì)應(yīng)的子樹剪去。函數(shù)MaxLoading將bestw初始化為0，直至搜索到葉子結(jié)點(diǎn)時(shí)才更新bestw，因此在算法搜索到第一個(gè)葉子結(jié)點(diǎn)之前bestw?=?0，且r＞0，故Ew+r＞bestw總成立，即此時(shí)右子樹測(cè)試不起作用。為了使上述右子樹測(cè)試盡早發(fā)揮作用，應(yīng)提前更新bestw。而我們知道算法最終找到的最優(yōu)值是所求問題的子樹中所有可行結(jié)點(diǎn)對(duì)應(yīng)的重量最大值，并且結(jié)點(diǎn)所對(duì)應(yīng)的重量僅在搜索進(jìn)入左子樹時(shí)增加，因此可以在算法每次進(jìn)入左子樹時(shí)更新bestw的值。分支界限法的應(yīng)用voidMaxLoading(intw[],intc,intn){InitQ();//初始化隊(duì)列intEw,bestw,r,layer,wt,i;Ew=0;//擴(kuò)展結(jié)點(diǎn)所對(duì)應(yīng)的載重量bestw=0;//當(dāng)前的最優(yōu)載重量r=0;//剩余集裝箱重量layer=1;

//當(dāng)前擴(kuò)展結(jié)點(diǎn)所處的層

for(intj=2;j<=n;j++)r+=w[j];add(Q,Ew);//起始設(shè)置隊(duì)列add(Q,

1);

while(!IsEmpty(Q)){delete(Q,Ew);

if(Ew==

1){

if(IsEmpty(Q)) break;

add(Q,

1);delete(Q,Ew);

layer++;

r

=w[layer]；

}分支界限法的應(yīng)用

//檢查左孩子結(jié)點(diǎn)

wt=Ew+w[layer]; //左孩子結(jié)點(diǎn)的重量

if(wt<=c){ //可行結(jié)點(diǎn)

if(wt>bestw)

bestw=wt; //更新最優(yōu)值

if(layer<n)

add(Q,wt); //加入活結(jié)點(diǎn)隊(duì)列

}

//檢查右孩子結(jié)點(diǎn)

if(((Ew+r)>bestw)&&(layer<n))

add(Q,Ew); //可能包含最優(yōu)解

}}分支界限法的應(yīng)用voidEnQueue(structQNode*activeQ,intwt,inti,intn,intbestw,structQNode*E,structQNode*bestE,intbestx[],intflagChild){

if(i==n){ //可行葉子結(jié)點(diǎn) if(wt==bestw){//當(dāng)前最優(yōu)裝載重量

bestE=E;

bestx[n]=flagChild; } return;

}

//非葉子結(jié)點(diǎn)

structQNode*q;

q->weight=wt;

q->parent=E->parent;

q->flagOfChild=flagChild;

add(Q,q);}將活結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中的函數(shù)EnQueue如下：分支界限法的應(yīng)用intMaxLoad(intw[],intc,intn,intbestx[]){

//返回最優(yōu)載重量，bestx返回最優(yōu)解

structQNode*aQ;

//活結(jié)點(diǎn)隊(duì)列

add(aQ,-1);//同層結(jié)點(diǎn)尾部標(biāo)志

inti=1;//當(dāng)前擴(kuò)展結(jié)點(diǎn)所處的層

intEw=0;//對(duì)應(yīng)擴(kuò)展結(jié)點(diǎn)的載重量

intbestw=0;//當(dāng)前最優(yōu)載重量

intr=0;

//剩余集裝箱重量for(intj=2;j<=n;j++)

r+=w[j];structQNode*Eq=0;//當(dāng)前擴(kuò)展結(jié)點(diǎn)

structQNode*bestE;//當(dāng)前最優(yōu)擴(kuò)展結(jié)點(diǎn)

分支界限法的應(yīng)用

//搜索子集空間樹

while(true){//檢查左孩子結(jié)點(diǎn)

intwt=Ew+w[i];

if(wt<c){//可行結(jié)點(diǎn)

if(wt>bestw)bestw=wt;

EnQueue(aQ,wt,i,n,bestw,Eq,bestE,bestx,1);

}

//檢查右孩子結(jié)點(diǎn)

if(Ew+r>bestw)

EnQueue(aQ,wt,i,n,bestw,Eq,bestE,bestx,0);

delete(aQ,Eq);

//取下一個(gè)擴(kuò)展結(jié)點(diǎn)

if(!Eq){//同層結(jié)點(diǎn)尾部

if(IsEmpty(aQ))break;

add(aQ,0);

//同層結(jié)點(diǎn)尾部標(biāo)志

delete(aQ,Eq);//取下一個(gè)擴(kuò)展結(jié)點(diǎn)

i++;//進(jìn)入下一層

r-=w[i];

}

}//while分支界限法的應(yīng)用

//構(gòu)造當(dāng)前最優(yōu)解

for(intj=n-1;j>0;j--){

bestx[j]=bestE->flagOfChild;

bestE=bestE->parent;}returnbestw;}分支界限法的應(yīng)用構(gòu)造最優(yōu)解

為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相對(duì)應(yīng)的最優(yōu)解，算法必須記錄相應(yīng)子集樹中從活結(jié)點(diǎn)到根的路徑，為此，必須設(shè)置指向其雙親結(jié)點(diǎn)的指針，并設(shè)置左右孩子標(biāo)志。活結(jié)點(diǎn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)如下：structQNode{structQNode*parent;

intflagOfChild;//0表示左孩子；1表示右孩子intweight;};分支界限法的應(yīng)用印刷電路板將布線區(qū)域劃分成n?×?m個(gè)方格陣列，如圖(a)所示。電路布線問題要求確定連接方格a的中點(diǎn)和方格b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿直線或直角布線，并且要求所布線路不能相交，如圖(b)所示。為了避免線路相交，已經(jīng)布線的方格應(yīng)設(shè)置封鎖標(biāo)記，其他線路不允許穿過已經(jīng)封鎖的方格。布線問題問題描述分支界限法的應(yīng)用分析布線問題的解空間是一個(gè)圖，用隊(duì)列分支界限法解此問題。從起始位置a開始，將其作為第一個(gè)擴(kuò)展結(jié)點(diǎn)，與該擴(kuò)展結(jié)點(diǎn)相鄰并且可達(dá)的方格成為可行結(jié)點(diǎn)被加入到活結(jié)點(diǎn)隊(duì)列中，并且將這些方格標(biāo)記為1，即從起始方格a到這些方格的距離為1。接著從活結(jié)點(diǎn)隊(duì)列中取出隊(duì)首結(jié)點(diǎn)作為下一個(gè)擴(kuò)展結(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰且未標(biāo)記過的方格標(biāo)記為2，并存入活結(jié)點(diǎn)隊(duì)列。這個(gè)過程一直持續(xù)到算法搜索到目標(biāo)方格b，或活結(jié)點(diǎn)隊(duì)列空時(shí)結(jié)束。分支界限法的應(yīng)用首先考慮記錄電路板上某方格位置：用結(jié)構(gòu)體表示。結(jié)構(gòu)體有row和col兩個(gè)成員。其次需要表示布線前進(jìn)的方向：布線可沿右、下、左、上四個(gè)方向移動(dòng)，分別用0、1、2、3表示。再用offset[i].row和offset[i].col(i=0,1,2,3)表示沿著四個(gè)方向移動(dòng)一步時(shí)對(duì)于當(dāng)前方格的相對(duì)位移，如下表所示。移動(dòng)方向行位移(offset[i].row)列位移(offset[i].col)0右011下102左0-13上-10用二位數(shù)組grid[i][j]表示電路板上某方格的布線，grid[i][j]=0表示該方格允許布線；grid[i][j]=1表示該方格不允許布線。分支界限法的應(yīng)用voidFindPath(structPositionbeginP,structPositionendP){

intfinished=0;if((beginP.row==endP.row)&&(beginP.col==endP.col)) pathLen=0;

else{ for(inti=0;i<=m+1;i++){

grid[0][i]=1;

grid[n+1][i]=1; } for(inti=0;i<=n+1;i++){

grid[i][0]=1;

grid[i][m+1]=1; }

算法分支界限法的應(yīng)用

structPositionoffset[4];

offset[0].row=0;

offset[0].col=1;

offset[1].row=1; offset[1].col=0; offset[2].row=0; offset[2].col=-1; offset[3].row=-1; offset[3].col=0; intnumbersOfNeighbor=4; structPositioncurrentP,currentNeighbor; currentP.row=beginP.row; currentP.col=beginP.col; grid[beginP.row][beginP.col]=MAX; structActiveNodeQueueactiveQ;分支界限法的應(yīng)用

while(finished==0){ for(inti=0;i<numbersOfNeighbor;i++){ currentNeighbor.row=currentP.row+offset[i].row; currentNeighbor.col=currentP.col+offset[i].col; if(grid[currentNeighbor.row][currentNeighbor.col]==0){

grid[currentNeighbor.row][currentNeighbor.col] =grid[currentP.row][currentP.col]+1;