分支限界法解01背包問題

1、分支限界法解01背包問題學(xué)院：網(wǎng)研院姓名：XXX學(xué)號：2013XXXXXX1、 分支限界法原理分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間中滿足約束條件的所有解；而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法對解空間的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間。分支限界法的搜索策略是，在擴展結(jié)點處，先生成其

2、所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一擴展結(jié)點。為了有效地選擇下一擴展結(jié)點，加速搜索的進程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。常見的分支限界法有如下兩種：隊列式（FIFO）分支限界法：按照先進先出原則選取下一個節(jié)點為擴展節(jié)點?；罱Y(jié)點表是先進先出隊列。FIFO分支限界法搜索策略：一開始，根結(jié)點是唯一的活結(jié)點，根結(jié)點入隊。從活結(jié)點隊中取出根結(jié)點后，作為當(dāng)前擴展結(jié)點。對當(dāng)前擴展結(jié)點，先從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的

3、兒子加入活結(jié)點隊列中。再從活結(jié)點表中取出隊首結(jié)點（隊中最先進來的結(jié)點）為當(dāng)前擴展結(jié)點，重復(fù)上述過程，直到找到一個解或活結(jié)點隊列為空為止。LC（leastcost）分支限界法（優(yōu)先隊列式分支限界法）：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。活結(jié)點表是優(yōu)先權(quán)隊列，LC分支限界法將選取具有最高優(yōu)先級的活結(jié)點出隊列，成為新的擴展節(jié)點。優(yōu)先隊列式分支限界法搜索策略：對每一活結(jié)點計算一個優(yōu)先級（某些信息的函數(shù)值）；根據(jù)這些優(yōu)先級從當(dāng)前活結(jié)點表中優(yōu)先選擇一個優(yōu)先級最高（最有利）的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。再從活結(jié)點表中下一個優(yōu)

4、先級別最高的結(jié)點為當(dāng)前擴展結(jié)點，重復(fù)上述過程，直到找到一個解或活結(jié)點隊列為空為止。2、 01背包問題簡介01背包問題假設(shè)有一個容量為c的背包，有n件物品，每件物品有重量w和價值v,求解怎樣往背包里裝物品能夠在不超出背包容量c的情況下獲得最大價值(本實驗中物品的w和v都是大于0的實數(shù)，可以是整數(shù)也可以是浮點數(shù))。3、 FIFO分支限界法解01背包問題1 .算法輸入背包容量capacity、物品數(shù)量count、物品的重量數(shù)組weights和物品的價值數(shù)組values,根據(jù)物品單位價值(value/weight)從大到小構(gòu)造一個新數(shù)組，數(shù)組元素(OriginNode)有weight、value和va

5、luePerWeight屬性，根據(jù)該排序數(shù)組構(gòu)造問題的解空間樹(完全二叉樹)；定義一個FIFO隊列(隊列元素是節(jié)點，見下文)，隊列可以在隊尾插入節(jié)點和在隊頭刪除節(jié)點；定義節(jié)點(ArrayNode),節(jié)點是問題的解空間樹上的點，它的屬性有當(dāng)前價值currentValue、當(dāng)前重量currentWeight、上限價值upboundValue、節(jié)點對應(yīng)的選擇情況nodeChoses(0表示不選，1表示選，如“101”表示該節(jié)點選擇了物品1和物品3,沒有選擇物品2)和節(jié)點在問題解空間樹上的層次nodeCount(0n)；定義一個計算節(jié)點價值上限的函數(shù)upBound(),upBound函數(shù)的計算規(guī)章是：

6、價值上限=節(jié)點現(xiàn)有價值+背包剩余容量*剩余物品的最大單位重量價值定義一個全局的currentMaxValue記錄程序目前取得的最大價值；將一個空節(jié)點推入隊列，空節(jié)點的當(dāng)前價值、當(dāng)前重量、節(jié)點層次均為0,全局的currentMaxValue初始化為0,使用upBound函數(shù)計算幾點的價值上限并使用該屬性初始化節(jié)點的upboundValue屬性；當(dāng)隊列不為空時，一直重復(fù)下述操作：從隊首取得頭節(jié)點，如果頭節(jié)點的上限價值upboundValue比全局的currentMaxValue要大，貝表明頭節(jié)點的子節(jié)點中可能有最優(yōu)節(jié)點，取頭節(jié)點在問題的解空間樹上的左子節(jié)點和右子節(jié)點，若左子節(jié)點和右子節(jié)點的重量沒有

