资源描述：
《天津科技大学算法设计与分析第9章分支限界法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9章分支限界法9.1概述9.2图问题中的分支限界法9.3组合问题中的分支限界法8/17/20211算法分析与设计--分支限界法9.1概述9.1.1解空间树的动态搜索（2）9.1.2分支限界法的设计思想9.1.3分支限界法的时间性能8/17/20212算法分析与设计--分支限界法分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]。9.1.1解空间树的动态搜索（2）按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值。如果某孩
2、子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。8/17/20213算法分析与设计--分支限界法随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解
3、。否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。8/17/20214算法分析与设计--分支限界法例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)1440102742635255431248/17/202
4、15算法分析与设计--分支限界法应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目标函数的界[40,100]。限界函数为：8/17/20216算法分析与设计--分支限界法×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70
5、w=9,v=65ub=69w=4,v=40ub=64w=12无效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包问题8/17/20217算法分析与设计--分支限界法分支限界法求解0/1背包问题，其搜索空间如上图所示，具体的搜索过程如下：（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100；（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)×6=76，将结点2加入待处理结点
6、表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入表PT中；（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；8/17/20218算法分析与设计--分支限界法（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)×5=70，将结点5加入表PT中；（5）在表PT中选取目标函数值取得极大的结点5优先进行搜索；（6）在结
7、点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)×4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)×4＝64，将结点6加入表PT中；8/17/20219算法分析与设计--分支限界法（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索；（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相
8、同，目标函数值为65；（9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。8/17/202110算法分析与设计--分支限界法9.1.2分支限界法的设计思想假设求解最大化问题，解向量为X=(x1,x2,…,xn)
