《分支与限界.ppt》由会员分享，可在线阅读，更多相关《分支与限界.ppt（19页珍藏版）》请在三一文库上搜索。
1、第8章 分支与限界,1. 由部分解估计整体解的界 2. 分支与限界法的基本思想 3. 分支与限界法示例 4. 分支与限界法总结 5. 分支与限界法界估算预处理示例 6.分支与限界法的双限界示例,1. 由部分解估计整体解的界,1.1 0/1背包问题解的上界估计 1.2 多段图最短路径问题解的下界估计 1.3 任务分配问题解的下界估计,1.1 0/1背包问题解的上界估计,假设0/1背包问题背包承重为M，有n个物品，其中的物品已按照价/重比由大到小的顺序排列。序号集合是0,1,n-1，第i个物品的价/重比是pi/wi。目前背包中已经有物品的集合是S1，被抛弃不用的物品集合是S2，待选物品集合是S3
2、（其中物品的价/重比是所有物品中最小的。假定S3中的物品全部加入背包后超重）。 此时，如果背包超重，上界估计为0；如果背包刚好放满，上界即为S1中价值总和；如果背包中尚有空间N， S3中的序号为m, m+1, , n-1。则必定存在一个序号k满足m=k=n-1，使得 此时，令 则Pe是对整体解的一个上界估计,例如，5个物品要装入载重为37的背包，物品重量和价值分别为（已按价/重比由大到小排列） 8，16，21，17，12（重） 8，14，16，11，7（价） 现在背包中只有一个元素0，估算解的上界。 S1=0， S2=， S3=1，2，3，4背包的剩余空间为37-8=29。它能装下S3中的物品
3、1和物品2的一部分。因此，解的估计为：,1.2 多段图最短路径问题解的下界估计,0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,如果当前路径为(0)(2)，则这个部分解估计整体解不会小于如下估计值，哪个好？,1.3 任务分配问题解的下界估计,任务1,任务2,任务3,任务4,人员a,人员b,人员c,人员d,9,2,7,8,6,4,3,7,5,8,1,8,7,6,9,4,n个任务、n个人构成的任务分配问题在没有任何选择的情况下，解的下界是： 当确定了某个任务分配给哪个人后，剩余的问题与原问题等价，下界估计是已选费用加子问题下界,任务1
4、,任务2,任务3,任务4,人员a,人员b,人员c,人员d,9,2,7,8,6,4,3,7,5,8,1,8,7,6,9,4,这个问题的下界估计是：5+2+1+4 = 12。第一个任务分配给第一个人后，得到子问题,任务2,任务3,任务4,人员b,人员c,人员d,4,3,7,8,1,8,6,9,4,这个子问题的下界估计是：4+1+4=9。部分解对应的原问题下界估计是：9+9=18,2. 分支与限界法的基本思想,分支与限界法从一个空的解向量开始，逐渐扩展这个解向量，直至扩展至完整的解向量（这与回溯法相同） 分支与限界法在解向量的扩展过程中，遇到不满足约束的情况，把当前解和它的分支全部删除（这也与回溯法
5、相同） 分支与限界法在选择当前解时，并不是按照解向量的固有先后顺序进行，而是对那些最有可能成为最优解的解向量或部分向量扩展 分支与限界法通常以一个最大或最小堆作为数据结构支持,3. 分支与限界法示例,3.1 分支限界法解决0/1背包问题 3.2 分支限界法解决多段图最短路径问题 3.3 分支限界法解决任务分配问题,3.1 分支限界法解决0/1背包问题,对M容量的背包和n个物品，如果物品i的价/重比是pi/wi，则把物品按照价/重比排序。排序后各个物品的序号是0, 1, 2, , n-1 一个完整的解要进行n次扩展才能完成。第i次扩展有两个分支：要物品i和不要物品i 当前解如果不满足背包重量约束
6、，则删除它；否则，估计该解的上界，按照估计值插入最大堆。如果是对当前部分解扩展，则要把它的所有子女估值插入最大堆，同时删除当前部分解 直至某个解扩展完成，并且它处于最大堆堆顶，则问题结束,8，16，21，17，12（重）背包载重37 8，14，16，11，17（价）,包中 包外0,1,2,3,4 上界31.9,包中 包外1,2,3,4 上界30,包中0 包外1,2,3,4 上界31.9,3.2 分支限界法解决多段图最短路径问题,假设多段图共有n段，每段上的路径条数的最大值是m 一个完整的解要进行n次扩展才能完成。第i次扩展的分支数是当前节点到下一阶段的节点中连线的条数，最多有m个分支 用一个最
7、小堆存放待处理的解，最小堆的关键字是对部分解下界的估计（下确界大于或等于这个关键字）。每次取堆顶、删除，并估算它的所有子女，并把它们插入到最小堆中，以便继续对解进行扩展 如果处于最小堆堆顶的解已经扩展完成，则它就是问题的解,0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,路径0 下界2+4+5+3=14,路径0-1 下界4+8+5+3=20,路径0-2 下界2+7+5+3=17,路径0-3 下界3+4+5+3=15,3.3 分支限界法解决任务分配问题,假设n个任务分配给n个人，每个人完成不同任务的耗费由一个矩阵给出 初始时，任何任
8、务都没分配给任何人，一个完整的解要进行n次扩展才能完成。第i次扩展的分支数是剩余的任务数（等于剩余的人数） 用一个最小堆存放待处理的解，最小堆的关键字是对部分解下界的估计。每次取堆顶、删除，并估算它的所有子女，并把它们插入到最小堆中，以便继续对解进行扩展 直至某个解扩展完成，并且它处于最小堆堆顶，则问题结束,解的下界： 5+2+1+4=12,解的下界： 9+4+1+4=18,解的下界： 6+2+1+4=18,解的下界： 5+2+3+4=14,解的下界： 7+2+1+7=17,4. 分支与限界法总结(待续),分支与限界法与回溯法的求解方式是一致的，都是对部分解进行扩展直至得到最佳的整体解 分支与
9、限界法与回溯法都可以在求解过程中删除不可能的解 但分支限界法能够改变回溯法处理部分解的顺序，使得最可能发展成为最优解的部分解优先处理。可以认为回溯法是“世袭制”，分支限界法是“竞争制” 当问题只有约束条件而没有最优目标时，分支限界法退化为回溯法,4. 分支与限界法总结(续),回溯法的空间一般由问题的深度决定，问题同一深度上的空间可以重复利用；而分支限界法需要大量的空间。可以用一些因问题而异的方法简化每一个节点的空间大小 分支限界法的时间消耗一般比回溯法少得多，但估计上/下界时，需要花费额外的时间。可以用预处理的办法减少上/下界估算的时间复杂度 最小问题在估算下界的同时，可以同时估算上界，以便有一个参考，使得高于上界的那些部分解的节点提前删除，减小堆的规模，提高运算效率,5. 分支与限界法界估算预处理示例,0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,下界序列：14，12，8，3 当部分解是0-3时，下界估计是3+4+8=15,6.分支与限界法的双限界示例,0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,部分解0-2的上界是0-2-5-8-9对应的值18 而部分解0-1的下界是4+8+5+3=20，它小于部分解0-2的上界，可以通过估算不插入堆中,