分支限界法解01背包問題

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

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

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

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

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

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

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

8、的解空間樹上的葉子，該頭結(jié)點(diǎn)可能就是最優(yōu)節(jié)點(diǎn)，將其存儲(chǔ)在全局的currentMaxNode屬性中(隨著隊(duì)列遍歷的進(jìn)行當(dāng)前存起來的節(jié)點(diǎn)仍可能被更優(yōu)的節(jié)點(diǎn)覆蓋)。l 當(dāng)隊(duì)列為空時(shí)，表明所有的可能情況已被處理，此時(shí)全局的currentMaxNode屬性指向了最優(yōu)的節(jié)點(diǎn)，該節(jié)點(diǎn)的currentValue屬性即為背包問題的最優(yōu)解。2. 算法復(fù)雜度在最壞的情況下所有的節(jié)點(diǎn)都入隊(duì)，最后一個(gè)節(jié)點(diǎn)才是最優(yōu)解，這種情況下時(shí)間復(fù)雜度是指數(shù)階。最好的情況是只裝單位價(jià)值最大的物品，其余分支都不符合條件被截去這種情況下時(shí)間復(fù)雜度是常數(shù)時(shí)間。但分支限界法本質(zhì)上還是窮舉法，平均時(shí)間復(fù)雜度仍是指數(shù)階。空間復(fù)雜度的分析類似時(shí)間復(fù)

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

10、ort方法用于數(shù)組排序（出于便于實(shí)現(xiàn)的考慮使用了冒泡排序，改成快速排序可獲得更好的性能）。ArrayNode類用于構(gòu)造問題的解空間樹上的節(jié)點(diǎn)。FIFOBBKnapsack類是程序的主類，定義了currentMaxValue等屬性，起全局變量的作用供節(jié)點(diǎn)共同維護(hù)，upBound方法用于計(jì)算節(jié)點(diǎn)價(jià)值上限。在FIFOBBKnapsack類的main方法里定義了分支限界法的邏輯，截取主要部分如下。五、 總結(jié)在本科的時(shí)候曾經(jīng)做過背包問題的項(xiàng)目，所以本次實(shí)驗(yàn)我選擇了01背包問題該題目。但在做本次實(shí)驗(yàn)之前，我對(duì)分支限界法的原理并不是很理解，經(jīng)過查看課件及網(wǎng)上查找資料，同時(shí)結(jié)合自己對(duì)回溯法等的理解，我對(duì)分支限

11、界法有了一個(gè)較好的理解，知道了兩種主要的分支限界法及分支限界法如何應(yīng)用于解01背包問題。在查找資料的過程中，我查看了許多網(wǎng)上的別人的代碼實(shí)現(xiàn)，但大多都存在著問題或者混淆使用了兩種分支限界法，最后通過參考別人的部分代碼以及結(jié)合自己對(duì)FIFO分支限界法的理解，使用了java語言完成了該實(shí)驗(yàn)。通過本次試驗(yàn)，我基本上掌握了分支限界法解0-1背包問題的原理，同時(shí)鍛煉了自己動(dòng)手編寫及調(diào)試代碼的能力，收獲良多。附錄程序運(yùn)行示例：代碼import java.util.LinkedList;import java.util.Scanner;public class FIFOBBKnapsack int capa

12、city;int count;float weights;float values;OriginNode originNodes;float currentMaxValue;ArrayNode currentMaxNode;private float upBound(ArrayNode node) float weightLeft = this.capacity - node.currentWeight;float bound = node.currentValue;int t = node.nodeCount;while (t this.count & originNodest.weight

13、 = weightLeft) weightLeft -= originNodest.weight;bound += originNodest.value;t+;if (t this.count)bound += (originNodest.value / originNodest.weight)* weightLeft;return bound;public static void main(String args) while (true) Scanner in = new Scanner(System.in);FIFOBBKnapsack knapsack = new FIFOBBKnap

14、sack();System.out.println(*FIFO分支限界法解01背包問題開始*);/ 輸入背包容量System.out.println(-請(qǐng)輸入背包容量（正整數(shù)）并回車-);knapsack.capacity = in.nextInt();/ 輸入物品數(shù)量System.out.println(-請(qǐng)輸入物品數(shù)量（正整數(shù)）并回車-);knapsack.count = in.nextInt();knapsack.weights = new floatknapsack.count;knapsack.values = new floatknapsack.count;/ 構(gòu)造物品重量數(shù)組Sy

15、stem.out.println(-請(qǐng)輸入物品重量數(shù)組（空格隔開）并回車-);for (int i = 0; i knapsack.count; i+) knapsack.weightsi = in.nextFloat();/ 構(gòu)造物品價(jià)值數(shù)組System.out.println(-請(qǐng)輸入物品價(jià)值數(shù)組（空格隔開）并回車-);for (int i = 0; i knapsack.count; i+) knapsack.valuesi = in.nextFloat();/ 排序knapsack.originNodes = new OriginNodeknapsack.count;for (int

16、i = 0; i knapsack.count; i+) knapsack.originNodesi = new OriginNode(knapsack.weightsi,knapsack.valuesi);OriginNode.sort(knapsack.originNodes);/ FIFO隊(duì)列LinkedList arrayNodeList = new LinkedList();ArrayNode headNode = new ArrayNode(0, 0, , 0);headNode.upboundValue = knapsack.upBound(headNode);knapsack.

17、currentMaxValue = 0;knapsack.currentMaxNode = null;arrayNodeList.push(headNode);while (!arrayNodeList.isEmpty() ArrayNode firstNode = arrayNodeList.pop();if (firstNode.nodeCount = knapsack.count& firstNode.currentValue = knapsack.currentMaxValue) knapsack.currentMaxNode = firstNode;continue;if (firs

18、tNode.upboundValue = knapsack.currentMaxValue& firstNode.nodeCount knapsack.count) ArrayNode leftNode = new ArrayNode(firstNode.currentWeight+ knapsack.originNodesfirstNode.nodeCount.weight,firstNode.currentValue+ knapsack.originNodesfirstNode.nodeCount.value,firstNode.nodeChoices + 1,firstNode.node

19、Count + 1);leftNode.upboundValue = knapsack.upBound(leftNode);if (leftNode.currentWeight knapsack.currentMaxValue) arrayNodeList.add(leftNode);if (leftNode.currentValue knapsack.currentMaxValue) knapsack.currentMaxValue = leftNode.currentValue;ArrayNode rightNode = new ArrayNode(firstNode.currentWei

20、ght, firstNode.currentValue,firstNode.nodeChoices + 0,firstNode.nodeCount + 1);rightNode.upboundValue = knapsack.upBound(rightNode);if (rightNode.upboundValue = knapsack.currentMaxValue) arrayNodeList.add(rightNode);System.out.println(背包能裝下的最大價(jià)值是：+ knapsack.currentMaxNode.currentValue + 此時(shí)背包裝的重量是：+

21、knapsack.currentMaxNode.currentWeight);System.out.println(物品的選擇情況是：);System.out.print(物品重量：);for (int i = 0; i knapsack.count; i+) System.out.print(knapsack.originNodesi.weight + );System.out.println();System.out.print(物品價(jià)值：);for (int i = 0; i knapsack.count; i+) System.out.print(knapsack.originNodesi.value + );System.out.println();System.out.print(選擇情況（0表示不選1表示選）：);System.out.println(knapsack.currentMaxNode.nodeChoices);/ 物品的重量一定不為0，價(jià)值可以是0cl