7、超出背包容量且它們的upboundValue大于全局的currentMaxValue,將該子節(jié)點插入隊尾，否則不插入，同時若子節(jié)點的當(dāng)前價值currentValue大于全局的currentMaxValue,更新currentMaxValue。如果頭結(jié)點的上限價值upboundValue比全局的currentMaxValue要小，則表明頭結(jié)點及其子節(jié)點不可能有最優(yōu)節(jié)點，將其舍棄。若頭結(jié)點的當(dāng)前價值currentValue正好等于全局的currentMaxValue且頭結(jié)點的層次nodeCount等于物品數(shù)量n,則表明頭結(jié)點是問題的解空間樹上的葉子，該頭結(jié)點可能就是最優(yōu)節(jié)點，將其存儲在全局的cur

8、rentMaxNode屬性中(隨著隊列遍歷的進行當(dāng)前存起來的節(jié)點仍可能被更優(yōu)的節(jié)點覆蓋)。當(dāng)隊列為空時，表明所有的可能情況已被處理，此時全局的currentMaxNode屬性指向了最優(yōu)的節(jié)點，該節(jié)點的currentvalue屬性即為背包問題的最優(yōu)解。2 .算法復(fù)雜度在最壞的情況下所有的節(jié)點都入隊，最后一個節(jié)點才是最優(yōu)解，這種情況下時間復(fù)雜度是指數(shù)階。最好的情況是只裝單位價值最大的物品，其余分支都不符合條件被截去這種情況下時間復(fù)雜度是常數(shù)時間。但分支限界法本質(zhì)上還是窮舉法，平均時間復(fù)雜度仍是指數(shù)階?？臻g復(fù)雜度的分析類似時間復(fù)雜度，也是指數(shù)階。3 .可能的改進在本次實驗中，即便取得了可能是最優(yōu)解的

