分支限界法的优先队列方式求解.pdf

《分支限界法的优先队列方式求解.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ABCGDEFHIJKLMNO分支限界法的优先队列方式求解0-1背包问题中国民航大学计算机科学与技术学院刘东楠1505040分支限界法的优先队列方式求解0-1背包问题0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？解题步骤：在算法中，算法首先检查当前扩展节点的左儿子的可行性。如果左儿Step1：搜索解空间建立二叉树，从根节点A开始。子节点是可行节点，则将它加入到子集数和活节点优先队列中。当前Step2：广度优先遍历二叉树，并用极大堆表示活

2、节扩展节点的右儿子一定是可行节点，点的优先级，选取扩展节点，找出可行解。仅当右儿子满足上界约束时才将它加入子集数和活节点优先队列。Step3：找出最优解。A10BCBC分支限界法的优先队列方式求解0-1背包问题应用实例：给定3种物品和一背包。物品重量是wi={16，15，15}，其价值vi={48，30，30}，背包的容量为c=30。问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？参数解释：Acp：当前装包价值cw：当前装包重量vupcp(Ccw)i1BCup：价值上界wi1bestx：bestx[i]=1最优解

3、中有物品iGDEF物品cpcwcp/cw148163HIJKLMNO230152330152分支限界法的优先队列方式求解0-1背包问题cw=0cp=0up=9010cw=16cp=48cw=0cp=0up=76up=901010cw=31cw=16cp=48cw=15cp=30cw=0cp=0无效解up=76up=60up=90101010cw=31cw=16cp=48cw=15cp=30cw=0cp=0无效解up=76可行解up=60可行解up=90可行解cw=30cp=60cw=15cp=30up=60可行解up=60可行解判断最优解：

4、寻找up=cp的叶子，此时背包被完全装满，或者寻找cp和up差距最小的叶子。分支限界法的优先队列方式求解0-1背包问题算法对比：利用分支限界法求解0-1背包问题与回溯法的区别-求解目标不同：一般而言，回溯法的求解目标是找出解空间树中满足的约束条件的所有解，而分支限界法的求解目标则是尽快的找出满足约束条件的一个解。-搜索方法不同：回溯法使用深度优先方法搜索，而分支限界一般用宽度优先或最佳优先方法来搜索。-对扩展结点的扩展方式不同：分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。-存储空间

5、的要求不同：分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。