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