9、問題空間樹上的葉子節(jié)點的時候仍然會遍歷其它節(jié)點以保證得到的是最優(yōu)解，當(dāng)對正確率的要求不是很高的時候，可以在取得第一個可能是最優(yōu)解的節(jié)點時候便停止算法。本次實驗使用的是FIFO分支限界法，若使用優(yōu)先隊列式分支限界法(LC),在空間復(fù)雜度上的性能肯定會得到改善，若不要求結(jié)果十分準(zhǔn)確，使用優(yōu)先隊列取得第一個可能節(jié)點時候便停止算法，則在時間復(fù)雜度上的性能應(yīng)該也能優(yōu)于FIFO分支限界(優(yōu)先隊列采取的是深度遍歷，能更快到達葉子節(jié)點)。4、 算法實現(xiàn)框架本次實驗使用的語言是java,OriginNode類用來按價值重量比構(gòu)造排序數(shù)組，sort方法用于數(shù)組排序(出于便于實現(xiàn)的考慮使用了冒泡排序，改成快速排序可

10、獲得更好的性能)。OriginNode(floatweight;floatvalue;floatvaluePerWeight;publicOriginNode(floatweightyfloatvaluf)thi5.weight=weightthis.value=this,valuePerMeight=value/weight;)H芭0排工讒wm室且二+HA大£小*工publicstaticvoidsort(Or£ginUodenodes)OrigifiMadetmp=null;far(inti-3;i<nodeshLength;in-)for(intj=i+-Ijj

11、<nodesilength;J*)if(n-odesfj.valuePerWeight>rrodesi.vjluePerlJeight)tmp=nodesi;nodesL=nodesJin-odesCJ=tmp;ArrayNode類用于構(gòu)造問題的解空間樹上的節(jié)點。cla5sArrayNode- FloatcurrentWei- floatcurrentvalue;- Floatupboundvalue;StringnodeChoLces;intnodE匚cu門t;publicArrayNcde(floatcurrentHeightjfloatcurrerrtValuejString

12、nodeCholc&sTintnod&Count)(this.CurrentLJelght=cu.rrentlrJelglrtjthis.currentValue=currenValuethis.nodechoices=nadeChoices;this.rodeCaurt=nodeC-ount;FIFOBBKnapsac疑是程序的主類，定義了currentMaxValue等屬性，起全局變量的作用供節(jié)點共同維護，upBound方法用于計算節(jié)點價值上限。publicclassFIFOBBKrapsackintcapacity；intcountjfloatweightsifloatv

13、alues;OriginNodeoriginNodes;floatcurrentMaxValue;ArrayNodecjrrenthaxNode;privatefloatupEound(ArrayModenode)floatweightLeft-this.capacity-node.currentWeightjfloatbound-node-currentvalue;intt-node.nodeCount*while(t<this.count&&originNodtst.weight<-weightLeft)weightiest-=orIginNodesft,wei

14、ghtybound+=originNodest.value；七"；if(t<this*count)bound4-=(originNodestxvalue/originNodestweiglit)*weightLeft;returnbound;publicstaticvoidinain(Stringargs)while(true)(在FIFOBBKnapsac蟆的main方法里定義了分支限界法的邏輯，截取主要部分如下。LinkedList<Arrayttode>arrayWodeList-newLinkedLi5t<ArrayH-ode>();ArrayN

15、odeheadNode=newArrayNode(&f*幻：headhode.upbQurrdalue=knapsack.upBcund(hadlJade)jknapsackxCurrentMaxValue=&knapsack+currenti-laxNcde=null;arrayNodeList,push(headMode);whil«(!a*rayNodeList.isEmptyO)|ArrayNodefirstNode=arrayHodaList.pop()if(firstNode.rodeCount=-knapsack.count&&first

16、Node.currentvalue=knapsack.currentMaxValue)knapsck(currenriaxhode=firstNode;continue;)if(firstNade.upboundValue>"knapsack,currerrtMaxValce*&firitNode.nodeCount<knapsack.court)ArrayJodeleftNode=newArrayN-ode(firstMode.currenfideiht+knapsack,origirirJadestfirstNode-nodeCount*weightj.fir

17、stNode.currentValue+knapsack.originNodesfir5tNod&*nodeCount.value,firstNadc.nodechoices+"liptfirstModenodeCount+1)jleftNod>upbcundValu?=knmp&mtk.upBound(le十七【和(1£)jif(leftNodecurr'entlJeight<=knepsackncapacityleftMods,upboundValue>knapsack.currenWaxValue)arrayiNedeLlst

18、.addfleftHode);if(IwftWod.curr0ntUalLi白>knapsack.currentMaxValue)knapsack,curren'axValde=l&ftN-odecurrentvalue；)rrayNoderightMode=newArr3yNocle(firstNadecurrentWeig.ht,firstNod«.currentValue>firstNade.ncdeChoices+*'5"jfirstNcde.nodeCount+1)jrightNode.upboundl'a1ue=kna

19、psack.upBound(rightFlode);iftrightMode.uphoundValue>=knapsack.current；axValue)arrayiNcdeList.add(rightNode);五、總結(jié)在本科的時候曾經(jīng)做過背包問題的項目，所以本次實驗我選擇了01背包問題該題目。但在做本次實驗之前，我對分支限界法的原理并不是很理解，經(jīng)過查看課件及網(wǎng)上查找資料，同時結(jié)合自己對回溯法等的理解，我對分支限界法有了一個較好的理解，知道了兩種主要的分支限界法及分支限界法如何應(yīng)用于解01背包問題。在查找資料的過程中，我查看了許多網(wǎng)上的別人的代碼實現(xiàn)，但大多都存在著問題或者混淆使用

20、了兩種分支限界法，最后通過參考別人的部分代碼以及結(jié)合自己對FIFO分支限界法的理解，使用了java語言完成了該實驗。通過本次試驗，我基本上掌握了分支限界法解0-1背包問題的原理，同時鍛煉了自己動手編寫及調(diào)試代碼的能力，收獲良多。附錄程序運行示例:*FIFOh豆詛，法鼻。1號里向罷產(chǎn)運*郭*一-左輪工當(dāng)巨姿工二二戛£1樣亙=-三通人片R或五：正充£3片回土1»-*注又把1鼻莊耳三；FEI-9S7523735022557399昌-T輪入E鼻學(xué)工三尸亙?nèi)?89的19431崎724416764三巨蒞戔=今亭土/笠壺：38S.0三里至三:294.0次8無d安言主跑二丁不主*

