分支与限界资料.ppt

第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 （其中物品的价/重比是所有物品中最小的。假定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中的物品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 任务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. 分支与限界法的基本思想 分支与限界法从一个空的解向量开始，逐渐扩展这个解向量，直至扩展至完整的解向量（这与回溯法相同） 分支与限界法在解向量的扩展过程中，遇到不满足约束的情况，把当前解和它的分支全部删除（这也与回溯法相同） 分支与限界法在选择当前解时，并不是按照解向量的固有先后顺序进行，而是对那些最有可能成为最优解的解向量或部分向量扩展 分支与限界法通常以一个最大或最小堆作为数据结构支持 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 当前解如果不满足背包重量约束，则删除它；否则，估计该解的上界，按照估计值插入最大堆。如果是对当前部分解扩展，则要把它的所有子女估值插入最大堆，同时删除当前部分解 直至某个解扩展完成，并且它处于最大堆堆顶，则问题结束 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个分支 用一个最小堆存放待处理的解，最小堆的关键字是对部分解下界的估计（下确界大于或等于这个关键字）。每次取堆顶、删除，并估算它的所有子女，并把它们插入到最小堆中，以便继续对解进行扩展 如果处于最小堆堆顶的解已经扩展完成，则它就是问题的解 0 1 2 3 4 5 6 7 8 9 4 2 3 9 8 8 8 7 4 7 5 6