1、分支與限界：貨物裝載問題課程名稱： 院 系: 學生姓名： 學 號: 專業班級： 指導教師：*2013年12月27日分支與限界：貨物裝載問題摘要：在現實生活中，我們會經常遇見貨物裝載問題，如何解決貨物裝載問題， 獲取利潤的最大化，花費最少的而得到更多的東西，是人們一直都要考慮的問題。 在廣泛的解決問題中，人們一般采用分支限界算法解決這樣的問題。 分支限界法 是由分支策略和限界策略兩部分組成的。分枝定界法是一個用途十分廣泛的算 法，運用這種算法的技巧性很強，不同類型的問題解法也各不相同。 該算法在具 體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個子集內的解的值計算一個下

2、界或上界（稱為定界）。在每次分支后，對凡是 界限超出已知可行解值那些子集不再做進一步分支。這樣，解的許多子集（即搜索樹上的許多結點）就可以不予考慮了，從而縮小了搜索范圍。該算法在具體執 行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個子集內的解的值計算一個下界或上界（稱為定界）。在每次分支后，對凡是界限 超出已知可行解值那些子集不再做進一步分支。 這樣，解的許多子集（即搜索樹 上的許多結點）就可以不予考慮了，從而縮小了搜索范圍。分支策略體現在對問 題空間是按廣度優先的策略進行搜索，限界策略是為了加速搜索速度而采用啟發 信息剪枝的策略。在分支限界法，經常采用的是分支搜索法，

3、分支搜索法是一種 在問題空間上進行搜索嘗試的算法。 所謂分支是采用廣度優先的策略，依次搜索 E-結點的所有的分支，也就是所有的相鄰結點。和回溯法一樣，在生成的節點中， 拋棄那些不滿足的約束條件的的結點，其余結點加入活結點表。在分支搜索的算 法中，人們經常會采用FIFO搜索和優先隊列式搜索。例題中采用的是輪船裝載 的問題，這是一個非常經典的分支限界算法的例題，通過這個例子的學習，將會理解并掌握分支限界貨物裝載的問題。關鍵詞：分支限界法 貨物裝載FIFO分支限界 優先隊列分支限界目錄第一章緒論 41.1分支-界限算法的基本思想 41.2常見的兩種分支界限算法 4第二章貨物裝載問題 52.1問題描述

4、 52.2 問題分析 5第三章 優先隊列式分支限界法解決貨物裝載問題 63.1算法設計 63.2數據結構設計 7程序流程圖 7數據結構描述 7重要算法 83.3測試結果與分析 9第四章 基于隊列式(FIFO)分支限界法解決貨物裝載問題.104.1算法設計 104.2數據結構設計 10程序流程圖 11數據結構描述和算法 114.3測試結果與分析 13第五章結論 14參考文獻 15第一章緒論1.1分支-界限算法的基本思想分支限界法常以廣度優先或以最小耗費 （最大效益）優先的方式搜索問題的 解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點 一旦成為擴展結點，就一次性產生其所有兒

5、子結點。 在這些兒子結點中，導致不 可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。1.2常見的兩種分支界限算法隊列式（FIFO）分支限界法按照隊列先進先出（FIFO）原則選取下一個節點 為擴展節點。FIFO搜索算法要依賴“隊”做基本的數據結構。一開始根節點是 唯一的活結點，根節點入隊。從活結點的對中取出艮結點后，作為當前擴展結點。 對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿 足約束函數的兒子加入到活結點隊列中。再從活結點表中

6、取出隊首結點為當前擴 展結點。優先隊列式分支限界法按照優先隊列中規定的優先級選取優先級最高的 節點成為當前擴展節點。優先隊列式搜索，對每一個活結點計算一個優先級， 并 根據這些優先級，從當前活結點表中優先選擇一個一個優先級最高的節點作為擴 展結點，使搜索朝著解空間樹上最優解的分支推進，以便盡快找出一個最優解。第二章貨物裝載問題2.1問題描述有兩艘船和需要裝運的N個貨箱，第一艘船的載重量是c1,第二艘船的載重 量是c2，wi是貨箱i的重量，且w1+w2+.+w*=c1+c2。希望確定是否有一種 可能將所有貨箱全部裝船的方法。若有的話，找出該方法。2.2問題分析先看一個實例，當n=3,c1=c2=

