第9章 分支限界法 (2)优秀课件.ppt

第第9章章 分支限界法分支限界法第1页，本讲稿共57页9.1 概概 述述 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2）9.1.2 分支限界法的设计思想分支限界法的设计思想9.1.3 分支限界法的时间性能分支限界法的时间性能第2页，本讲稿共57页 分分支支限限界界法法首首先先确确定定一一个个合合理理的的限限界界函函数数，并并根根据据限限界界函函数数确确定定目目标标函函数数的的界界down,up。然然后后，按按照照广广度度优优先先策策略略遍遍历历问问题题的的解解空空间间树树，在在分分支支结结点点上上，依依次次搜搜索索该该结结点点的的所所有有孩孩子子结结点点，分分别别估估算算这这些些孩孩子子结结点点的的目目标标函函数数的的可可能能取取值值，如如果果某某孩孩子子结结点点的的目目标标函函数数可可能能取取得得的的值值超超出出目目标标函函数数的的界界，则则将将其其丢丢弃弃，因因为为从从这这个个结结点点生生成成的的解解不不会会比比目目前前已已经经得得到到的的解解更更好好；否否则则，将将其其加加入入待待处处理理结结点点表表（以以下下简简称称表表PT）中中。依依次次从从表表PT中中选选取取使使目目标标函函数数的的值值取取得得极极值值的的结结点点成成为为当当前前扩展结点，重复上述过程，直到找到最优解。扩展结点，重复上述过程，直到找到最优解。9.1.1 解空间树的动态搜索（解空间树的动态搜索（2）第3页，本讲稿共57页 随着这个遍历过程的不断深入，表随着这个遍历过程的不断深入，表PT中所估算的目标函数的界中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结，如果该结点的目标函数值是表点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，中的结点，将超出目标函数界的结点丢弃，然后从表将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得中选取使目标函数取得极值的结点继续进行扩展。极值的结点继续进行扩展。第4页，本讲稿共57页 例例：0/1背背包包问问题题。假假设设有有4个个物物品品，其其重重量量分分别别为为(4,7,5,3)，价价值值分分别别为为(40,42,25,12)，背背包包容容量量W=10。首首先先，将将给给定定物物品品按按单单位重量价值从大到小排序，结果如下：位重量价值从大到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124第5页，本讲稿共57页 应用贪心法求得近似解为应用贪心法求得近似解为(1,0,0,0)，获得的价值为，获得的价值为40，这可以作为，这可以作为0/1背包问题的下界。背包问题的下界。如何求得如何求得0/1背包问题的一个合理的上界呢？考虑最好背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第情况，背包中装入的全部是第1个物品且可以将背包装个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：满，则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界。于是，得到了目标函数的界40,100。限界函数为：限界函数为：第6页，本讲稿共57页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=65234567891分支限界法求解分支限界法求解0/1背包问题背包问题第7页，本讲稿共57页 分分支支限限界界法法求求解解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，目目标标函函数数值值为为10660，将将结结点点3加入表加入表PT中；中；（3）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进行搜索；优先进行搜索；第8页，本讲稿共57页（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)464，将将结结点点6加入表加入表PT中；中；第9页，本讲稿共57页（7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行搜索；优先进行搜索；（8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，背包的重量为12，不满足约束条件，将结点不满足约束条件，将结点8丢弃；在结点丢弃；在结点9，没有将物品，没有将物品4装入背装入背包，因此，背包的重量和获得的价值与结点包，因此，背包的重量和获得的价值与结点6相同，相同，目标函数值目标函数值为为65；（9）由由于于结结点点9是是叶叶子子结结点点，同同时时结结点点9的的目目标标函函数数值值是是表表PT中中的极大值，所以，结点的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。对应的解即是问题的最优解，搜索结束。第10页，本讲稿共57页9.1.2 分支限界法的设计思想分支限界法的设计思想 假假设设求求解解最最大大化化问问题题，解解向向量量为为X=(x1,x2,xn)，其其中中，xi的的取取值值范范围围为为某某个个有有穷穷集集合合Si，|Si|=ri（1in）。在在使使用用分分支支限限界界法法搜搜索索问问题题的的解解空空间间树树时时，首首先先根根据据限限界界函函数数估估算算目目标标函函数数的的界界down,up，然然后后从从根根结结点点出出发发，扩扩展展根根结结点点的的r1个个孩孩子子结结点点，从从而而构构成成分分量量x1的的r1种种可可能能的的取取值值方方式式。对对这这r1个个孩孩子子结结点点分分别别估估算算可可能能取取得得的的目目标标函函数数值值bound(x1)，其其含含义义是是以以该该孩孩子子结结点点为为根根的的子子树树所所可可能能取取得得的的目目标标函函数数值值不不大大于于bound(x1)，也也就就是是部部分分解应满足：解应满足：bound(x1)bound(x1,x2)bound(x1,x2,xk)bound(x1,x2,xn)第11页，本讲稿共57页 若若某某孩孩子子结结点点的的目目标标函函数数值值超超出出目目标标函函数数的的界界，则则将将该该孩孩子子结结点点丢丢弃弃；否否则则，将将该该孩孩子子结结点点保保存存在在待待处处理理结结点点表表PT中中。从从表表PT中中选选取取使使目目标标函函数数取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，重重复复上上述述过过程程，当当到到达达一一个个叶叶子子结结点点时时，就就得得到到了了一一个个可可行行解解X=(x1,x2,xn)及及其目标函数值其目标函数值bound(x1,x2,xn)。如如果果bound(x1,x2,xn)是是表表PT中中目目标标函函数数值值最最大大的的结结点点，则则bound(x1,x2,xn)就就是是所所求求问问题题的的最最大大值值，(x1,x2,xn)就就是是问问题的最优解；题的最优解；如如果果bound(x1,x2,xn)不不是是表表PT中中目目标标函函数数值值最最大大的的结结点点，说说明明还还存存在在某某个个部部分分解解对对应应的的结结点点，其其上上界界大大于于bound(x1,x2,xn)。于于是是，用用bound(x1,x2,xn)调调整整目目标标函函数数的的下下界界，即即令令down=bound(x1,x2,xn)，并并将将表表PT中中超超出出目目标标函函数数下下界界down的的结结点点删删除除，然然后后选选取取目目标标函函数数值值取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，继继续续搜搜索索，直直到到某某个个叶叶子子结结点点的的目目标标函函数数值值在在表表PT中中最最大。大。第12页，本讲稿共57页分支限界法求解最大化问题的一般过程分支限界法求解最大化问题的一般过程分支限界法的一般过程分支限界法的一般过程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页，本讲稿共57页应用分支限界法的关键问题应用分支限界法的关键问题（1）如何确定合适的限界函数）如何确定合适的限界函数（2）如何组织）如何组织待处理结点表待处理结点表（3）如何确定最优解中的）如何确定最优解中的各个分量各个分量 第14页，本讲稿共57页分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表到某个叶子结点且该叶子结点的目标函数值在表PT中最大时中最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方法解决：法解决：对每个扩展结点保存该结点到根结点的路径；对每个扩展结点保存该结点到根结点的路径；在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构，在在求求得得最最优优解解时时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。从叶子结点不断回溯到根结点，以确定最优解中的各个分量。第15页，本讲稿共57页(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背包问题，为了对每个扩展结点保存该结点背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解到根结点的路径，将部分解(x1,xi)和该部分解的目标函数值都和该部分解的目标函数值都存储在待处理结点表存储在待处理结点表PT中，在搜索过程中表中，在搜索过程中表PT的状态如图的状态如图9.2所所示。示。第16页，本讲稿共57页(a)扩展根结点后扩展根结点后 (b)扩展结点扩展结点2后后(c)扩展结点扩展结点5后后 (d)扩展结点扩展结点6后，最优解为后，最优解为(1,0,1,0)65 图图9.3 方法方法确定确定0/1背包问题最优解的各分量背包问题最优解的各分量(0,76)(0,60)PTST(0,60)(1,70)PTST(0,76)(0,60)(0,69)(0,64)PTST(0,76)(1,70)(0,60)(0,64)(1,65)PTST(0,76)(1,70)(0,69)图图9.1所所示示0/1背背包包问问题题，为为了了在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构，设设一一个个表表ST，在在表表PT中中取取出出最最小小值值结结点点进进行行扩扩充充时时，将将最最小小值值结结点点存存储储到到表表ST中中，表表PT和和表表ST的的数数据据结结构构为为(物物品品i-1的的选选择择结结果果，ub)，在在搜搜索索过过程程中中表表PT和和表表ST的的状状态态如图如图9.3所示。所示。第17页，本讲稿共57页9.1.3 分支限界法的时间性能分支限界法的时间性能 分分支支限限界界法法和和回回溯溯法法实实际际上上都都属属于于蛮蛮力力穷穷举举法法，当当然然不不能能指指望望它它有有很很好好的的最最坏坏时时间间复复杂杂性性，遍遍历历具具有有指指数数阶阶个个结结点点的的解解空空间间树树，在最坏情况下，时间复杂性肯定为指数阶。在最坏情况下，时间复杂性肯定为指数阶。与与回回溯溯法法不不同同的的是是，分分支支限限界界法法首首先先扩扩展展解解空空间间树树中中的的上上层层结结点点，并并采采用用限限界界函函数数，有有利利于于实实行行大大范范围围剪剪枝枝，同同时时，根根据据限限界界函函数数不不断断调调整整搜搜索索方方向向，选选择择最最有有可可能能取取得得最最优优解解的的子子树树优优先先进进行行搜搜索索。所所以以，如如果果选选择择了了结结点点的的合合理理扩扩展展顺顺序序以以及及设计了一个好的限界函数，分支界限法可以快速得到问题的解。设计了一个好的限界函数，分支界限法可以快速得到问题的解。第18页，本讲稿共57页 分支限界法的较高效率是以付出一定代价为基础的，其工作分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，一个更好的限界函数通方式也造成了算法设计的复杂性。首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表使得算法的设计较为复杂；再次，算法要维护一个待处理结点表PTPT，并且需要在表，并且需要在表PTPT中快速查找取得极值的结点，等等。这都需中快速查找取得极值的结点，等等。这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。杂性是指数阶。第19页，本讲稿共57页9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题第20页，本讲稿共57页9.2.1 TSP问题问题 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城市经个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。历且仅经历一次然后回到出发城市，并要求所走的路程最短。271563134253984C=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页，本讲稿共57页 采用贪心法求得近似解为采用贪心法求得近似解为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页，本讲稿共57页部分解的目标函数值的计算方法部分解的目标函数值的计算方法 例例如如图图9.4所所示示无无向向图图，如如果果部部分分解解包包含含边边(1,4)，则则该该部部分分解解的的下下界界是是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。第23页，本讲稿共57页412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=1491152lb=1954lb=141142lb=16142lb=1845lb=151152lb=201分支限界法求解分支限界法求解TSP问题示例问题示例第24页，本讲稿共57页应用分支限界法求解图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页，本讲稿共57页（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页，本讲稿共57页（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页，本讲稿共57页（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页，本讲稿共57页(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页，本讲稿共57页算法算法9.1TSP问题问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3for(i=1;i=2)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=+=+kijpiEvrijjjjvrcrrclbpi21,11min1段的最短边段的最短边第第第32页，本讲稿共57页 应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点1，根据限界函数计算目标函数的值为14；（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页，本讲稿共57页（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页，本讲稿共57页（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页，本讲稿共57页6401lb=20231startlb=1402lb=1703lb=15图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)535lb=1636lb=188757lb=2258lb=16第36页，本讲稿共57页 为了在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表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页，本讲稿共57页算法算法9.2多段图的最短路径问题多段图的最短路径问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3for(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页，本讲稿共57页9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.1 9.3.1 任务分配问题任务分配问题 9.3.2 9.3.2 批处理作业调度问题批处理作业调度问题第39页，本讲稿共57页9.3.1 任务分配问题任务分配问题 任任务务分分配配问问题题要要求求把把n项项任任务务分分配配给给n个个人人，每每个个人人完完成成每每项项任任务务的的成成本本不不同同，要要求求分分配配总总成成本本最最小小的的最最优优分分配配方方案案。如如图图9.10所所示示是是一一个个任任务务分分配配的的成成本本矩矩阵。阵。C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵第40页，本讲稿共57页求最优分配成本的上界和下界求最优分配成本的上界和下界考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务将任务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页，本讲稿共57页设当前已对人员设当前已对人员1i分配了任务，并且获得了成本分配了任务，并且获得了成本v，则限界函，则限界函数可以定义为：数可以定义为：（式（式9.4）第42页，本讲稿共57页（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页，本讲稿共57页（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页，本讲稿共57页（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，将任