【正文】 p[i]/w[i] * cleft。 b += p[i]。amp。 // 剩余容量 Typep b = cp。當擴展到葉節(jié)點時即為問題的最優(yōu)值。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。 ?在優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝入背包的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。 } 構(gòu)造當前最優(yōu)解 2021年 11月 12日 46 提綱 一、分支限界法的基本思想 二、單源最短路徑問題 三、裝載問題 四、 01背包問題 五、最大團問題 六、旅行售貨員問題 2021年 11月 12日 47 問題定義 ?給定 n種物品和一個背包，物品 i的重量是 wi，價值 pi,背包容量為 C， 問如何選擇裝入背包的物品，使裝入背包中的物品的總價值最大？ ?對于每種物品只能選擇完全裝入或不裝入，一個物品至多裝入一次。 E = Eparent。 j 0。 //優(yōu)先權(quán) uweight = Ew + r[ i 1]。 E = Nptr。//取下一擴展結(jié)點 DeletMax(N)。 } AddLiveNode(E, Ew+r[ i ], false, i+1)。該最優(yōu)解所相應(yīng)的路徑可由子集樹中從該葉結(jié)點開始沿結(jié)點父指針逐步構(gòu)造出來。如果此時不存在下一個擴展結(jié)點，則相應(yīng)的問題無可行解。擴展結(jié)點的右兒子結(jié)點總是可行的，故直接插入子集樹的最大堆中。 //擴展結(jié)點所相應(yīng)的載重量 2021年 11月 12日 43 優(yōu)先隊列式分支限界法 While循環(huán)體產(chǎn)生當前擴展結(jié)點的左右兒子結(jié)點。 // 當前擴展結(jié)點所處的層 bbnode * E =0。 j) r[j]= r[j+1] + w[j+1]。 for(int j = n1。 //定義剩余重量數(shù)組 r int * r = (int*)malloc(sizeof(int)*(n+1)) 。 head ptr =NULL 。 } headlevel = 0 。 if(head ==NULL) {printf(沒有足夠的空間分配 \n) 。 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 )。 j 0。 r[n] = 0。算法開始時， i＝ 1， Ew＝ 0，子集樹的根結(jié)點是擴展結(jié)點。 2021年 11月 12日 41 第 i十 1層結(jié)點的剩余重量 r[i]定義為 r[i]＝ 。第二種策略在算法的搜索進程中保存當前已構(gòu)造出的部分解空間樹，這樣在算法確定了達到最優(yōu)值的葉結(jié)點時，就可以在解空間樹中從該葉結(jié)點開始向根結(jié)點回溯，構(gòu)造出相應(yīng)的最優(yōu)解。 2021年 11月 12日 40 上述策略可以用兩種不同的方式實現(xiàn)。 ?在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)點成為當前擴展結(jié)點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解。以結(jié)點 x為根的子樹中所有結(jié)點相應(yīng)的路徑的載重量不超過它的優(yōu)先級?；罱Y(jié)點 x在優(yōu)先隊列中的優(yōu)先級定義為從根結(jié)點到結(jié)點 x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。 } 找到最優(yōu)值后，可以根據(jù) parent回溯到根結(jié)點，找到最優(yōu)解。 j) { bestx[j] = bestELChild。 2021年 11月 12日 38 // 構(gòu)造當前最優(yōu)解 for (int j = n 1。 // 結(jié)點所相應(yīng)的載重量 } 為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲相應(yīng)子集樹中從活結(jié)點到根結(jié)點的路徑。 // 指向父結(jié)點的指針 bool LChild。 // 進入下一層 r = w[i] 。 // 同層結(jié)點尾部標志 (Ew)。 // 取下一擴展結(jié)點 if (Ew == 1) { // 同層結(jié)點尾部 if (()) return bestw。 i n) (Ew)。 } // 檢查右兒子結(jié)點 if (Ew + r bestw amp。 // 左兒子結(jié)點的重量 if (wt = c) { // 可行結(jié)點 if (wt bestw) bestw = wt。 // 可能含最優(yōu)解 (Ew)。amp。 // 加入活結(jié)點隊列 if (i n) (wt)。 2021年 11月 12日 35 算法的改進 // 檢查左兒子結(jié)點 Type wt = Ew + w[i]。也就是說，此時右子樹測試不起作用。 算法 MaxLoading初始時將 bestw置為 0，直到搜索到第一個葉結(jié)點時才更新 bestw。設(shè) bestw是當前最優(yōu)解； ew是當前擴展結(jié)點所相應(yīng)的重量； r是剩余集裝箱的重量。 // 取下一擴展結(jié)點 i++。 (1)。 // x[i] = 0 (Ew)。 2021年 11月 12日 33 隊列式分支限界法 while (true) { // 檢查左兒子結(jié)點 if (Ew + w[i] = c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n)。 當取出的元素是 1時 ， 再判斷當前隊列是否為空 。 2個兒子結(jié)點都產(chǎn)生后 ， 當前擴展結(jié)點被舍棄 。 如果是則將其加入到活結(jié)點隊列中 。 Ew存儲當前擴展結(jié)點所相應(yīng)的重量。此時活結(jié)點隊列為空。 } else (wt)。Q,Type wt,Type amp。當 i＜ n時，當前活結(jié)點是一個內(nèi)部結(jié)點，應(yīng)加入到活結(jié)點隊列中。由于葉結(jié)點不會被進一步擴展，因此不必加入到活結(jié)點隊列中。該函數(shù)首先檢查 i是否等于 n。 當其值為 — 1時，表示隊列已到達解空間樹同一層結(jié)點的尾部。其中隊列 Q用于存放活結(jié)點表。 2021年 11月 12日 28 解裝載問題的隊列式分支限界法只求出所要求的最優(yōu)值，稍后將進一步討論求出最優(yōu)解。 ?容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。} // 優(yōu)先隊列空 } } 頂點 i和 j間有邊，且此路徑長小于原先從源點到 j的路徑長 2021年 11月 12日 24 實例 計算從源頂點 1到其它頂點間最短路徑 2021年 11月 12日 25 12 30 V2 V0 V1 V4 V3 3 8 25 4 20 5 10 計算從源頂點 V0 到其它頂點間最短路徑 練習 2021年 11月 12日 26 提綱 一、分支限界法的基本思想 二、單源最短路徑問題 三、裝載問題 四、 01背包問題 五、最大團問題 六、旅行售貨員問題 2021年 11月 12日 27 問題定義 ?有一批共個集裝箱要裝上 2艘載重量分別為C1和 C2的輪船，其中集裝箱 i的重量為 wi，且 ∑wi≤C1+C2 ?裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這 2艘輪船。} try {(E)。 =dist[j]。 // 加入活結(jié)點優(yōu)先隊列 MinHeapNodeType N。(+c[][j]dist[j])) { // 頂點 i到頂點 j可達，且滿足控制約束 dist[j]=+c[][j]。 j++) if ((c[][j]inf)amp。 B A優(yōu)于 B， B可剪枝 經(jīng)過不同的路徑到達相同的頂點 A 2021年 11月 12日 23 算法描述 while (true) { for (int j = 1。故可將后一條路