7、50,w=10,40,40時，可將貨箱1,2裝到第一 艘船上，貨箱3裝到第二艘船上。但如果w=20,40,40,則無法將貨箱全部裝船。 有此可知問題可能有解，可能無解，也可能多解。雖然是關于兩艘船的問題，若 w1+w2+w3+.wn-bestw<=c2則可能確定一個解，否則問題就無解。這樣的問題 就轉化為第一艘船的最大裝載問題。第三章優先隊列式分支限界法解決貨物裝載問題3.1算法設計解裝載問題的優先隊列式分支限界法用最大優先隊列存儲活結點表。活結 點x在優先隊列中的優先級定義為從根結點到結點x的路徑所相應的載重量再加上剩余集裝箱的重量之和。優先隊列中優先級最大的活結點成為下一個擴展結 點

8、。優先隊列中活結點x的優先級為x.uweight。以結點x為根的子樹中所有結 點相應的路徑的載重量不超過x.uweight。子集樹中葉結點所相應的載重量與其 優先級相同。因此在優先隊列式分支限界法中，一旦有一個葉結點成為當前擴展 結點，貝冋以斷言該葉結點所相應的解即為最優解，此時終止算法。通過實驗， 了解了分支限界法的基本思想。掌握了利用優先隊列式分支限界法實現具體的裝 載問題。由于利用java.util 包下的PriorityQueue 代替算法中的最大堆，免去 了編寫實現最大堆的程序代碼。優先隊列式分支限界法進行算法設計的要點如下：(1) 結點擴展方式：無論是那種分支限界法，需要有一張活的

9、結點表。優先隊列的分支限界法將活結點組成一個優先隊列，并按優先隊列中規定的結點優 先選取最高的下一個結點成為當前擴展結點。(2) 結點優先級確定：優先隊列中的結點優先級長規定一個與該節點相關 的數值w,w 一般表示以該節點為根的子樹的分支接近最優解的程度。(3) 優先隊列組織：結點優先級確定后，按結點優先級進行排序，就生成 了優先隊列。排序算法的時間復雜度較高，考慮到搜索算法每次只擴展一個結點， 數據結構中堆排序，適合這一特點且比較交換的次數最少。此例采用最大堆來實 現優先隊列。3.2數據結構設計程序流程圖創建-卒飆駅t prioriiyQueiM笄蟲側牝j-nr j = rj + l + w

10、j41bastx j - E . Lchild E = E - parent; j+否i=衛識)count = o 1=1iddLivIJode iW,E”wwk - v il ;k+ + ; bestk li - false;if+Eu+w*1T+r （1,truerF鼻丹i+lHaddLivNods（HFE 廠UJt木樂Sih2i木氐此JEw+r i false i+1）;*F咨崎2卒社程同上r圖3-1優先隊列限界法流程圖數據結構描述(1) 要輸出解的方案，在搜索過程中仍需要生成解結構樹，其結點信息包括指向父結點的指針和標識物品取舍（或是父結點的左、右孩子）。（2） 堆結點包括結點優先級信

11、息：結點所在分支的裝載上界uweight ;堆 中無法體現結點的層次信息（level ），只能存儲在結點中；（3）由于擴展結點不是按層進行的，計算結點所在分支的裝載上界時，要 用數組變量r記錄當前層以下的最大重量，這樣可隨時方便使用各層結點的裝載 上界。重要算法HeapNode H1000;struct bbnode bbnode *parent;/ 父結點指針int LChild; ;/當且僅當是父結點的左孩子時，取值為 1struct HeapNodebbnode *ptr;/活結點指針float uweight;/活結點的重量上限int level; ;MaxLoadi ng(float

12、 c, int n, int bestx) float r100,Ew,bestw=0; rn =0;for (int j=n-1; j > 0; j-)rj=rj+1 + wj+1;int i = 1; bbnode *E = 0; Ew = 0;/ 搜索子集空間樹while (i != n +1)/不在葉子上 if (Ew+wi<=c)/可行的左孩子 AddLiveNode(E,Ew+wi+ri,1,i+1); if (bestw<Ew+wi) bestw=Ew+wi;if(bestw<Ew+ri) AddLiveNode(E,Ew+ri,0,i+1); Delet

13、eMax(H,E);i=N.level;E=N.ptr; Ew=N.uweight-ri-1;for (int j=n ;j>O;j_)bestxj = E->LChild; E = E->pare nt;return Ew;AddLiveNode(float wt, in t lev,bb node *E, i nt ch)bbnode *b=new bbno de;b->pare nt=E;b->LChild=ch;HeapNode N;N.uweight=wt;N.level=lev;N.ptr=b;In sert(H,N);3.3測試結果與分析牡FJ為D貝

