分支定界法背包.doc

《分支定界法背包.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、其實(shí)分支限界法理解了也很好實(shí)現(xiàn)，舉一個《算法設(shè)計(jì)與分析》上的例子。例：0/1背包問題。假設(shè)有4個物品，其重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量價(jià)值從大到小排序，結(jié)果如下：我們使用的啟發(fā)式函數(shù)為通過這個啟發(fā)式函數(shù)得到的一個解空間樹如下圖：可以對照一下步驟，具體的搜索過程如下：（紅色表示我的代碼實(shí)現(xiàn)）（1）在根結(jié)點(diǎn)1，沒有將任何物品裝入背包，因此，背包的重量和獲得的價(jià)值均為0，根據(jù)限界函數(shù)計(jì)算結(jié)點(diǎn)1的目標(biāo)函數(shù)值為10×10=100；　　(計(jì)算完之后推入隊(duì)列，作

2、為起始點(diǎn)）。（2）在結(jié)點(diǎn)2，將物品1裝入背包，因此，背包的重量為4，獲得的價(jià)值為40，目標(biāo)函數(shù)值為40+(10-4)×6=76，將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)3，沒有將物品1裝入背包，因此，背包的重量和獲得的價(jià)值仍為0，目標(biāo)函數(shù)值為10×6＝60，將結(jié)點(diǎn)3加入表PT中；　　（推出結(jié)點(diǎn)1，對選擇和不選擇物品1分別計(jì)算ub值，并推入隊(duì)列）（3）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索；　?。ǔ鲫?duì)ub值大的點(diǎn)）（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒有將物

3、品2裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)2相同，目標(biāo)函數(shù)值為40+(10-4)×5=70，將結(jié)點(diǎn)5加入表PT中；　　（重復(fù)結(jié)點(diǎn)1的操作并入隊(duì)新結(jié)點(diǎn)）（5）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)6，將物品3裝入背包，因此，背包的重量為9，獲得的價(jià)值為65，目標(biāo)函數(shù)值為65+(10-9)×4=69，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)7，沒有將物品3裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)5相同，目標(biāo)函數(shù)值為40+(10-4)×4＝64，將結(jié)點(diǎn)6加入表PT中；（7）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)

4、點(diǎn)6優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)8，將物品4裝入背包，因此，背包的重量為12，不滿足約束條件，將結(jié)點(diǎn)8丟棄；在結(jié)點(diǎn)9，沒有將物品4裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)6相同，目標(biāo)函數(shù)值為65；（9）由于結(jié)點(diǎn)9是葉子結(jié)點(diǎn)，同時結(jié)點(diǎn)9的目標(biāo)函數(shù)值是表PT中的極大值，所以，結(jié)點(diǎn)9對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束?！　。ㄅ袛嘟Y(jié)束并跳出）我實(shí)現(xiàn)的方法是先按單位密度排序優(yōu)先隊(duì)列，每次踢出ub值最大的，對排在這個點(diǎn)之后的點(diǎn)選擇或者不選擇分別進(jìn)行一次計(jì)算，得出相應(yīng)的ub，放入優(yōu)先隊(duì)列中。跳出的條件設(shè)定了兩個：1、當(dāng)踢出的最大ub在葉子結(jié)

5、點(diǎn)上時，結(jié)束。2、當(dāng)踢出的最大ub和v值相等時，結(jié)束。第一點(diǎn)顯而易見，現(xiàn)在說說第二點(diǎn)。當(dāng)ub和v相等的時候，可以這么理解，此時背包已經(jīng)被完全裝滿了，因此完全不用再繼續(xù)試下去了，對于剩下的物品，直接全都不選即可，不用再進(jìn)行計(jì)算。