分支限界法大連海事大學5．5．1分支搜索算法

1．基本思想

分支搜索法也是一種在問題解空間上進行嘗試搜索算法。所謂“分支”是采用廣度優先的策略，依次生成E-結點所有分支，也就是所有的兒子結點。和回溯法一樣，在生成的節點中，拋棄那些不滿足約束條件（或者說不可能導出最優可行解）的結點，其余節點加入活節點表。然后從表中選擇一個節點作為下一個E-節點。選擇下一個E-節點的方式不同導致幾種不同的分支搜索方式：1．FIFO搜索

2．LIFO搜索

3．優先隊列式搜索

1．FIFO搜索大連海事大學

一開始，根結點是唯一的活結點，根結點入隊。從活結點隊中取出根結點后，作為當前擴展結點。對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數的兒子加入活結點隊列中。再從活結點表中取出隊首結點（隊中最先進來的結點）為當前擴展結點，……，直到找到一個解或活結點隊列為空為止。

2．LIFO搜索大連海事大學

一開始，根結點入棧。從棧中彈出一個結點為當前擴展結點。對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數的兒子入棧，再從棧中彈出一個結點（棧中最后進來的結點）為當前擴展結點，……，直到找到一個解或棧為空為止。

3．優先隊列式搜索大連海事大學

為了加速搜索的進程，應采用有效地方式選擇E-結點進行擴展。優先隊列式搜索，對每一活結點計算一個優先級（某些信息的函數值），并根據這些優先級，從當前活結點表中優先選擇一個優先級最高（最有利）的結點作為擴展結點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。這種擴展方式要到下一節才用的到。

5．5．2分枝-限界搜索算法大連海事大學【例】有兩艘船，n個貨箱。第一艘船的載重量是c1，第二艘船的載重量是c2，wi

是貨箱i的重量,且

w1+w2+……+wn≤c1+c2。我們希望確定是否有一種可將所有n個貨箱全部裝船的方法。若有的話，找出該方法

FIFO限界搜索算法優先隊列式分支限界法算法1的缺點有:1）在可解的情況下，沒有給出每艘裝載物品的方案。而要想記錄第一艘船最大裝載的方案，象回溯法中用n個元素的數組是不能實現的，可以象5.2.2小節中的例子用數組隊列下標記錄解方案。這里采用構造二叉樹的方法，和5.2.2小節中的例題一樣只需要記錄最優解的葉結點，這樣二叉樹就必需有指向父結點的指針，以便從葉結點回溯找解的方案。又為了方便知道當前結點對物品的取舍情況，還必須記錄當前結點是父結點的哪一個兒子。數據結構：由此，樹中結點的信息包括：weight;parent;LChild;。同時這些結點的地址就是抽象隊列的元素，隊列操作與算法1相同.

2）算法1是在對子集樹進行盲目搜索，我們雖然不能將搜索算法改進為多項式復雜度，但在算法中加入了“限界”技巧，還是能降低算法的復雜度。

一個簡單的現象，若當前分支的“裝載上界”，比現有的最大裝載小，則該分支就無需繼續搜索。而一個分支的“裝載上界”，也是容易求解的，就是假設裝載當前物品以后的所有物品。舉一個簡單的例子，W={50，10，10}，C1=60，所構成的子集樹就無需搜索結點2的分支，因為擴展結點1后，就知道最大裝載量不會小于50；而擴展結點2時，發現此分支的“裝載上界”為w2+w3=20<50，無需搜索此分支，結點2不必入隊。數據結構：相應地，當前最大裝載bestw不僅僅對葉結點計算，每次搜索裝載情況（搜索左兒子）時，都重新確定bestw的值。為了方便計算一個分支的“裝載上界”，用變量r記錄當前層以下的最大重量。

公共變量的定義：大連海事大學floatbestw,w[100],bestx[100];intn；QueueQ;structQNode{floatweight;QNode*parent;QNodeLChild;}

