分支定界法背包.doc

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

1、其實(shí)分支限界法理解了也很好實(shí)現(xiàn)，舉一個(gè)《算法設(shè)計(jì)與分析》上的例子。例：0/1背包問(wèn)題。假設(shè)有4個(gè)物品，其重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量?jī)r(jià)值從大到小排序，結(jié)果如下：我們使用的啟發(fā)式函數(shù)為通過(guò)這個(gè)啟發(fā)式函數(shù)得到的一個(gè)解空間樹(shù)如下圖：可以對(duì)照一下步驟，具體的搜索過(guò)程如下：（紅色表示我的代碼實(shí)現(xiàn)）（1）在根結(jié)點(diǎn)1，沒(méi)有將任何物品裝入背包，因此，背包的重量和獲得的價(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，沒(méi)有將物品1裝入背包，因此，背包的重量和獲得的價(jià)值仍為0，目標(biāo)函數(shù)值為10×6＝60，將結(jié)點(diǎn)3加入表PT中；　?。ㄍ瞥鼋Y(jié)點(diǎn)1，對(duì)選擇和不選擇物品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，不滿(mǎn)足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒(méi)有將物

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

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