分支定界法背包

其实分支限界法理解了也很好实现，举一个《算法设计与分析》上的例子。例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：我们使用的启发式函数为通过这个启发式函数得到的一个解空间树如下图：可以对照一下步骤，具体的搜索过程如下：（红色表示我的代码实现）（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100；(计算完之后推入队列，作为起始点）。（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)×6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入表PT中；（推出结点1，对选择和不选择物品1分别计算ub值，并推入队列）（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；（出队ub值大的点）（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)×5=70，将结点5加入表PT中；（重复结点1的操作并入队新结点）（5）在表PT中选取目标函数值取得极大的结点5优先进行搜索；（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)×4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)×4＝64，将结点6加入表PT中；（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索；（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；（9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。（判断结束并跳出）我实现的方法是先按单位密度排序优先队列，每次踢出ub值最大的，对排在这个点之后的点选择或者不选择分别进行一次计算，得出相应的ub，放入优先队列中。跳出的条件设定了两个：1、当踢出的最大ub在叶子结点上时，结束。2、当踢出的最大ub和v值相等时，结束。第一点显而易见，现在说说第二点。当ub和v相等的时候，可以这么理解，此时背包已经被完全装满了，因此完全不用再继续试下去了，对于剩下的物品，直接全都不选即可，不用再进行计算。