算法如下：main(){intc1,c2,n,s=0,i;input(c1,c2，n);for(i=1;i<=n;i++){input(w[i])；s=s+w[i]；}if(s<=c1ors<=c2){print(“needonlyoneship”);return;}if(s>c1+c2){print(“nosolution”);return;}大連海事大學MaxLoading(c1);if(s-bestw<=c2);{print(“Thefirstshiploading”,bestw，“chose：”);for(i=1;i<=n;i++)if(bestx[i]=1)print(i，“，”);print(“換行符Thesecondshiploading”,s-bestw,“chose”);for(i=1;i<=n;i++)if(bestx[i]=1)print(i,”,”);}elseprint(“nosolution”);}2AddLiveNode(folatwt,inti,QNode*E,intch){Qnode*b;if(i=n)/葉子

{if(wt>bestw)/目前的最優解/{bestE=E;bestx[n]=ch;}//bestx[n]取值為chreturn;}b=newQNode;//不是葉子,添加到隊列中b->weight=wt;b->parent=E;b->LChild=ch;//新節點是左孩子時add(Q,b);}

MaxLoading(intn,intbestx[]){Qnode*E;inti=1;E=newQNode;add(Q,0);//0代表本層的尾部E->weight=0;E->parent=null;E->Lchild=0;add(Q,E);bestw=0;r=0;//E-節點中余下的重量Ew=E->weight;for(intj=2;j<=n;j++)r=r+w[i];while(true)//搜索子集空間樹

{wt=E->weight+w[i];//檢查E-節點的左孩子

if(wt<=c)//可行的左孩子

{if(wt>bestw)bestw=wt;AddLiveNode(wt,i,E,1);}if(Ew+r>bestw)//檢查右孩子

AddLiveNode(Ew,i,E,0);Delete(Q,E);//下一個E-節點if(!E)//層的尾部

{if(Empty(Q))break;add(Q0);//層尾指針

Delete(Q,E);//下一個E-節點

i++;//E-節點的層次

r=r-w[i];}//E-節點中余下的重量

Ew=E->weight;//新的E-節點的重量

}//沿著從bestE到根的路徑構造x[]，x[n]由AddLiveNode來設置for(j=n-1;j>0;j--){bestx[j]=bestE->LChild;//從bool轉換為intbestE=bestE->parent;}returnbestw;}

算法設計3：用優先隊列式分支限界法解決【例】的問題大連海事大學

上一節介紹的優先隊列式擴展方式，若不加入限界策略其實是無意義的。因為要說明解的最優性，不搜索完所有問題空間是不能下結論的，而要對問題空間進行完全搜索，考慮優先級也就沒有意義了。優先隊列式搜索通過結點的優先級，可以使搜索盡快朝著解空間樹上有最優解的分支推進，這樣當前最優解一定較接近真正的最優解。其后我們將當前最優解作為一個“界”，對上界（或下界）不可能達到（大于）這個界的分支則不去進行搜索，這樣就縮小搜索范圍，提高了搜索效率。這種搜索策略稱為優先隊列式分支限界法——LC-檢索。大連海事大學

1）結點擴展方式：無論那種分支限界法，都需要有一張活結點表。優先隊列的分支限界法將活結點組織成一個優先隊列，并按優先隊列中規定的結點優先級選取優先級最高的下一個結點成為當前擴展結點。

2）結點優先級確定：優先隊列中結點優先級常規定為一個與該結點相關的數值p，它一般表示其接近最優解的程度，本例題就以當前結點的所在分支的裝載上界為優先值。3）優先隊列組織：結點優先級確定后，簡單地按結點優先級進行排序，就生成了優先隊列。排序算法的時間復雜度較高，考慮到搜索算法每次只擴展一個結點，回憶數據結構中堆排序，適合這一特點且比較交換的次數最少。此題應該采用最大堆來實現優先隊列。

大連海事大學數據結構設計：1）要輸出解的方案，在搜索過程中仍需要生成解結構樹，其結點信息包括指向父結點的指針和標識物品取舍（或是父結點的左、右孩子）。

2）堆結點首先應該包括結點優先級信息：結點的所在分支的裝載上界uweight；堆中無法體現結點的層次信息（level），只能存儲在結點中；AddLiveNode用于把bbnode類型的活節點加到子樹中，并把HeapNode類型的活節點插入最大堆。

3）不同與算法2，由于擴展結點不是按層進行的計算結點的所在分支的裝載上界時，要用數組變量r記錄當前層以下的最大重量，這樣可以隨時方便使用各層結點的裝載上界。

算法設計3（3）：算法3如下：HeapNodeH[1000];structbbnode{bbnode*parent;//父節點指針intLChild;};//當且僅當是父節點的左孩子時，取值為1structHeapNode{bbnode*ptr;//活節點指針

floatuweight;//活節點的重量上限

intlevel;};//活節點所在層

同樣為了突出算法本身的思想，對堆操作也只進行抽象的描述：用HeapNode代表隊列類型，則HeapNodeH；定義了一個堆H，相關操作有：Insert(Q，……)表示入堆；DeleteMax(Q，……);表示出堆。算法設計3（4）大連海事大學AddLiveNode(floatwt,intlev,bbnode*E,intch){bbnode*b=newbbnode;b->parent=E;b->LChild=ch;HeapNodeN;N.uweight=wt;N.level=lev;N.ptr=b;Insert(H，N);}大連海事大學MaxLoading(floatc,intn,intbestx[]){froatr[100],Ew，bestw=0;r[n]=0;for(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];inti=1;bbnode*E=0;Ew=0;//搜索子集空間樹while(i!=n+1)//不在葉子上

{if(Ew+w[i]<=c)//可行的左孩子

{AddLiveNode(E,Ew+w[i]+r[i],1,i+1);}if(bestw<Ew+w[i])bestw=Ew+w[i];if(bestw<Ew+r[i])AddLiveNode(E,Ew+r[i],0,i+1);DeleteMax(H，E);i=N.level;E=N.ptr;Ew=N.uweight-r[i-1];}for(intj=n;j>0;j--){bestx[j]=E->LChild;E=E->parent;}returnEw;}算法說明：

算法的復雜度仍為O（2n），但通過限界策略，并沒有搜索子集樹中的所有結點，且，由于每次都是選取的最接近最優解的結點擴展，所以一當搜索到葉結點作E結點時算法就可以結束了。算法結束時堆并不一定為空。

小結討論：FIFO搜索或LIFO搜索也可以通過加入“限界”策略加速搜索嗎？那與優先隊列式分支限界法——LC—檢索的區別在哪兒呢？

答案：由于FIFO搜索或LIFO搜索是盲目擴展地結點，當前最優解距真正的最優解距離較大，作為“界”所起到的剪枝作用很有限，不能有效提高搜索速度。其實看了下面的例子大家會發現，優先隊列式擴展結點的過程，一開始實際是在進行類似“深度優先”的搜索。

例如：W={10，30，50}，C1=60，所構成的子集樹如下圖所表示：FIFO限界搜索過程為：大連海事大學1）

初始隊列中只有結點A；2）

結點A變為E-結點擴充B入隊，bestw=10；結點C的裝載上界為30+50=80>bestw，也入隊；3）

結點B變為E-結點擴充D入隊，bestw=40；結點E的裝載上界為60>bestw，也入隊；4）

結點C變為E-結點擴充F入隊，bestw仍為40；結點G的裝載上界為50>bestw，也入隊；5）

結點D變為E-結點，葉結點H超過容量，葉結點I的裝載為40，bestw仍為40；6）

結點E變為E-結點，葉結點J裝載量為60，bestw為60；葉結點K被剪掉；7）

結點F變為E-結點，葉結點L超過容量，bestw為60；葉結點M被剪掉；8）

結點G變為E-結點，葉結點N、O都被剪掉；此時隊列空算法結束。LC-搜索的過程如下：大連海事大學1）

初始隊列中只有結點A；2）

結點A變為E-結點擴充B入堆，bestw=10；結點C的裝載上界為30+50=80>bestw，也入堆；堆中B上界為90在優先隊列首。3）

結點B變為E-結點擴充D入堆，bestw=40；結點E的裝載上界為60>bestw，也入堆；此時堆中D上界為90為優先隊列首。4）

結點D變為E-結點，葉結點H超過容量，葉結點I的裝載為40入堆，

bestw仍為40；此時堆中C上界為80為優先隊列首。5）

結點C變為E-結點擴充F入堆，bestw仍為40；結點G的裝載上界為50>bestw，也入堆；此時堆中E上界為60為優先隊列首。6）

結點E變為E-結點，葉結點J裝載量為60入堆，bestw變為60；葉結點K上界為10<bestw被剪掉；此時堆中J上界為60為優先隊列首。7）

結點J變為E-結點，擴展的層次為4算法結束。雖然此時堆并不空，但可以確定已找到了最優解。大連海事大學FIFO限界算法搜索解空間的過程是按圖5-26子集樹中字母序進行的，而優先隊列限界搜索解空間的過程是：A-B-D-C-E-J

看了上面的例子大家會發現，優先隊列法擴展結點的過程，一開始實際是在進行類似“深度優先”的搜索。5．5．3算法框架

上一小節的例子是求最大值的最優化問題，下面我們以求找最小成本的最優化問題，給出FIFO分支搜索算法框架。假定問題解空間樹為T，T至少包含一個解結點（即答案結點）。u為當前的最優解，初值為一個較大的數;E表示當前擴展的活結點，x為E的兒子，s(x)為結點x下界函數，當其值比u大時，不可能為最優解，不繼續搜索此分支，該結點不入隊；當其值比u小時，可能達到最優解，繼續搜索此分支，該結點入隊；cost（X）為當前葉結點所在分支的解。算法框架如下：大連海事大學

2）：

大連海事大學search（T）

//為找出最小成本答案結點檢索T。

{leaf=0;

初始化隊；ADDQ（T）；

//根結點入隊parent（E）=0；

//記錄擴展路徑，當前結點的父結點

while（隊不空）{DELETEQ(E)//隊首結點出隊為新的E結點；for（E的每個兒子

X）

if(s（X）<u)//當是可能的最優解時入隊

{ADDQ（X）；

parent（X）=E;

if(X是解結點

)//x為葉結點

{U=min（cost（X），u）;

leaf=x;}//方案的葉結點存儲在leaf中

}}3）：

大連海事大學

print（”leastcost=’，u）；

while（leaf<>0）

//輸出最優解方案

{print（leaf）；

leaf=parent（leaf）；}

}

大連海事大學

找最小成本的LC分支-限界算法框架與

FIFO分支-限界算法框架結構大致相同，只是擴展結點的順序不同，因而存儲活結點的數據結構不同。

FIFO分支-限界算法用隊存儲活結點，LC分支-限界算法用堆存儲活結點，以保證比較優良的結點先被擴展。且對于LC分支-限界算法，一當擴展到葉結點就已經找到最優解，可以停止搜索。5．6圖的搜索算法小結

大連海事大學1．深度優先搜索與廣度優先搜索算法有何區別

通常深度優先搜索法不全部保留結點，擴展完的結點從數據存儲結構棧中彈出刪去，這樣，一般在數據棧中存儲的結點數就是解空間樹的深度，因此它占用空間較少。所以，當搜索樹的結點較多，用其它方法易產生內存溢出時，深度優先搜索不失為一種有效的求解方法。

廣度優先搜索算法，一般需存儲產生的所有結點，占用的存儲空間要比深度優先搜索大得多，因此，程序設計中，必須考慮溢出和節省內存空間的問題。但廣度優先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優先搜索要快些。

大連海事大學2．回溯與分支限界法回溯法以深度優先的方式搜索解空間樹T，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹T。由于它們在問題的解空間樹T上搜索的方法不同，適合解決的問題也就不同。一般情況下，回溯法的求解目標是找出T中滿足約束條件的所有解的方案，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使用某一目標函數值達到極大或極小的解，即在某種意義下的最優解。相對而言，分支限界算法的解空間比回溯法大得多，因此當內存容量有限時，回溯法成功的可能性更大。下表列出了回溯法和分支限界法的一些區別：3.

在處理最優問題時，采用窮舉法、回溯法或分支限界法都可以通過利用當前最優解和上界函數加速。僅就對限界剪支的效率而言，優先隊列的分支限界法顯然要更充分一些。在窮舉法中通過上界函數與當前情況下函數值的比較可以直接略過不合要求的情況而省去了更進一步的枚舉和判斷；回溯法則因為層次的劃分，可以在上界函數值小于當前最優解時，剪去以該結點為根的子樹，也就是節省了搜索范圍；分支限界法在這方面除了可以做到回溯法能做到的之外，同時若采用優先隊列的分支限界法，用上界函數作為活結點的優先級，一旦有葉結點成為當前擴展結點，就意味著該葉結點所對應的解即為最優解，可以立即終止其余的過程。在前面的例題中曾說明，優先隊列的分支限界法更象是有選擇、有目的地進行深度優先搜索，時間效率、空間效率都是比較高的。大連海事大學5.