第9章-分支限界法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计与分析,清华大学出版社,第,9,章 分支限界法,9.1,概,述,9.2,图问题中的分支限界法,9.3,组合问题中的分支限界法,9.4,实验项目,电路布线问题,1,9.1,概,述,9.1.1,解空间树的动态搜索（,2,）,9.1.2,分支限界法的设计思想,9.1.3,分支限界法的时间性能,2,分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界,down,up,。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表,PT,）中。依次从表,PT,中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。,9.1.1,解空间树的动态搜索（,2,）,3,随着这个遍历过程的不断深入，表,PT,中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时,，如果该结点的目标函数值是表,PT,中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表,PT,中的结点，将超出目标函数界的结点丢弃，然后从表,PT,中选取使目标函数取得极值的结点继续进行扩展。,4,例：,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,5,应用贪心法求得近似解为,(1,0,0,0),，获得的价值为,40,，这可以作为,0/1,背包问题的下界。,如何求得,0/1,背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第,1,个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：,ub,=,W,(,v,1,/,w,1,)=10,10=100,。于是，得到了目标函数的界,40,100,。,限界函数为：,6,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,分支限界法求解,0/1,背包问题,7,分支限界法求解,0/1,背包问题，其搜索空间如图,9.1,所示，具体的搜索过程如下：,（,1,）在根结点,1,，没有将任何物品装入背包，因此，背包的重量和获得的价值均为,0,，根据限界函数计算结点,1,的目标函数值为,1010=100,；,（,2,）在结点,2,，将物品,1,装入背包，因此，背包的重量为,4,，获得的价值为,40,，目标函数值为,40+(10-4)6=76,，将结点,2,加入待处理结点表,PT,中；在结点,3,，没有将物品,1,装入背包，因此，背包的重量和获得的价值仍为,0,，目标函数值为,106,60,，将结点,3,加入表,PT,中；,（,3,）在表,PT,中选取目标函数值取得极大的结点,2,优先进行搜索；,8,（,4,）在结点,4,，将物品,2,装入背包，因此，背包的重量为,11,，不满足约束条件，将结点,4,丢弃；在结点,5,，没有将,物品,2,装入背包，因此，背包的重量和获得的价值与结点,2,相同，目标函数值为,40+(10-4)5=70,，将结点,5,加入表,PT,中；,（,5,）在表,PT,中选取目标函数值取得极大的结点,5,优先进行搜索；,（,6,）在结点,6,，将物品,3,装入背包，因此，背包的重量为,9,，获得的价值为,65,，目标函数值为,65+(10-9)4=69,，将结点,6,加入表,PT,中；在结点,7,，没有将物品,3,装入背包，因此，背包的重量和获得的价值与结点,5,相同，目标函数值为,40+(10-4)4,64,，将结点,6,加入表,PT,中；,9,（,7,）在表,PT,中选取目标函数值取得极大的结点,6,优先进行搜索；,（,8,）在结点,8,，将物品,4,装入背包，因此，背包的重量为,12,，不满足约束条件，将结点,8,丢弃；在结点,9,，没有将物品,4,装入背包，因此，背包的重量和获得的价值与结点,6,相同，,目标函数值为,65,；,（,9,）由于结点,9,是叶子结点，同时结点,9,的目标函数值是表,PT,中的极大值，所以，结点,9,对应的解即是问题的最优解，搜索结束。,10,9.1.2,分支限界法的设计思想,假设求解最大化问题，解向量为,X,=(,x,1,x,2,x,n,),，其中，,x,i,的取值范围为某个有穷集合,S,i,，,|,S,i,|=,r,i,（,1,i,n,）。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界,down,up,，然后从根结点出发，扩展根结点的,r,1,个孩子结点，从而构成分量,x,1,的,r,1,种可能的取值方式。对这,r,1,个孩子结点分别估算可能取得的目标函数值,bound,(,x,1,),，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于,bound,(,x,1,),，也就是部分解应满足：,bound,(,x,1,),bound,(,x,1,x,2,),bound,(,x,1,x,2,x,k,),bound,(,x,1,x,2,x,n,),11,若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表,PT,中。从表,PT,中选取使目标函数取得极大值的结点作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行解,X,=(,x,1,x,2,x,n,),及其目标函数值,bound,(,x,1,x,2,x,n,),。,如果,bound,(,x,1,x,2,x,n,),是表,PT,中目标函数值最大的结点，则,bound,(,x,1,x,2,x,n,),就是所求问题的最大值，,(,x,1,x,2,x,n,),就是问题的最优解；,如果,bound,(,x,1,x,2,x,n,),不是表,PT,中目标函数值最大的结点，说明还存在某个部分解对应的结点，其上界大于,bound,(,x,1,x,2,x,n,),。于是，用,bound,(,x,1,x,2,x,n,),调整目标函数的下界，即令,down,=,bound,(,x,1,x,2,x,n,),，并将表,PT,中超出目标函数下界,down,的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表,PT,中最大。,12,分支限界法求解最大化问题的一般过程,分支限界法的一般过程,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,是叶子结点且结点,x,的,value,值在表,PT,中最大,),，,则将结点,x,对应的解输出，算法结束；,4.2.4,若,(,结点,x,是叶子结点但结点,x,的,value,值在表,PT,中不是最大,),，,则令,down=value,，并且将表,PT,中所有小于,value,的结点删除；,13,应用分支限界法的关键问题,（,1,）如何确定合适的,限界函数,（,2,）如何组织,待处理结点表,（,3,）如何确定最优解中的,各个分量,14,分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表,PT,中最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方法解决：,对每个扩展结点保存该结点到根结点的路径；,在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。,15,(0)60 (1,0,0)64 (1,0,1,0)65,(a),扩展根结点后表,PT,状态,(b),扩展结点,2,后表,PT,状态,(c),扩展结点,5,后表,PT,状态,(d),扩展结点,6,后表,PT,状态，最优解为,(1,0,1,0)65,图,9.2,方法,确定,0/1,背包问题最优解的各分量,(0)60 (1,0,1)69 (1,0,0)64,(1)76 (0)60,(0)60 (1,0)70,例如图,9.1,所示,0/1,背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解,(,x,1,x,i,),和该部分解的目标函数值都存储在待处理结点表,PT,中，在搜索过程中表,PT,的状态如图,9.2,所示。,16,(a),扩展根结点后,(b),扩展结点,2,后,(c),扩展结点,5,后,(d),扩展结点,6,后，最优解为,(1,0,1,0)65,图,9.3,方法,确定,0/1,背包问题最优解的各分量,(0,76)(0,60),PT,ST,(0,60)(1,70),PT,ST,(0,76),(0,60)(0,69)(0,64),PT,ST,(0,76)(1,70),(0,60)(0,64)(1,65),PT,ST,(0,76)(1,70)(0,69),图,9.1,所示,0/1,背包问题，为了在搜索过程中构建搜索经过的树结构，设一个表,ST,，在表,PT,中取出最小值结点进行扩充时，将最小值结点存储到表,ST,中，表,PT,和表,ST,的数据结构为,(,物品,i,-1,的选择结果，,ub,),，在搜索过程中表,PT,和表,ST,的状态如图,9.3,所示。,17,9.1.3,分支限界法的时间性能,分支限界法和回溯法实际上都属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。,与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，有利于实行大范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。,18,分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表,PT,，并且需要在表,PT,中快速查找取得极值的结点，等等。这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。,19,9.2,图问题中的分支限界法,9.2.1 TSP,问题,9.2.2,多段图的最短路径问题,20,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,无向图及其代价矩阵,21,采用贪心法求得近似解为,135421,，其路径长度为,1+2+3+7+3=16,，这可以作为,TSP,问题的上界。,把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为,1+3+1+3+2=10,，但是还有一个信息量更大的下界：考虑一个,TSP,问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以,2,，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。,lb,=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,于是，得到了目标函数的界,14,16,。,需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。,22,部分解的目标函数值的计算方法,例如图,9.4,所示无向图，如果部分解包含边,(1,4),，则该部分解的下界是,lb,=(1+,5,)+(3+6)+(1+2)+(3+,5,)+(2+3)/2=16,。,23,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,1,1,52,lb,=19,54,lb,=14,1,1,42,lb,=16,1,42,lb,=18,45,lb,=15,1,1,52,lb,=20,1,分支限界法求解,TSP,问题示例,24,应用分支限界法求解图,9.4,所示无向图的,TSP,问题，其搜索空间如图,9.5,所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：,（,1,）在根结点,1,，根据限界函数计算目标函数的值为,lb,=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,；,（,2,）在结点,2,，从城市,1,到城市,2,，路径长度为,3,，目标函数的值为,(1+,3,)+(,3,+6)+(1+2)+(3+4)+(2+3)/2=14,，将结点,2,加入待处理结点表,PT,中；在结点,3,，从城市,1,到城市,3,，路径长度为,1,，目标函数的值为,(,1,+3)+(3+6)+(,1,+2)+(3+4)+(2+3)/2=14,，将结点,3,加入表,PT,中；在结点,4,，从城市,1,到城市,4,，路径长度为,5,，目标函数的值为,(1+,5,)+(3+6)+(1+2)+(3+,5,)+(2+3)/2=16,，将结点,4,加入表,PT,中；在结点,5,，从城市,1,到城市,5,，路径长度为,8,，目标函数的值为,(1+,8,)+(3+6)+(1+2)+(3+5)+(2+,8,)/2=19,，超出目标函数的界，将结点,5,丢弃；,25,（,3,）在表,PT,中选取目标函数值极小的结点,2,优先进行搜索；,（,4,）在结点,6,，从城市,2,到城市,3,，目标函数值为,(1+,3,)+(,3,+,6,)+(1+,6,)+(3+4)+(2+3)/2=16,，将结点,6,加入表,PT,中；在结点,7,，从城市,2,到城市,4,，目标函数值为,(1+,3,)+(,3,+,7,)+(1+2)+(3+,7,)+(2+3)/2=16,，将结点,7,加入表,PT,中；在结点,8,，从城市,2,到城市,5,，目标函数值为,(1+,3,)+(,3,+,9,)+(1+2)+(3+4)+(2+,9,)/2=19,，超出目标函数的界，将结点,8,丢弃；,（,5,）在表,PT,中选取目标函数值极小的结点,3,优先进行搜索；（,6,）在结点,9,，从城市,3,到城市,2,，目标函数值为,(,1,+3)+(3+,6,)+(,1,+,6,)+(3+4)+(2+3)/2=16,，将结点,9,加入表,PT,中；在结点,10,，从城市,3,到城市,4,，目标函数值为,(,1,+3)+(3+6)+(,1,+,4,)+(3+,4,)+(2+3)/2=15,，将结点,10,加入表,PT,中；在结点,11,，从城市,3,到城市,5,，目标函数值为,(,1,+3)+(3+6)+(,1,+,2,)+(3+4)+(,2,+3)/2=14,，将结点,11,加入表,PT,中；,26,（,7,）在表,PT,中选取目标函数值极小的结点,11,优先进行搜索；,（,8,）在结点,12,，从城市,5,到城市,2,，目标函数值为,(,1,+3)+(3+,9,)+(,1,+,2,)+(3+4)+(,2,+,9,)/2=19,，超出目标函数的界，将结点,12,丢弃；在结点,13,，从城市,5,到城市,4,，目标函数值为,(,1,+3)+(3+6)+(,1,+,2,)+(,3,+4)+(,2,+,3,)/2=14,，将结点,13,加入表,PT,中；,（,9,）在表,PT,中选取目标函数值极小的结点,13,优先进行搜索；,（,10,）在结点,14,，从城市,4,到城市,2,，目标函数值为,(,1,+3)+(3+,7,)+(,1,+,2,)+(,3,+,7,)+(,2,+,3,)/2=16,，最后从城市,2,回到城市,1,，目标函数值为,(,1,+,3,)+(,3,+,7,)+(,1,+,2,)+(,3,+,7,)+(,2,+,3,)/2=16,，由于结点,14,为叶子结点，得到一个可行解，其路径长度为,16,；,27,（,11,）在表,PT,中选取目标函数值极小的结点,10,优先进行搜索；,（,12,）在结点,15,，从城市,4,到城市,2,，目标函数的值为,(,1,+3)+(3+,7,)+(,1,+,4,)+(,7,+,4,)+(2+3)/2=18,，超出目标函数的界，将结点,15,丢弃；在结点,16,，从城市,4,到城市,5,，目标函数值为,(,1,+3)+(3+6)+(,1,+,4,)+(,3,+,4,)+(2+,3,)/2=15,，将结点,16,加入表,PT,中；,（,13,）在表,PT,中选取目标函数值极小的结点,16,优先进行搜索；,（,14,）在结点,17,，从城市,5,到城市,2,，目标函数的值为,(,1,+3)+(3+,9,)+(,1,+,4,)+(,3,+,4,)+(,9,+,3,)/2=20,，超出目标函数的界，将结点,17,丢弃；,（,15,）表,PT,中目标函数值均为,16,，且有一个是叶子结点,14,，所以，结点,14,对应的解,135421,即是,TSP,问题的最优解，搜索过程结束。,28,(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,后的状态,29,算法,9.1,TSP,问题,1,根据限界函数计算目标函数的下界,down,；采用贪心法得到上界,up,；,2,将待处理结点表,PT,初始化为空；,3,for(i=1;i=1),5.1 i=k+1;,5.2 xi=1;,5.3 while(xi=n),5.3.1,如果路径上顶点不重复，则,5.3.1.1,根据式,9.2,计算目标函数值,lb,；,5.3.1.2 if(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,段的最短边,第,32,应用分支限界法求解图,9.7,所示多段图的最短路径问题，其搜索空间如图,9.8,所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：,（,1,）在根结点,1,，根据限界函数计算目标函数的值为,18,；,（,2,）在结点,2,，第,1,段选择边,，目标函数值为,lb,=,4,+,8,+,5+3=20,，超出目标函数的界，将结点,2,丢弃；在结点,3,，第,1,段选择边,，目标函数值为,lb,=,2,+,6,+5+3=16,，将结点,3,加入待处理结点表,PT,中；在结点,4,，第,1,段选择边,，目标函数值为,lb,=,3,+,4,+5+3=15,，将结点,4,加入表,PT,中；,（,3,）在表,PT,中选取目标函数值极小的结点,4,优先进行搜索；,33,（,4,）在结点,5,，第,2,段选择边,，目标函数值为,lb,=,3,+,4,+,6,+3=16,，将结点,5,加入表,PT,中；在结点,6,，第,2,段选择边,，目标函数值为,lb,=,3,+,7,+,5,+3=18,，将结点,6,加入表,PT,中；,（,5,）在表,PT,中选取目标函数值极小的结点,3,优先进行搜索；,（,6,）在结点,7,，第,2,段选择边,，目标函数值为,lb,=,2,+,6,+,5,+3=16,，将结点,7,加入表,PT,中；在结点,8,，第,2,段选择边,，目标函数值为,lb,=,2,+,7,+,6,+3=18,，将结点,8,加入表,PT,中；在结点,9,，第,2,段选择边,，目标函数值为,lb,=,2,+,8,+,5,+3=18,，将结点,9,加入表,PT,中；,34,（,7,）在表,PT,中选取目标函数值极小的结点,5,优先进行搜索；,（,8,）在结点,10,，第,3,段选择边,，可直接确定第,4,段的边,，目标函数值为,lb,=,3,+,4,+,8,+,7,=22,，为一个可行解但超出目标函数的界，将其丢弃；在结点,11,，第,3,段选择边,，可直接确定第,4,段的边,，目标函数值为,lb,=,3,+,4,+,6,+,3,=16,，为一个较好的可行解。由于结点,11,是叶子结点，并且其目标函数值是表,PT,中最小的，所以，结点,11,代表的解即是问题的最优解，搜索过程结束。,35,6,4,01,lb,=20,2,3,1,start,lb,=18,02,lb,=16,03,lb,=15,图,9.8,分支限界法求解多段图的最短路径问题示例,(,表示该结点被丢弃，结点上方的数组表示搜索顺序,),7,24,lb,=16,8,25,lb,=18,9,26,lb,=18,5,35,lb,=16,36,lb,=18,11,10,57,lb,=22,58,lb,=16,36,为了在搜索过程中构建搜索经过的树结构，设一个表,ST,，在表,PT,中取出最小值结点进行扩充时，将最小值结点存储到表,ST,中，表,PT,和表,ST,的数据结构为,(,第,i,段，,lb),，在搜索过程中表,PT,和表,ST,的状态如下：,(b),扩展结点,3,后的状态,(d),扩展结点,5,后的状态，最优解为,03589,图,9.9,多段图的最短路径问题最优解的确定,(1,16)(1,15),(1,16)(2,16)(2,18)(2,18),(1,15),(2,16)(2,18)(2,18)(2,16)(2,18),(1,15)(1,16),(2,16)(2,18)(2,18)(2,18)(3,16),(1,15)(1,16)(2,16),(a),扩展根结点后的状态,PT,ST,ST,PT,(c),扩展结点,4,后的状态,ST,ST,回溯过程是：,(3,16)(2,16)(1,15),。,37,算法,9.2,多段图的最短路径问题,1,根据限界函数计算目标函数的下界,down,；采用贪心法得到上界,up,；,2,将待处理结点表,PT,初始化为空；,3,for(i=1;i=1),5.1,对顶点,u,的所有邻接点,v,5.1.1,根据式,9.3,计算目标函数值,lb;,5.1.2,若,lb=up,，则将,i,lb,存储在表,PT,中；,5.2,如果,i=k-1,且叶子结点的,lb,值在表,PT,中最小，,则输出该叶子结点对应的最优解；,5.3,否则，如果,i=k-1,且表,PT,中的叶子结点的,lb,值不是最小，则,5.3.1 up=,表,PT,中的叶子结点最小的,lb,值,;,5.3.2,将表,PT,中目标函数值超出,up,的结点删除；,5.4 u=,表,PT,中,lb,最小的结点的,v,值；,5.5 i=,表,PT,中,lb,最小的结点的,i,值；,i+;,伪代码,38,9.3,组合问题中的分支限界法,9.3.1,任务分配问题,9.3.2,批处理作业调度问题,39,9.3.1,任务分配问题,任务分配问题要求把,n,项任务分配给,n,个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图,9.10,所示是一个任务分配的成本矩阵。,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,任务分配问题的成本矩阵,40,求最优分配成本的上界和下界,考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务,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,是一个更好的上界。为了获得下界，考虑人员,a,执行所有任务的最小代价是,2,，人员,b,执行所有任务的最小代价是,3,，人员,c,执行所有任务的最小代价是,1,，人员,d,执行所有任务的最小代价是,4,。因此，将每一行的最小元素加起来就得到解的下界，其成本是,2+3+1+4=10,。需要强调的是，这个解并不是一个合法的选择（,3,和,1,来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是,10,14,之间的某个值。,41,设当前已对人员,1,i,分配了任务，并且获得了成本,v,，则限界函数可以定义为：,（式,9.4,）,42,（,2,）在结点,2,，将任务,1,分配给人员,a,，获得的成本为,9,，目标函数值为,9+(3+1+4)=17,，超出目标函数的界,10,14,，将结点,2,丢弃；在结点,3,，将任务,2,分配给人员,a,，获得的成本为,2,，目标函数值为,2+(3+1+4)=10,，将结点,3,加入待处理结点表,PT,中；在结点,4,，将任务,3,分配给人员,a,，获得的成本为,7,，目标函数值为,7+(3+1+4)=15,，超出目标函数的界,10,14,，将结点,4,丢弃；在结点,5,，将任务,4,分配给人员,a,，获得的成本为,8,，目标函数值为,8+(3+1+4)=16,，超出目标函数的界,10,14,，将结点,5,丢弃；,应用分支限界法求解图,9.10,所示任务分配问题，对解空间树的搜索如图,9.11,所示，具体的搜索过程如下：,（,1,）在根结点,1,，没有分配任务，根据限界函数估算目标函数值为,2+3+1+4=10,；,43,（,3,）在表,PT,中选取目标函数值极小的结点,3,优先进行搜索；,（,4,）在结点,6,，将任务,1,分配给人员,b,，获得的成本为,2+6=8,，目标函数值为,8+(1+4),13,，将结点,6,加入表,PT,中；在结点,7,，将任务,3,分配给人员,b,，获得的成本为,2+3=5,，目标函数值为,5+(1+4),10,，将结点,7,加入表,PT,中；在结点,8,。将任务,4,分配给人员,b,，获得的成本为,2+7=9,，目标函数值为,9+(1+4),14,，将结点,8,加入表,PT,中；,（,5,）在表,PT,中选取目标函数值极小的结点,7,优先进行搜索；,（,6,）在结点,9,，将任务,1,分配给人员,c,，获得的成本为,5+5=10,，目标函数值为,10+4=14,，将结点,9,加入表,PT,中；在结点,10,，将任务,4,分配给人员,c,，获得的成本为,5+8=13,，目标函数值为,13+4=17,，超出目标函数的界,10,14,，将结点,10,丢弃；,44,（,7,）在表,PT,中选取目标函数值极小的结点,6,优先进行搜索；,（,8,）在结点,11,，将任务,3,分配给人员,c,，获得的成本为,8+1=9,，目标函数值为,9+4=13,，将结点,11,加入表,PT,中；在结点,12,，将任务,4,分配给人员,c,，获得的成本为,8+8=16,，目标函数值为,16+4=20,，超出目标函数的界,10,14,，将结点,12,丢弃；,（,9,）在表,PT,中选取目标函数值极小的结点,11,优先进行搜索；,（,10,）在结点,13,，将任务,4,分配给人员,d,，获得的成本为,9+4=13,，目标函数值为,13,，由于结点,13,是叶子结点，同时结点,13,的目标函数值是表,PT,中的极小值，所以，结点,13,对应的解即是问题的最优解，搜索结束。,45,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,图,9.11,分支限界法求解任务分配问题示例,(,表示该结点被丢弃，结点上方的数组表示搜索顺序,),2,3,5,6,7,8,9,12,13,11,1,46,为了在搜索过程中构建搜索经过的树结构，设一个表,ST,，在表,PT,中取出最小值结点进行扩充时，将最小值结点存储到表,ST,中，表,PT,和表,ST,的数据结构为,(,人员,i,-,1,分配的任务,lb),(e),扩展结点,11,后的状态，最优解为,2,a,1,b,3,c,4,d,图,9.12,任务分配问题最优解的确定,(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),(a),扩展根结点后的状态,(b),扩展结点,3,后的状态,PT,ST,PT,ST,PT,(c),扩展结点,7,后的状态,(d),扩展结点,6,后的状态,(2,14)(3,14)(3,13),PT,ST,PT,ST,ST,回溯过程是：,(3,13)(1,13)(2,13)(0,10),。,47,算法,9.3,任务分配问题,1,根据限界函数计算目标函数的下界,down,；采用贪心法得到上界,up,；,2,将待处理结点表,PT,初始化为空；,3,for(i=1;i=1),5.1 xk=1;,5.2 while(xk=n),5.2.1,如果人员,k,分配任务,xk,不发生冲突，则,5.2.1.1,根据式,9.4,计算目标函数值,lb;,5.2.1.2,若,lb=up,，则将,i,lb,存储在表,PT,中；,5.2.2 xk=xk+1;,5.3,如果,k=n,且叶子结点的,lb,值在表,PT,中最小，,则输出该叶子结点对应的最优解；,5.4,否则，如果,k=n,且表,PT,中的叶子结点的,lb,值不是最小，则,5.4.1 up=,表,PT,中的叶子结点最小的,lb,值,;,5.4.2,将表,PT,中超出目标函数界的结点删除；,5.5 i=,表,PT,中,lb,最小的结点的,xk,值；,5.6 k=,表,PT,中,lb,最小的结点的,k,值；,k+;,伪代码,48,9.3.2,批处理作业调度问题,给定,n,个作业的集合,J,=,J,1,J,2,J,n,，每个作业都有,3,项任务分别在,3,台机器上完成，作业,J,i,需要机器,j,的处理时间为,t,ij,（,1,i,n,1,j,3,），每个作业必须先由机器,1,处理，再由机器,2,处理，最后由机器,3,处理。批处理作业调度问题要求确定这,n,个作业的最优处理顺序，使得从第,1,个作业在机器,1,上处理开始，到最后一个作业在机器,3,上处理结束所需的时间最少。,显然，批处理作业的一个最优调度应使机器,1,没有空闲时间，且机器,2,和机器,3,的空闲时间最小。可以证明，存在一个最优作业调度使得在机器,1,、机器,2,和机器,3,上作业以相同次序完成。,49,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,2,J,3,J,1,J,4,),，则从作业,2,在机器,1,处理开始到作业,4,在机器,3,处理完成的调度方案如图,9.14,所示。,J,2,:10,J,3,:9,J,1,:5,J,4,:7,机器,1,机器,2,机器,3,图,9.14,批处理调度问题的调度方案,空闲,:10,J,2,:5,J,3,:9,J,1,:7,J,4,:8,空闲,:15,J,2,:2,J,3,:5,J,1,:9,J,4,:10,设,J,=,J,1,J,2,J,3,J,4,是,4,个待处理的作业，每个作业的处理顺序相同，即先在机器,1,上处理，然后在机器,2,上处理，最后在机器,3,上处理，需要的处理时间如图,9.13,所示。,50,一般情况下，对于一个已安排的作业集合,M,1,2,n,，,|,M,|=,k,，即已安排了,k,个作业，设,sum1k,表示机器,1,完成,k,个作业的处理时间，,sum2k,表示机器,2,完成,k,个作业的处理时间，现在要处理作业,k+1,，此时，该部分解的目标函数值的下界计算方法如下：,（,1,）,sum1k+1=sum1k+,t,k,1,（,2,）,（,3,）,sum2k+1=maxsum1k+1,sum2k+,t,k,2,批处理作业调度问题的限界函数,考虑理想情况，机器,1,和机器,2,无空闲，最后处理的恰好是在机器,3,上处理时间最短的作业。例如，以作业,J,i,开始的处理顺序，估算处理所需的最短时间是：,51,应用分支限界法求解图,9.13,所示批处理作业调度问题，其搜索空间如图,9.15,所示，具体的搜索过程如下：,（,1,）在根结点，将,sum10,和,sum20,分别初始化为,0,；,（,2,）在结点,2,，以作业,J,1,开始处理，则,sum11=5,，目标函数值为,5+(7+5+9+8)+2=36,，,sum21=5+7=12,，将结点,2,加入待处理结点表,PT,中；在结点,3,，以作业,J,2,开