14、C耳OHE. . . QL.兇*恭DB.圜& -x g.鑒畫圖|當貝y <l&rmi nat*i> EranchLiriii tFIFOS&sr elk Java AppLicalion B： VprflgraiiVjivaVjreTVbLrkVj ivaw. eue (2013-1 分支限界FIFO算袪：輸入貨箱的亍數：5輸入第一艘貨船的載重量:SO輸入第二艘貨船的載重量：70輸入各個賞箱的質量：124 6 o o h h1 1 2 2 br TO-23圖3.2貨物裝載問題的解由圖可以看出，當輸入貨箱的個數為 5時，第一艘船的載重量為50,第二 艘船的載重

15、量為70時，每個貨箱的質量分別是12,14,16,20,20，得到如下圖的 結果。第四章 基于隊列式(FIFO)分支限界法解決貨物裝載問題4.1算法設計將此問題轉化為一艘船的最優化問題，問題的解空間為一個子集樹。也就是算法要考慮的所有物品的取、舍情況的組合，n個物品的取舍組合共2的N次 個分支，搜索子集樹是NP-復雜問題。如下圖所示，xi為1表示選取第i件物品， xi為0表示不選取第i件物品。搜索結點3,時 可以確定它不必被擴充為活結 點；因為擴展結點1后，就知道最大裝載量不會小于 50；而擴展節點3時，發 現此分支的“裝載上界”為 w2+w3=20<50無需搜索此分支，節點3不必入隊。

16、圖4-1 子集圖4.2數據結構設計用FIFO分支搜索所有的分支，并記錄已搜索分支的最優解，搜索完子集樹 也就找到出了問題的解。要想求出最優解，必須搜素出最優解，必須搜索到葉節 點。所以要記錄樹的層次，當層次為n+1時，搜索完全部葉節點，算法結束。不 同于回溯算法，分支搜索過程中活節點的“層”是需要標志飛，否則在入隊后就 無法識別節點所在的層。421程序流程圖呈tj l.T 二二圖4-2優先隊列限界法流程圖數據結構描述和算法float bestw,w100,bestx100; int n;Queue Q;struct QNode float weight;QNode *pare nt;QNode

17、 LChild;mai n() int c1,c2, n, s=0,i;in put(c1,c2, n);for(i=1;i<=n ;i+) in put(wi); s=s+wi;if (s<=c1 or s<=c2) print(“ need only one ship ” ); return;if (s>c1+c2)print( "no solution ” );return;MaxLoadi ng(c1);if (s-bestw <=c2); print( “The first ship loading ” , bestw, “ chose:” )

18、;for(i=1;i<=n ;i+)if (bestxi=1) print(i, “，” );print("換行符 The second ship loading ” , s-bestw, “ chose” );for(i=1;i<=n ;i+)if (bestxi=0) print(i, ”，” ); else print( "no solution ” )；MaxLoadi ng(i nt c) Qnode *E;/活結點隊列int i = 1;E-結點的層E= new QNode; add (Q,0) ;0 代表分層標記E->weight=0; E-

19、>pare nt =n ull; E->Lchild=0; add (Q,E); bestw=0; r=0; / E-結點中余下的重量Ew=E->weight;E-結點的重量for (int j=2;j<=n ;j+) r=r+ wj;while (true) /搜索子集空間樹 wt=Ew+wi; /檢查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,

20、E ) ; / 下一個 E-節點if (E=0)/層的尾部 if (Empty(Q ) add (Q, 0); Delete(Q,E); i+ ;r=r-wi; Ew=E->weight ;break;/層尾指針/下一個E-結點/ E-結點的層次/ E-結點中余下的重量/新的E-結點的重量/沿著從bestE到根的路徑構造bestxfor (j=n-1;j>O;j-) bestxj=bestE->LChild; /從 bool 轉換為 int bestE=bestE->pare nt;retur n bestw;4.3測試結果與分析請輸入貨箱的數呈：E諸輸入貨箱的質呈：1214162025諳輸入兩亍貨船的載重墾:5070|first: 50可裝重為：14 16 2 0second:37可裝重為:12 25圖4.3貨物裝載問題的解由結果可以看出，當貨箱的質量分別為 12 14 16 20 25時，兩個貨船的載 重量分別為50,70.由此算法可以得到第一艘船可以達到滿裝 14 16 20，第二 艘船可以裝剩下的37。第五章結論通過本次的算法設計，了解并熟練掌握了 FIFO分支限界搜索算法和優先隊 列分支限界算法的使