第9章_分支限界法

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Branch and Bound Method,*,第,9,章分支限界法,Branch and Bound Method,算法设计与分析,本科,生课程,Design and Analysis of Algorithm,邱钊,海南大学信息科学技术学院,College of Information Science and Technology, Hainan University,qiuzhao73,2024/9/21,2,教学重点,分支限界法的设计思想，各种经典问题的限界函数,教学难点,各种经典问题的限界函数以及限界算法,教学内容及目标,知识点,教学要求,了解,理解,掌握,熟练掌握,分支限界法的设计思想,分支限界法的时空性能,TSP,问题,多段图的最短路径问题,0/1,背包问题,任务分配问题,批处理作业调度问题,学习目标,Chapter,8,Back Track Method,2024/9/21,Branch and Bound Method,3,第,9,章 分支限界法,9.1,概,述,9.2,图,问题中的分支限界法,9.3,组合问题中的分支限界法,2024/9/21,Branch and Bound Method,4,回溯法,：按深度优先策略遍历问题的解空间树，应用约束条件、目标函数等剪枝函数实行剪枝,分支限界法,：按广度优先策略遍历问题的解空间树，在遍历过程中，对已经处理的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。,9.1,概,述,2024/9/21,Branch and Bound Method,5,9.1,概,述,9.1.1,分支限界法的设计思想,9.1.2,分支限界法的时间性能,2024/9/21,Branch and Bound Method,6,回溯法存在的问题,虽用,剪枝,减少了搜索空间，但,按深度优先策略机械地进行,，搜索是盲目的,。如,0/1,背包问题。,首先将目标函数初始化为最大值，目标函数只有在,有一个可行解（第一个叶子）后才有意义,，此后的搜索相对来说才有方向，所以从搜索的整个过程来看还是盲目的。如,TSP,问题（图,8.6,）。,分支限界法,先确定一个合理的,限界函数,由限界函数确定目标函数的界,down, up,仍以,穷举法的解空间树,为基础，但以,广度优先的原理,搜索该结点的所有孩子结点，分别估算这些,孩子结点的目标函数的可能取值,分支限界法的设计思想,2024/9/21,Branch and Bound Method,7,如果某孩子结点的目标函数,可能取值超出目标函数的界，则将其丢弃，,因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（表,PT,）,依次从表,PT,中选取使目标函数的值取极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。,目标函数的界,down, up,的确定,对最大化问题,Up,由限界函数确定，,down,由某种启发方式得到,如贪心算法,对最小化问题,down,由限界函数确定，,up,由某种启发方式得到,如贪心算法,分支限界法的设计思想,2024/9/21,Branch and Bound Method,8,例：,0/1,背包问题。假设有,4,个物品，其重量分别为,(4, 7, 5, 3),，价值分别为,(40, 42, 25, 12),，背包容量,W=10,。首先，将给定物品按单位重量价值从大到小排序，结果如下：,物品,重量,(,w,),价值,(,v,),价值,/,重量,(,v,/,w,),1,4,40,10,2,7,42,6,3,5,25,5,4,3,12,4,分支限界法的设计思想,2024/9/21,Branch and Bound Method,9,确定上下界,down,：,应用贪心法求得近似解为,(1, 0, 1, 0),，获得的价值为,65,，这可以作为,0/1,背包问题的,下界,。,up,：,考虑最好情况，背包中全部装入第,1,个物品且可以将背包装满，则可得到一个,简单上界,的计算方法：,up=W(v,1,/w,1,)=1010=100,则目标函数的界：,65, 100,限界函数为,：,分支限界法的设计思想,2024/9/21,Branch and Bound Method,10,w,=0,v,=0,ub,=100,w,=4,v,=40,ub,=76,w,=0,v,=0,ub,=60,w,=11,无效解,w,=4,v,=40,ub,=70,w,=9,v,=65,ub,=69,w,=4,v,=40,ub,=64,w,=12,无效解,w,=9,v,=65,ub,=65,2,3,4,5,6,7,8,9,1,PT,表,图,9.1 0/1,背包问题,分支限界法的设计思想,2024/9/21,Branch and Bound Method,11,分支限界法的搜索过程如下：,在根结点,1,没有物品装入背包，,w=0,v=0,限界函数值：,ub=0+(10-0)=1010=100,在结点,2,物品,1,装入背包，,w=w,1,=4,，,v=40,目标函数值,:,ub=40 + (10-4)6=76,将结点,2,加入待处理结点表,PT,中,在结点,3,物品,1,不装入背包，,w=0,v=0,目标函数值,:,10ub=0+(10-0)6,60W,，不满足约束条件， 将结点,4,丢弃,在结点,5,物品,2,不装入背包，,w=4,v=40,与结点,2,相同,目标函数值为,:,ub=40 + (10-4)5=70,将结点,5,加入表,PT,中,在结点,6,物品,3,装入背包，,w=4+5=9,，,v=40+25=65,目标函数值为,:,ub=65 + (10-9)4=69,将结点,6,加入表,PT,中,在表,PT,中选取目标函数值取得极大的结点,5,优先进行搜索,分支限界法的设计思想,2024/9/21,Branch and Bound Method,13,在结点,7,物品,3,不装入背包，,w=4,v=40,与结点,5,相同,目标函数值为：,ub=40 + (10-4)4,64W,不满足约束条件，将结点,8,丢弃；,在结点,9,物品,4,不装入背包，,w=9, v=65,与结点,6,相同,目标函数值为,:,ub=65+(W-w)*0=65,将结点,9,加入表,PT,中,在表,PT,中选取目标函数值取得极大的结点,6,优先进行搜索,分支限界法的设计思想,2024/9/21,Branch and Bound Method,14,结点,9,是叶子结点,同时结点,9,的目标函数值是表,PT,中的极大值，,结点,9,对应的解即是问题的最优解，,搜索结束,在图,9.1,的,0/1,背包问题中，为了在搜索过程中,构建搜索经过的树结构,，设一个表,PT,，记录搜索过程，如图,9.2,。,再设计了一表,ST,，从,PT,中,取出最大值结点进行扩充,时，将最大值结点存储到表,ST,中，表,PT,和表,ST,的数据结构为：,(,物品,i-1,的选择结果，,ub,),在搜索过程中表,PT,和表,ST,的状态如图,9.2,所示,分支限界法的设计思想,2024/9/21,Branch and Bound Method,15,(c),扩展结点,5,后,(d),扩展结点,6,后，最优解为,(1,0,1,0)65,图,9.2,方法确定,0/1,背包问题最优解的各分量,(a),扩展根结点后,(b),扩展结点,2,后,(0,76),PT,ST,(1,70),PT,ST,(0,76),(0,69),PT,ST,(0,76) (1,70),(1,65),PT,ST,(0,76) (1,70) (0,69),9,2,5,6,分支限界法的设计思想,2024/9/21,Branch and Bound Method,16,基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点,只有一次机会,成为扩展结点。活结点一旦成为扩展结点，,就一次性产生其所有儿子结点。,在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中,取下一结点（ 使目标函数取得极值的结点 ）,成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分支限界法的设计思想,2024/9/21,Branch and Bound Method,17,分支限界法的一般过程,1,根据限界函数计算目标函数的,down,，,up,；,2,将待处理结点表,PT,初始化为空；,3.,对根结点的每个孩子结点,x,执行下列操作,3.1,估算结点,x,的目标函数值,value;,3.2,若（,value=down,）,则将结点,x,加入表,PT,中；,4,循环直到某个叶子结点的目标函数值在表,PT,中最大,4.1 i=,表,PT,中值最大的结点；,4.2,对结点,i,的每个孩子结点,x,执行下列操作,4.2.1,估算结点,x,的目标函数值,value,；,4.2.2,若,(value=down),，则将结点,x,加入表,PT,中；,4.2.3,若（结点,x,是叶子结点且,value,值在表,PT,中最大），则将结点,x,对应的解输出，算法结束；,4.2.4,若,(,结点,x,是叶子结点但,value,值在表,PT,中不是最大,),则令,down=value,，并且将表,PT,中所有小于,value,的结点删除；,分支限界法的设计思想,2024/9/21,Branch and Bound Method,18,用分支限界法求解问题的关键,如何确定合适的,限界函数,限界函数用于估算结点的目标函数的可能取值。好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能尽早对超出目标函数界的结点进行剪枝，减少搜索空间。有时需要对具体的问题实例进行大量实验才能确定一个合理的限界函数。,如何组织,待处理结点表,为提高查找极值的效率，待处理结点表,PT,可采用堆或优先队列的形式存储。,分支限界法的设计思想,2024/9/21,Branch and Bound Method,19,用分支限界法求解问题的关键（续）,如何确定最优解中,的各个分量,分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此当搜索到最优解（叶子结点）时，却无法求得该叶子结点对应的最优解中的各个分量（,路径,）。解决方法：,对每个扩展结点保存根结点到该结点的路径；,在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。,分支限界法的设计思想,2024/9/21,Branch and Bound Method,20,(c),扩展结点,5,后,(d),扩展结点,6,后，最优解为,(1,0,1,0)65,图,9.2,方法确定,0/1,背包问题最优解的各分量,(a),扩展根结点后,(b),扩展结点,2,后,(0,76),PT,ST,(1,70),PT,ST,(0,76),(0,69),PT,ST,(0,76) (1,70),(1,65),PT,ST,(0,76) (1,70) (0,69),9,2,5,6,分支限界法的设计思想,2024/9/21,Branch and Bound Method,21,9.1,概,述,9.1.1,分支限界法的设计思想,9.1.2,分支限界法的时间性能,2024/9/21,Branch and Bound Method,22,与回溯法相同点,分支限界法,和,回溯法,实际上都是基于蛮力法，遍历具有指数阶个结点的解空间树,在最坏情况下，时间复杂性肯定为指数阶,2,n,或,n,n,与回溯法不同点,分支限界法,首先扩展解空间树中的上层结点,，并用,限界函数大范围剪枝,根据限界函数,不断调整搜索方向,，选择最有可能取得最优解的子树优先进行搜索,如果选择了结点的合理,扩展顺序,以及设计,好的限界函数,，分支界限法,可以快速得到问题的解,9.1.2,分支限界法的时间性能,2024/9/21,Branch and Bound Method,23,分支限界法的代价,首先，设计,一个好的限界函数通常需要花费更多的时间计算相应的目标函数值,，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；,其次，分支限界法,对解空间树中结点的处理是跳跃式的,，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个,扩展结点保存该结点到根结点的路径,，或者在搜索过程中构建搜索经过的树结构，这使得,算法的设计较为复杂,；,再次，分支限界法为维护,PT,表,需要较大的存储空间,，在最坏情况下，分支限界法需要的,空间复杂性是指数阶,。,9.1.2,分支限界法的时间性能,2024/9/21,Branch and Bound Method,24,第,9,章 分支限界法,9.1,概,述,9.2,图问题中的分支限界法,9.3,组合问题中的分支限界法,9.2,图问题中的分支限界法,9.2.1 TSP,问题,9.2.2,多段图的最短路径问题,25,Branch and Bound Method,算法设计与分析,2024/9/21,Branch and Bound Method,26,9.2.1 TSP,问题,TSP,问题是指旅行家要旅行,n,个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,C,=,3,1,5 8,3,6,7 9,1,6 4,2,5,7 4 ,3,8 9,2,3,(a),一个无向图,(b),无向图的代价矩阵,图,9.4,无向图及其代价矩阵,2024/9/21,Branch and Bound Method,27,确定上界,ub,采用贪心法求得近似解为,:,135421,ub=1+2+3+7+3=16,这可以作为,TSP,问题的上界,确定下界,lb,把矩阵中每一行最小的元素相加，可以得到一个简单的下界,:,lb=1+3+1+3+2=10,一个信息量更大的下界：把矩阵中每一行最小的两个元素相加再除以,2,，再对这个结果向上取整，就得到了一个合理的下界,:,lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,则，目标函数的界,:lb, ub=14, 16,注意：该解并不是一个合法的选择（即没构成哈密顿回路），仅给出了一个,参考下界,。,9.2 TSP,问题,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,2024/9/21,Branch and Bound Method,28,部分解的目标函数值的计算方法,假设当前已确定的路径为,U=(r,1,r,2,r,k,),则：,例如图,10.4,所示无向图，如果部分解包含顶点,U=(1, 4),，则该部分解的下界是,:,lb=(2*,5,+(,1+3,)+(,(3+6)+(1+2)+(2+3),)/2=16,分支限界法求解,TSP,问题示例,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,C,=, 3,1,5,8,3,6,7 9,1,6 4,2,5,7 4 ,3,8 9,2,3,i=1,k,2024/9/21,Branch and Bound Method,29,TSP,问题的搜索过程,考察根结点,1,目标函数,: lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,将根结点,1,加入,PT,表中,考察孩子结点,2,:,C,1,C,2,路径长度为,3,目标函数,:,lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3)/2=14,将结点,2,加入待处理结点表,PT,中,；,在结点,3,：,C,1,C,3,，路径长度为,1,目标函数,:lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3)/2=14,将结点,3,加入表,PT,中,在结点,4,：,C,1,C,4,，路径长度为,5,目标函数,:,lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=16,将结点,4,加入表,PT,中, 3,1,5 8,3,6,7 9,1,6 4,2,5,7 4 ,3,8 9,2,3,2024/9/21,Branch and Bound Method,30,在结点,5,：,C,1,C,5,，路径长度为,8,目标函数：,lb=(2*8+(1+2)+(3+6)+(1+2)+(3+4)/2=19,超出目标函数的界，将结点,5,丢弃；,处理结点,2,的孩子结点。结点,6,C,1,C,2,C,3,路径长度为,3+,6,目标函数,:,lb=(2*9+(1+1)+(3+4)+(2+3)/2=16,将结点,6,加入表,PT,中,在结点,7,，,C,1,C,2,C,4,，路径长度为,3+,7,目标函数,lb=(2*10+(1+3)+(1+2)+(2+3)/2=16,将结点,7,加入表,PT,中,分支限界法求解,TSP,问题示例,在表,PT,中选取目标函数值极小的结点,2,优先进行搜索,3,1,5 8,3,6,7,9,1,6, 4,2,5,7,4 3,8 9 2 3,2024/9/21,Branch and Bound Method,31,在结点,8,，,C,1,C,2,C,5,，路径长度为,3+,9,目标函数,:,lb=(2*12+(1+2)+(1+2)+(3+4)/2=19,超出目标函数的界，将结点,8,丢弃,处理结点,3,的孩子。结点,9,，,C,1,C,3,C,2,，路径长度为,1+,6,目标函数值,:,lb=(2*7+(3+3)+(3+4)+(2+3)/2=16,将结点,9,加入表,PT,中,在结点,10,，,C,1,C,3,C,4,，路径长度为,1+,4,目标函数,:,lb=(2*5+(3+3)+(3+6)+(2+3)/2=15,将结点,10,加入表,PT,中,分支限界法求解,TSP,问题示例,在表,PT,中选取目标函数值极小的结点,3,优先进行搜索,3,1,5 8,3 ,6,7 9,1,6,4,2,5,7,4, 3,8,9,2,3,2024/9/21,Branch and Bound Method,32,在结点,11,，,C,1,C,3,C,5,，路径长度为,1+,2,目标函数值,:,lb=(2*3+(3+3)+(3+6)+(3+4)/2=14,将结点,11,加入表,PT,中,在表,PT,中选取目标函数值极小的结点,11,优先进行搜索,处理结点,11,的孩子。结点,12,，,C,1,C,3,C,5,C,2,，路径长度为,1+2+,9,，,目标函数值,:,lb=(2*12+(3+3)+(3+4)/2=19,超出目标函数的界，将结点,12,丢弃,在结点,13,，,C,1,C,3,C5,C,4,，路径长度为,1+2+,3,目标函数值：,lb=(2*6+(3+4)+(3+6)/2=14,将结点,13,加入表,PT,中,在表,PT,中选取目标函数值极小的结点,13,优先进行搜索,3,1,5 8,3 6 7,9,1,6 4,2,5,7 4 ,3,8,9,2,3,2024/9/21,Branch and Bound Method,33,在表,PT,中选取目标函数值极小的结点,10,优先进行搜索,处理结点,13,的孩子。结点,14,，,C,1,C,3,C5,C4,C,2,，路径长度为,1+2+3+7,，,目标函数值,:,lb=(2*13+(3+3)/2=16,由于结点,14,为叶子结点，,得到一个可行解,其路径长度为,16,3,1,5 8,3, 6,7,9,1,6 4,2,5,7,4 ,3,8,9,2,3,分支限界法求解,TSP,问题示例,2024/9/21,Branch and Bound Method,34,分支限界法求解,TSP,问题示例,在表,PT,中选取目标函数值极小的结点,16,优先进行搜索,处理结点,10,的孩子。结点,15,，,C,1,C,3,C,4,C,2,，长度,12,。,目标函数,:,lb=(2*12+(3+3)+(2+3)/2=18,超出目标函数的界，将结点,15,丢弃,结点,16,，,C,1,C,3,C,4,C,5,，长度,8,目标函数,:,lb=(2*8+(3+2)+(3+6)/2=15,将结点,16,加入表,PT,中,处理结点,16,的孩子。结点,17,C,1,C,3,C,4,C,5,C,2,长度,17,，,目标函数,:lb =(2*17+(3+3)/2=20,超目标函数的界，结点,17,丢弃,表,PT,中目标函数值均为,16,，且已找到叶子结点,14,的长度是,16,，故这是最优解，搜索过程结束。,3,1,5 8,3, 6 7,9,1,6 ,4,2,5,7,4,3,8,9,2,3,2024/9/21,Branch and Bound Method,35,4,12,lb,=14,2,3,5,6,7,8,1,start,lb=14,13,lb=14,14,lb,=16,15,lb,=19,23,lb,=16,24,lb,=16,25,lb,=19,32,lb,=16,34,lb,=15,35,lb=14,9,10,11,52,lb,=19,54,lb=14,12,13,42,lb=16,14,42,lb,=18,45,lb,=15,15,16,52,lb,=20,17,分支限界法求解,TSP,问题示例,C,2,C,1,C,3,C,5,C,4,C,3,C,5,C,4,C,2,C,4,C,5,C,4,C,2,C,2,3,1,5 8,3,6,7 9,1,6 4,2,5,7,4,3,8 9,2,3,2024/9/21,Branch and Bound Method,36,(g),扩展结点,16,后的状态，最优解为,135421,图,9.6 TSP,问题最优解的确定,(1, 2)14 (1, 3)14 (1, 4)16,(a),扩展根结点后的状态,(b),扩展结点,2,后的状态,(c),扩展结点,3,后的状态,(d),扩展结点,11,后的状态,(e),扩展结点,13,后的状态,(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16,(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5)14,(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4)14,(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4, 2)16,(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15,(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15,(f),扩展结点,10,后的状态,2024/9/21,Branch and Bound Method,37,算法,9.1,TSP,问题,输入：图,G,（,V,，,E,）,输出：最短哈密尔顿回路,1,根据限界函数计算目标函数的下界,down,；采用贪心法得到上界,up,；,2,计算根结点的目标函数值并加入待处理结点表,PT,；,3,循环直到某个叶子结点的目标函数值在表,PT,中取得极小值,3.1 i=,表,PT,中具有最小值的结点；,3.2,对结点,i,的每个孩子结点,x,执行下列操作：,3.2.1,估算结点,x,的目标函数值,lb;,3.2.2,若（,lb,=,+,+,=,+,k,i,j,p,i,E,v,r,i,j,j,j,j,v,r,c,r,r,c,lb,p,i,2,1,1,1,min,1,段的最短边,第,40,Branch and Bound Method,算法设计与分析,已确定的路径长度,r,i+1,出发的最短边,r,i+2,后面每段的最短边和,应用分支限界法求解图,9.7,所示多段图的最短路径问题，其搜索空间如图,9.8,所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：,（,1,）在根结点,1,，计算目标函数的值为,14,，将根结点加入表,PT,；,（,2,）处理根结点每个孩子结点。结点,2,，第,1,段选择边,，目标函数值为,lb,=,4,+,8,+,5+3=20,，超出目标函数的界，将结点,2,丢弃；在结点,3,，第,1,段选择边,，目标函数值为,lb,=,2,+,7,+5+3=17,，将结点,3,加入表,PT,；在结点,4,，第,1,段选择边,，目标函数值为,lb,=,3,+,4,+5+3=15,，将结点,4,加入表,PT,中；,（,3,）在表,PT,中选取目标函数值极小的结点,4,优先进行搜索；,41,Branch and Bound Method,算法设计与分析,1,2,0,3,4,5,6,7,8,9,4,9,2,3,8,7,8,8,4,7,5,6,8,6,6,5,3,7,（,4,）在结点,5,，第,2,段选择边,，目标函数值为,lb,=,3,+,4,+,6,+3=16,，将结点,5,加入表,PT,中；在结点,6,，第,2,段选择边,，目标函数值为,lb,=,3,+,7,+,5,+3=18,，将结点,6,加入表,PT,；,（,5,）在表,PT,中选取目标函数值极小的结点,5,优先进行搜索；,（,6,）处理结点,5,的每个孩子结点。结点,7,，已确定路径是,0357,，可直接确定第,4,段的边,，目标函数值为,lb,=,3,+,4,+,8,+7=22,，超界丢弃；在结点,8,，已确定路径是,0358,，可直接确定第,4,段的边,，目标函数值为,lb,=3+4+,6,+3=16,，为一个可行解；由于结点,8,是叶子结点，并且其目标函数值是,PT,中最小的，所以它是最优解，搜索结束。,42,Branch and Bound Method,算法设计与分析,1,2,0,3,4,5,6,7,8,9,4,9,2,3,8,7,8,8,4,7,5,6,8,6,6,5,3,7,6,4,01,lb,=20,2,3,1,start,lb,=18,02,lb,=16,03,lb,=15,图,9.8,分支限界法求解多段图的最短路径问题示例,(,表示该结点被丢弃，结点上方的数组表示搜索顺序,),5,35,lb,=16,36,lb,=18,8,7,lb,=22,lb,=16,58,57,43,Branch and Bound Method,算法设计与分析,2024/9/21,Branch and Bound Method,44,第,9,章 分支限界法,9.1,概,述,9.2,图问题中的分支限界法,9.3,组合问题中的分支限界法,2024/9/21,Branch and Bound Method,45,9.3,组合问题中的分支限界法,9.3.2,任务分配问题,9.3.3,批处理作业调度问题,9.3.1,0/1,背包问题,2024/9/21,Branch and Bound Method,46,问题描述,任务分配问题要求把,n,项任务分配给,n,个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图,9.10,所示是一个任务分配的成本矩阵。,9.3.2,任务分配问题,C,9 2 7 8,6 4 3 7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,人员,a,人员,b,人员,c,人员,d,图,9.10,任务分配问题的成本矩阵,2024/9/21,Branch and Bound Method,47,如何求最优分配成本的上界,Up,和下界,Down,获得上界,UP,如考虑以,矩阵的对角线,作为一个可行解,:,任务,1,人员,a,、任务,2,给人员,b,任务,3,人员,c,、任务,4,人员,d,成本,：,9+4+1+4=18,或应用贪心法求得一个近似解：,任务,2,人员,a,、任务,3,人员,b,任务,1,人员,c,、任务,4,人员,d,成本,:,2+3+5+4=14,14,是一个更好的上界,9.3.2,任务分配问题,C,9 2 7 8,6 4 3 7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,人员,a,人员,b,人员,c,人员,d,图,9.10,任务分配问题的成本矩阵,2024/9/21,Branch and Bound Method,48,获得下界,Down,考虑,人员,a,所有任务的最小代价是,2,人员,b,执行所有任务的最小代价是,3,人员,c,执行所有任务的最小代价是,1,人员,d,执行所有任务的最小代价是,4,每行取最小元素，其成本下界：,2+3+1+4=10,则上下界为：,10, 14,注意：这个解并不是一个合法的选择,因为：,3,、,1,来自于矩阵同一列，仅给出一个参考下界,9.3.2,任务分配问题,2024/9/21,Branch and Bound Method,49,设当前已对人员,1,i,分配了任务，并且获得了成本,v,，则限界函数可以定义为：,（式,9.4,）,搜索过程,在根结点,1,没有分配任务，限界函数函数值为,:,lb=2+3+1+4=10,在结点,2,将,J,1,人员,a,，,获得的成本为,9,目标函数值为,:,lb=9 + (3+1+4)=17,超出目标函数的界,10, 14,，将结点,2,丢弃,9.3.2,任务分配问题,C,9 2 7 8,6 4 3 7,5 8 1 8,7 6 9 4,人员,a,人员,b,人员,c,人员,d,2024/9/21,Branch and Bound Method,50,图,9.11,分支限界法求解任务分配问题示例,(,表示该结点被丢弃，结点上方的数组表示搜索顺序,),4,a,lb,=16,10,4,start,lb,=10,1,a,lb,=17,2,a,lb,=10,3,a,lb,=15,1,b,lb,=13,3,b,lb,=10,4,b,lb,=14,1,c,lb,=14,4,c,lb,=17,4,c,lb,=17,3,c,lb,=13,4,d,lb,=13,2,3,5,6,7,8,9,12,13,11,1,C,9 2 7 8,6 4 3 7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,人员,a,人员,b,人员,c,人员,d,任务,1,任务,4,任务,2,任务,1,任务,3,任务,4,任务,1,任务,4,9.3.2,任务分配问题,2024/9/21,Branch and Bound Method,51,搜索过程,在结点,3,将,J,2,人员,a,，获得的成本为,2,目标函数值,:,lb=2 + (3+1+4)=10,将结点,3 -,PT,表中,在结点,4,将,J,3,人员,a,，获得的成本为,7,目标函数值,:,lb=7 + (3+1+4)=15,超出目标函数的界,10, 14,，将结点,4,丢弃,9.3.2,任务分配问题,C,9 2 7 8,6 4 3 7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,人员,a,人员,b,人员,c,人员,d,2024/9/21,Branch and Bound Method,52,在结点,5,将,J,4,人员,a,，获得的成本为,8,目标函数值,:,lb=8 + (3+1+4)=16,超出目标函数的界,10, 14,，将结点,5,丢弃,在结点,6,将,J,2,人员,a,J,1,人员,b,，获得的成本为,2+6=8,目标函数值,:,lb=8+(1+4),13,将结点,6,加入表,PT,中,在表,PT,中选取目标函数值极小的结点,3,优先进行搜索,9.3.2,任务分配问题,9,2,7 8,6,4 3 7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,人员,a,人员,b,人员,c,人员,d,2024/9/21,Branch and Bound Method,53,在结点,7,将,J,2,人员,a,，,J,3,人员,b,，获得的成本为,2+3=5,目标函数值,:,lb=5+(1+4),10,将结点,7,加入表,PT,中,在结点,8,将,J,2,人员,a,，,J,4,人员,b,，获得的成本为,2+7=9,目标函数值,:,lb=9+(1+4),14,将结点,8,加入表,PT,中；,在表,PT,中选取目标函数值极小的结点,7,优先进行搜索,9.3.2,任务分配问题,9,2,7 8,6 4,3,7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,人员,a,人员,b,人员,c,人员,d,2024/9/21,Branch and Bound Method,54,在结点,9,将,J,2,人员,a,，,J,3,人员,b,，,J,1,人员,c,，获得的成本为,5+5=10,目标函数值,:,lb=10+4=14,将结点,9,加入表,PT,中,在结点,10,将,J,2,人员,a,，,J,3,人员,b,，,J,4,人员,c,，获得的成本为,5+8=13,目标函数值,:,lb=13+4=17,超出目标函数的界,10, 14,，将结点,10,丢弃,在表,PT,中选取目标函数值极小的结点,6,优先进行搜索,9.3.2,任务分配问题,2024/9/21,Branch and Bound Method,55,在结点,11,将,J,2,人员,a,J,1,人员,b,，,J,3,人员,c,，获得的成本为,8+1=9,目标函数值,:,lb=9+4=13,将结点,11,加入表,PT,中,在结点,12,将,J,2,人员,a,J,1,人员,b,，,J,4,人员,c,，获得的成本为,8+8=16,目标函数值,:,lb=16+4=20,超出目标函数的界,10, 14,，将结点,12,丢弃；,在表,PT,中选取目标函数值极小的结点,11,优先进行搜索,9.3.2,任务分配问题,9,2,7 8,6 4,3,7,5 8 1 8,7 6 9 4,任务,1,任务,2,任务,3,任务,4,2024/9/21,Branch and Bound Method,56,在结点,13,将,J,2,人员,a,J,1,人员,b,，,J,3,人员,c,，,J,4,人员,d,获得的成本为,9+4=13,目标函数值为,:,lb=13,由于结点,13,是叶子结点，同时结点,13,的目标函数值是表,PT,中的极小值，,所以，结点,13,对应的解即是问题的最优解,搜索结束。,构建搜索经过的树结构,取出表,PT,中最小值结点进行扩充时，并将最小值结点存储到,ST,中，表,PT,和表,ST,的数据结构为：,(,人员,i-1,分配的任务,lb,),9.3.2,任务分配问题,2024/9/21,Branch and Bound Method,57,(,人员,i-1,分配的任务,lb,),(e),扩展结点,11,后的状态，,最优解为,2,a,，,1,b,，,3,c,，,4,d,(0,10),(2,13) (2,10) (2,14),(0,10),(2,13) (2,14) (3,14),(0,10) (2,10),(2,14) (3,14) (1,13),(0,10) (2,10) (2,13),(0,10) (2,10) (2,13) (1,13) (3,13),(a),扩展根结点后的状态,(b),扩展结点,3,后的状态,PT,ST,PT,ST,PT,ST,(c),扩展结点,7,后的状态,(d),扩展结点,6,后的状态,(2,14) (3,14) (3,13),PT,ST,PT,ST,9.3.2,任务分配问题,2024/9/21,Branch and Bound Method,58,9.3,组合问题中的分支限界法,9.3.2,任务分配问题,9.3.3,批处理作业调度问题,9.3.1,0/1,背包问题,2024/9/21,Branch and Bound Method,59,问题描述,n,个作业的集合,J=J,1,J2, J,n,，,每个作业都有,3,项任务分别在,3,台机器上完成,J,i,需要机器,j,的处理时间为,t,ij,（,1in, 1j3,）,作业处理顺序,:,机器,1,处理,机器,2,处理,机器,3,处理,批处理作业调度问题,?,要求确定这,n,个作业的最优处理顺序使得从第,1,个作业在机器,1,上处理开始，到最后一个作业在机器,3,上处理结束所需的时间最少。,最优调度原则,使机器,1,没有空闲时间，且机器,2,和,3,的空闲时间最小,9.3.3,批处理作业调度问题,2024/9/21,Branch and Bound Method,60,T,5 7 9,10 5 2,9 9 5,7 8 10,J,1,J,2,J,3,J,4,机器,1,机器,2,机器,3,设,J,=,J,1,J,2,J,3,J,4,是,4,个待处理的作业，每个作业的处理顺序相同,:,机器,1,上处理,机器,2,上处理,机器,3,上处理,需要的处理时间如下矩阵所示,:,9.3.3,批处理作业调度问题,2024/9/21,Branch and Bound Method,61,上界？随机产生几个方案，从中选取最短完成时间为问题的上界。如若处理顺序为,:,J,4,J,1,J,3,J,2,，调度方案,:,J,4,:7,J,1,:5,J,3,:9,J,2,:10,机器,1,机器,2,机器,3,图,9.13,批处理调度问题的调度方案,空闲,:7,J,4,:8,J,1,:7,J,3,:9,J,2,:5,空闲,:15,J,4,:10,J,1,:9,J,3,:5,J,2,:2,9.3.3,批处理作业调度问题,上界：,41,2024/9/21,Branch and Bound Method,62,批处理作业调度问题的限界函数,down,理想情况,机器,1,和,机器,2,开始作业后无空闲，最后处理的恰好是在,机器,3,上处理时间最短的作业。例如，以作业,J,i,开始的处理顺序，估算处理所需的,最短时间是,：,t,ij,:,表示,J,i,需要机器,j,的处理时间,(1in, 1j3),9.3.3,批处理作业调度问题,作业,J,i,在机器,1,上的处理时间,作业,1,作业,n,在机器,2,上的处理时间总和,在机器,3,上处理时间最短的作业,2024/9/21,Branch and Bound Method,63,目标函数下界计算,lb,若已安排了,k-1,个作业集合，即：,M 1, 2, ,k-1,，,|M|=k-1,sum,1,k-1,：,机器,1,完成,k-1,个作业的处理时间,sum,2,k-1,：,机器,2,完成,k-1,个作业的处理时间,现要处理作业,