分支限界法

分支限界法的性质

• 广度优先或最小耗费（最大效益）优先的方式搜索解空间树

• 先入先出队列式分支限界

• 优先队列式分支限界

分支限界法和回溯法的关系

• 搜索方式

• 解题目标

分支限界法例子

0-1背包问题：（队列式分支限界法）

题目：

0-1背包问题定义如下：

n=3, c=5, w={2,3,2}, v={2,2,3} 通过完成下面的表格，给出用队列式分支限界法解决这个问题时的解题过程 最优值和最优解分别是什么？

答案：

答题步骤：

0. 画出解空间树（左1右0）
1. 初始化根节点
2. 按照广度优先的方式入队（只入队没有超背包容量且剩余价值比bestv大的节点）
3. 按照队列先进先出原则
4. 遇到叶子节点则更新bestv及bestx

0-1背包问题：（优先队列式分支限界法）

问题：

0-1背包问题定义如下： n=3, c=5, w={2,3,2}, v={2,2,3}

通过完成下面的表格，给出用（优化后的）优先队列式分支限界法解决这个问题时的解题过程， 优先级为背包中物品单位重量的价值(假设重量为0时单位重量为的价值为0） 最优值和最优解分别是什么？

答案：

解题步骤： 基本步骤跟队列式分支限界法一致，在元素入队后，计算入队节点单位价值，并按照节点从到到小出队。 只入队没有超背包容量且剩余价值比bestv大的节点