资源描述：
《第6章 分支限界法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第6章分支限界法1学习要点理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法2通过应用范例学习分支限界法的设计策略（1）0-1背包问题（2）旅行售货员问题（3）单源最短路径问题（4）装载问题（5）布线问题36.1分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或
2、以最小耗费（最大效益）优先的方式搜索解空间树。46.1分支限界法的基本思想此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。两个重要机制：产生分支（解空间树）产生一个界限，能够终止许多分支（剪枝）56.1分支限界法的基本思想常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（F
3、IFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。常用堆来实现优先队列6分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。依次从表PT中选取使目标函数的值取得极
4、值的结点成为当前扩展结点，重复上述过程，直到找到最优解。6.2解空间树的动态搜索7随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。6.2解空间树的动态搜索8例：0/1背包问题。假
5、设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)1440102742635255431249应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目标函数的界[40,100]。限
6、界函数为：已装入价值剩余容量剩下物品最大单位价值10×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包问题W=10,n=4w[i]=(4,7,5,3)v[i]=(40,42,25,12)11分支限界法求解0/1背包问题，其搜索空间如前图所示，具体的搜索过程如下：（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的
7、目标函数值为10×10=100；（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)×6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入表PT中；（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；12（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)×5=70，将
8、结点5加入表PT中；（5
