分支限界法解01背包问题.docx

分支限界法解01背包问题
学院：网研院 姓名：XXX 学号：2013XXXXXX

分支限界法原理
分支限界法类似于HYPERLINK"http://www.cnblogs.com/ttltry-air/archive/2012/07/31/2617137.html"回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解；而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。
分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
常见的分支限界法有如下两种：
队列式（FIFO）分支限界法：按照先进先出原则选取下一个节点为扩展节点。活结点表是先进先出队列。FIFO分支限界法搜索策略：
一开始，根结点是唯一的活结点，根结点入队。
从活结点队中取出根结点后，作为当前扩展结点。
对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。
再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，重复上述过程，直到找到一个解或活结点队列为空为止。
LC（leastcost）分支限界法（优先队列式分支限界法）：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。活结点表是优先权队列，LC分支限界法将选取具有最高优先级的活结点出队列，成为新的扩展节点。优先队列式分支限界法搜索策略：
对每一活结点计算一个优先级（某些信息的函数值）；
根据这些优先级从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
再从活结点表中下一个优先级别最高的结点为当前扩展结点，重复上述过程，直到找到一个解或活结点队列为空为止。
01背包问题简介
01背包问题假设有一个容量为c的背包，有n件物品，每件物品有重量w和价值v，求解怎样往背包里装物品能够在不超出背包容量c的情况下获得最大价值（本实验中物品的w和v都是大于0的实数，可以是整数也可以是浮点数）。
FIFO分支限界法解01背包问题
算法
输入背包容量capacity、物品数量count、物品的重量数组weights和物品的价值数组values，根据物品单位价值（value/weight）从大到小构造一个新数组，数组元素(OriginNode)有weight、value和valuePerWeight属性，根据该排序数组构造问题的解空间树（完全二叉树）；
定义一个FIFO队列(队列元素是节点，见下文)，队列可以在队尾插入节点和在队头删除节点；
定义节点（ArrayNode），节点是问题的解空间树上的点，它的属性有当前价值currentValue、当前重量currentWeight、上限价值upboundValue、节点对应的选择情况nodeChoses（0表示不选，1表示选，如“101”表示该节点选择了物品1和物品3，没有选择物品2）和节点在问题解空间树上的层次nodeCount(0~n)；
定义一个计算节点价值上限的函数upBound()，upBound函数的计算规章是：
价值上限=节点现有价值+背包剩余容量*剩余物品的最大单位重量价值
定义一个全局的currentMaxValue记录程序目前取得的最大价值；
将一个空节点推入队列，空节点的当前价值、当前重量、节点层次均为0，全局的currentMaxValue初始化为0，使用upBound函数计算几点的价值上限并使用该属性初始化节点的upboundValue属性；
当队列不为空时，一直重复下述操作：从队首取得头节点，如果头节点的上限价值upboundValue比全局的currentMaxValue要大，则表明头节点的子节点中可能有最优节点，取头节点在问题的解空间树上的左子节点和右子节点，若左子节点和右子节点的重量没有超出背包容量且它们的upboundValue大于全局的currentMaxValue，将该子节点插入队尾，否则不插入，同时若子节点的当前价值currentValue大于全局的currentMaxValue