【文章內容簡介】 確保右子樹成功剪枝，應該在算法每一次進入左子樹的時候更新 bestw的值。 2021年 11月 12日 35 算法的改進 // 檢查左兒子結點 Type wt = Ew + w[i]。 // 左兒子結點的重量 if (wt = c) { // 可行結點 if (wt bestw) bestw = wt。 // 加入活結點隊列 if (i n) (wt)。 } 提前更新 bestw // 檢查右兒子結點 if (Ew + r bestw amp。amp。 i n) (Ew)。 // 可能含最優(yōu)解 (Ew)。 // 取下一擴展結點 右兒子剪枝 2021年 11月 12日 36 算法的改進 while (true) { // 檢查左兒子結點 Type wt = Ew + w[i]。 // 左兒子結點的重量 if (wt = c) { // 可行結點 if (wt bestw) bestw = wt。 // 加入活結點隊列 if (i n) (wt)。 } // 檢查右兒子結點 if (Ew + r bestw amp。amp。 i n) (Ew)。 // 可能含最優(yōu)解 (Ew)。 // 取下一擴展結點 if (Ew == 1) { // 同層結點尾部 if (()) return bestw。 (1)。 // 同層結點尾部標志 (Ew)。 // 取下一擴展結點 i++。 // 進入下一層 r = w[i] 。 } } } 2021年 11月 12日 37 構造最優(yōu)解 class QNode { QNode *parent。 // 指向父結點的指針 bool LChild。 // 左兒子標志 Type weight。 // 結點所相應的載重量 } 為了在算法結束后能方便地構造出與最優(yōu)值相應的最優(yōu)解，算法必須存儲相應子集樹中從活結點到根結點的路徑。為此目的，可在每個結點處設置指向其父結點的指針，并設置左、右兒子標志。 2021年 11月 12日 38 // 構造當前最優(yōu)解 for (int j = n 1。 j 0。 j) { bestx[j] = bestELChild。 bestE = bestEparent。 } 找到最優(yōu)值后，可以根據 parent回溯到根結點，找到最優(yōu)解。 構造最優(yōu)解 2021年 11月 12日 39 ?解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結點表?；罱Y點 x在優(yōu)先隊列中的優(yōu)先級定義為從根結點到結點 x的路徑所相應的載重量再加上剩余集裝箱的重量之和。 ?優(yōu)先隊列中優(yōu)先級最大的活結點成為下一個擴展結點。以結點 x為根的子樹中所有結點相應的路徑的載重量不超過它的優(yōu)先級。子集樹中葉結點所相應的載重量與其優(yōu)先級相同。 ?在優(yōu)先隊列式分支限界法中，一旦有一個葉結點成為當前擴展結點，則可以斷言該葉結點所相應的解即為最優(yōu)解。此時可終止算法 。 2021年 11月 12日 40 上述策略可以用兩種不同的方式實現。第一種方式在結點優(yōu)先隊列的每一個活結點中保存從解空間樹的根結點到該活結點的路徑，在算法確定了達到最優(yōu)值的葉結點時，就在該葉結點處同時得到相應的最優(yōu)解。第二種策略在算法的搜索進程中保存當前已構造出的部分解空間樹，這樣在算法確定了達到最優(yōu)值的葉結點時，就可以在解空間樹中從該葉結點開始向根結點回溯，構造出相應的最優(yōu)解。在下面的算法中，我們采用第二種策略。 2021年 11月 12日 41 第 i十 1層結點的剩余重量 r[i]定義為 r[i]＝ 。 變量 E指向子集樹中當前擴展結點 , Ew是相應的重量。算法開始時， i＝ 1， Ew＝ 0，子集樹的根結點是擴展結點。 //定義剩余重量數組 r int * r = (int*)malloc(sizeof(int)*(n+1)) 。 r[n] = 0。 for(int j = n1。 j 0。 j) r[j]= r[j+1] + w[j+1]。 2021年 11月 12日 42 int MaxLoading(int w[ ], int c, int n) {//優(yōu)先隊列式分支限界法，返回最優(yōu)載重量， bestx返回最優(yōu)解 //定義最大堆的容量為 1000 // MaxHeap HeapNode Type H( 1000 )。 head = (HeapNode*)malloc(sizeof(HeapNode)) 。 if(head ==NULL) {printf(沒有足夠的空間分配 \n) 。 return 1 。 } headlevel = 0 。 headnext = NULL 。 head ptr =NULL 。 headuweight = 0 。 //定義剩余重量數組 r int * r = (int*)malloc(sizeof(int)*(n+1)) 。 r[n] = 0。 for(int j = n1。 j 0。 j) r[j]= r[j+1] + w[j+1]。 //初始化 int i = 1。 // 當前擴展結點所處的層 bbnode * E =0。 //當前擴展結點 int Ew = 0。 //擴展結點所相應的載重量 2021年 11月 12日 43 優(yōu)先隊列式分支限界法 While循環(huán)體產生當前擴展結點的左右兒子結點。如果當前擴展結點的左兒子結點是可行結點，即它所相應的重量末超過船載容量，則將它加入到子集樹的第 i十1層上，并插入最大堆。擴展結點的右兒子結點總是可行的，故直接插入子集樹的最大堆中。接著算法從最大堆中取出最大元素作為下一個擴展結點。如果此時不存在下一個擴展結點，則相應的問題無可行解。如果下一個擴展結點是一個葉結點，即子集樹中第 n十 1層結點，則它相應的可行解為最優(yōu)解。該最優(yōu)解所相應的路徑可由子集樹中從該葉結點開始沿結點父指針逐步構造出來。具體算法可描述如下： 2021年 11月 12日 44 while( i!=n+1 ) { //非葉結點 //檢查當前擴展結點的兒子結點 if(Ew+w[ i ] = c ){ //左兒子結點為可行結點 AddLiveNode(E, Ew + w[ i ] + r[ i ], true, i +1)。 } AddLiveNode(E, Ew+r[ i ], false, i+1)。 //右兒子結點 HeapNode* N 。//取下一擴展結點 DeletMax(N)。 //非空 i = Nlevel。 E = Nptr。 Ew = Nuweightr[i1]。 //優(yōu)先權 uweight = Ew + r[ i 1]。 } 2021年 11月 12日 45 for(j = n 。 j 0。j){ //構造當前最優(yōu)解 { bestx[j] = E LChild。 E = Eparent。 } return Ew。 } 構造當前最優(yōu)解 2021年 11月 12日 46 提綱 一、分支限界法的基本思想 二、單源最短路徑問題 三、裝載問題 四、 01背包問題 五、最大團問題 六、旅行售貨員問題 2021年 11月 12日 47 問題定義 ?給定 n種物品和一個背包，物品 i的重量是 wi，價值 pi,背包容量為 C， 問如何選擇裝入背包的物品，使裝入背包中的物品的總價值最大？ ?對于每種物品只能選擇完全裝入或不裝入，一個物品至多裝入一次。 2021年 11月 12日 48 算法思想