21、22.。50.095.02375,巧96,073.057.0S?t0填同步£44.072.&106439.®19.®59,g64,043,01d。1.電嘮捶由W:伺森三串出1段事丐：:1111191330代碼importjava.util.LinkedList;importjava.util.Scanner;publicclassFIFOBBKnapsackintcapacity;intcount;float口weights;floatvalues;OriginNodeoriginNodes;floatcurrentMaxValue;ArrayNodecu

22、rrentMaxNode;privatefloatupBound(ArrayNodenode)floatweightLeft=this.capacity-node.currentWeight;floatbound=node.currentValue;intt=node.nodeCount;while(t<this.count&&originNodest.weight<=weightLeft)weightLeft-=originNodest.weight;bound+=originNodest.value;t+;if(t<this.count)bound+=(o

23、riginNodest.value/originNodest.weight)*weightLeft;returnbound;publicstaticvoidmain(Stringargs)while(true)Scannerin=newScanner(System.in);FIFOBBKnapsackknapsack=newFIFOBBKnapsack();System.out.println("*FIFO分支限界法解01背包問題開始*");/輸入背包容量System.out.println("-請輸入背包容量(正整數(shù))并回車-");knapsack.c

24、apacity=in.nextInt();/輸入物品數(shù)量System.out.println("-請輸入物品數(shù)量(正整數(shù))并回車-");knapsack.count=in.nextInt();knapsack.weights=newfloatknapsack.count;knapsack.values=newfloatknapsack.count;/構(gòu)造物品重量數(shù)組System.out.println("-請輸入物品重量數(shù)組(空格隔開)并回車-");for(inti=0;i<knapsack.count;i+)knapsack.weightsi=i

25、n.nextFloat();/構(gòu)造物品價值數(shù)組System.out.println("-請輸入物品價值數(shù)組(空格隔開)并回車-");for(inti=0;i<knapsack.count;i+)knapsack.valuesi=in.nextFloat();/排序knapsack.originNodes=newOriginNodeknapsack.count;for(inti=0;i<knapsack.count;i+)knapsack.originNodesi=newOriginNode(knapsack.weightsi,knapsack.valuesi);

26、OriginNode.sort(knapsack.originNodes);/FIFO隊列LinkedList<ArrayNode>arrayNodeList=newLinkedList<ArrayNode>();ArrayNodeheadNode=newArrayNode(0,0,"",0);headNode.upboundValue=knapsack.upBound(headNode);knapsack.currentMaxValue=0;knapsack.currentMaxNode=null;arrayNodeList.push(headNo

27、de);while(!arrayNodeList.isEmpty()ArrayNodefirstNode=arrayNodeList.pop();if(firstNode.nodeCount=knapsack.count&&firstNode.currentValue=knapsack.currentMaxValue)knapsack.currentMaxNode=firstNode;continue;if(firstNode.upboundValue>=knapsack.currentMaxValue&&firstNode.nodeCount<kn

28、apsack.count)ArrayNodeleftNode=newArrayNode(firstNode.currentWeight+knapsack.originNodesfirstNode.nodeCount.weight,firstNode.currentValue+knapsack.originNodesfirstNode.nodeCount.value,firstNode.nodeChoices+"1",firstNode.nodeCount+1);leftNode.upboundValue=knapsack.upBound(leftNode);if(leftN

29、ode.currentWeight<=knapsack.capacity&&leftNode.upboundValue>knapsack.currentMaxValue)arrayNodeList.add(leftNode);if(leftNode.currentValue>knapsack.currentMaxValue)knapsack.currentMaxValue=leftNode.currentValue;ArrayNoderightNode=newArrayNode(firstNode.currentWeight,firstNode.current

30、Value,firstNode.nodeChoices+"0",firstNode.nodeCount+1);rightNode.upboundValue=knapsack.upBound(rightNode);if(rightNode.upboundValue>=knapsack.currentMaxValue)arrayNodeList.add(rightNode);System.out.println("背包能裝下的最大價值是："+knapsack.currentMaxNode.currentValue+"此時背包裝的重量是："+knapsack.currentMaxNode.currentWeight);System.out.println("物品的選擇情況是：")；System.out.print("物品重量：");for(inti=0;i<knapsack.count;i+)System.out.print(knapsack.originNodesi.weight+"&q