分支限界算法

算法基本思想

按广度优先的顺序搜索解空间树，若结点的限界值不在限界范围内则实行剪枝，否则压入待处理结点表。

基本步骤：
1) 确定问题的上下界。通常采用贪心算法得到上界；用理想状态分析得到下界。
2) 计算部分解的下界。即已确定部分解的情况下，估算能得到的最优解，通常分两部分计算：已确定部分直接计算；未确定部分采用理想状态计算。
3) 按广度优先的顺序搜索解空间树，每次从PT表中选择最优结点进行展开。每搜索一个结点，计算该结点的下界，若超出已确定的上下界，则实行剪枝；否则压入PT表等待展开。

多段图最短路径问题

基本思想：

确定问题的界

采用贪心算法得到问题的上界；
每段最短边之和作为下界

部分解的下界

L1部分为已确定部分路径长度；

L2由两部分组成：
1) 尾结点往下走一步的最短边
2) 除已确定结点外，取各段最短边之和

解题思路：

0 -> 1 = 20 =》 4（已确定） + 8（下一步最短） + (5 + 3)（各段最短边） = 20

0/1背包问题

基本思想：

确定问题的界

采用贪心算法单位价值最大优先策略得到问题的下界；
剩余空间填满未确定物品中单位价值最高的物品所得到的价值作为问题上界

部分解的下界

L1部分为已确定放进包里的物品价值；
L2部分为剩余空间填满未确定物品中单位价值最高的物品所得到的价值

第一个结点什么都不放，ub = 0 + (10 - 0) * V1+1/Wi+1 (10) = 100

第二个结点放入物品1，ub = 40 + (10 - 4) * 6 = 76

任务分配问题

贪心法：2 + 6 + 1 + 4 = 14
最优解：2 + 3 + 1+ 4 = 10

故范围为：[10,14]