第9章分支限界法.ppt

算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法9.4 实验项目实验项目——电路布线问题电路布线问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.1 概概 述述 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2））9.1.2 分支限界法的设计思想分支限界法的设计思想9.1.3 分支限界法的时间性能分支限界法的时间性能算法设计与分析算法设计与分析清华大学出版社清华大学出版社 分分支支限限界界法法首首先先确确定定一一个个合合理理的的限限界界函函数数，，并并根根据据限限界界函函数数确确定定目目标标函函数数的的界界[down, up] 然然后后，，按按照照广广度度优优先先策策略略遍遍历历问问题题的的解解空空间间树树，，在在分分支支结结点点上上，，依依次次搜搜索索该该结结点点的的所所有有孩孩子子结结点点，，分分别别估估算算这这些些孩孩子子结结点点的的目目标标函函数数的的可可能能取取值值，，如如果果某某孩孩子子结结点点的的目目标标函函数数可可能能取取得得的的值值超超出出目目标标函函数数的的界界，，则则将将其其丢丢弃弃，，因因为为从从这这个个结结点点生生成成的的解解不不会会比比目目前前已已经经得得到到的的解解更更好好；；否否则则，，将将其其加加入入待待处处理理结结点点表表（（以以下下简简称称表表PT））中中。

依依次次从从表表PT中中选选取取使使目目标标函函数数的的值值取取得得极极值值的的结结点点成成为为当当前前扩扩展展结结点点，，重重复复上上述述过过程程，，直到找到最优解直到找到最优解9.1.1 解空间树的动态搜索（解空间树的动态搜索（2）） 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 随着这个遍历过程的不断深入，表随着这个遍历过程的不断深入，表PT中所估算的目标函中所估算的目标函数的界越来越接近问题的最优解当搜索到一个叶子结点时数的界越来越接近问题的最优解当搜索到一个叶子结点时，，如果该结点的目标函数值是表如果该结点的目标函数值是表PT中的极值（对于最小化问题，中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表调整下界），依次考察表PT中的结点，将超出目标函数界的中的结点，将超出目标函数界的结点丢弃，然后从表结点丢弃，然后从表PT中选取使目标函数取得极值的结点继中选取使目标函数取得极值的结点继续进行扩展。

续进行扩展算法设计与分析算法设计与分析清华大学出版社清华大学出版社 例例：：0/1背背包包问问题题假假设设有有4个个物物品品，，其其重重量量分分别别为为(4, 7, 5, 3)，，价价值值分分别别为为(40, 42, 25, 12)，，背背包包容容量量W=10首首先先，，将将给给定物品按单位重量价值从大到小排序，结果如下：定物品按单位重量价值从大到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124算法设计与分析算法设计与分析清华大学出版社清华大学出版社 应用贪心法求得近似解为应用贪心法求得近似解为(1, 0, 0, 0)，获得的价，获得的价值为值为40，这可以作为，这可以作为0/1背包问题的下界背包问题的下界 如何求得如何求得0/1背包问题的一个合理的上界呢？考背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第虑最好情况，背包中装入的全部是第1个物品且可以个物品且可以将背包装满，则可以得到一个非常简单的上界的计将背包装满，则可以得到一个非常简单的上界的计算方法：算方法：ub=W××(v1/w1)=10××10=100。

于是，得到了于是，得到了目标函数的界目标函数的界[40, 100] 限界函数为：限界函数为： 算法设计与分析算法设计与分析清华大学出版社清华大学出版社×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=6523456789×1分支限界法求解分支限界法求解0/1背包问题背包问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社 分分支支限限界界法法求求解解0/1背背包包问问题题，，其其搜搜索索空空间间如如图图9.1所所示，具体的搜索过程如下：示，具体的搜索过程如下：（（1））在在根根结结点点1，，没没有有将将任任何何物物品品装装入入背背包包，，因因此此，，背背包包的的重重量量和和获获得得的的价价值值均均为为0，，根根据据限限界界函函数数计计算算结结点点1的的目目标函数值为标函数值为10×10=100；；（（2））在在结结点点2，，将将物物品品1装装入入背背包包，，因因此此，，背背包包的的重重量量为为4，，获获得得的的价价值值为为40，，目目标标函函数数值值为为40 + (10-4)×6=76，，将将结结点点2加加入入待待处处理理结结点点表表PT中中；；在在结结点点3，，没没有有将将物物品品1装装入入背背包包，，因因此此，，背背包包的的重重量量和和获获得得的的价价值值仍仍为为0，，目目标标函函数值为数值为10×6＝＝60，将结点，将结点3加入表加入表PT中；中；（（3））在在表表PT中中选选取取目目标标函函数数值值取取得得极极大大的的结结点点2优优先先进进行搜索；行搜索； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社（（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中；中；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（（7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行优先进行搜索；搜索；（（8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，背包的重量为12，不满足约束条件，将结点，不满足约束条件，将结点8丢弃；在结点丢弃；在结点9，没有将物，没有将物品品4装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点6相相同，同，目标函数值为目标函数值为65；；（（9））由由于于结结点点9是是叶叶子子结结点点，，同同时时结结点点9的的目目标标函函数数值值是是表表PT中中的的极极大大值值，，所所以以，，结结点点9对对应应的的解解即即是是问问题题的的最最优优解解，，搜索结束。

搜索结束算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.1.2 分支限界法的设计思想分支限界法的设计思想 假假设设求求解解最最大大化化问问题题，，解解向向量量为为X=(x1, x2, …, xn)，，其其中中，，xi的的取取值值范范围围为为某某个个有有穷穷集集合合Si，，|Si|=ri（（1≤i≤n））在在使使用用分分支支限限界界法法搜搜索索问问题题的的解解空空间间树树时时，，首首先先根根据据限限界界函函数数估估算算目目标标函函数数的的界界[down, up]，，然然后后从从根根结结点点出出发发，，扩扩展展根根结结点点的的r1个个孩孩子子结结点点，，从从而而构构成成分分量量x1的的r1种种可可能能的的取取值值方方式式对对这这r1个个孩孩子子结结点点分分别别估估算算可可能能取取得得的的目目标标函函数数值值bound(x1)，，其其含含义义是是以以该该孩孩子子结结点点为为根根的的子子树树所所可可能能取取得得的的目目标标函数值不大于函数值不大于bound(x1)，，也就是部分解应满足：也就是部分解应满足： bound(x1)≥bound(x1, x2)≥ … ≥bound(x1, x2, …, xk)≥ … ≥bound(x1, x2, …, xn)算法设计与分析算法设计与分析清华大学出版社清华大学出版社 若若某某孩孩子子结结点点的的目目标标函函数数值值超超出出目目标标函函数数的的界界，，则则将将该该孩孩子子结结点点丢丢弃弃；；否否则则，，将将该该孩孩子子结结点点保保存存在在待待处处理理结结点点表表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中最大。

中最大 算法设计与分析算法设计与分析清华大学出版社清华大学出版社分支限界法求解最大化问题的一般过程分支限界法求解最大化问题的一般过程分支限界法的一般过程分支限界法的一般过程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的结点删除；的结点删除；算法设计与分析算法设计与分析清华大学出版社清华大学出版社应用分支限界法的关键问题应用分支限界法的关键问题（（1）如何确定合适的）如何确定合适的限界函数限界函数（（2）如何组织）如何组织待处理结点表待处理结点表（（3）如何确定最优解中的）如何确定最优解中的各个分量各个分量 算法设计与分析算法设计与分析清华大学出版社清华大学出版社分支限界法对问题的解空间树中结点的处理是跳跃式的，回分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表搜索到某个叶子结点且该叶子结点的目标函数值在表PT中中最大时（假设求解最大化问题），求得了问题的最优值，但最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。

这是，却无法求得该叶子结点对应的最优解中的各个分量这个问题可以用如下方法解决：个问题可以用如下方法解决：①① 对每个扩展结点保存该结点到根结点的路径；对每个扩展结点保存该结点到根结点的路径；②② 在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构，，在在求求得得最最优优解解时时，，从叶子结点不断回溯到根结点，以确定最优解中的各个分量从叶子结点不断回溯到根结点，以确定最优解中的各个分量 算法设计与分析算法设计与分析清华大学出版社清华大学出版社(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所示。

所示算法设计与分析算法设计与分析清华大学出版社清华大学出版社(a) 扩展根结点后扩展根结点后 (b) 扩展结点扩展结点2后后(c) 扩扩展展结结点点5后后 (d) 扩扩展展结结点点6后后，，最最优优解解为为(1,0,1,0)65 图图9.3 方法方法②②确定确定0/1背包问题最优解的各分量背包问题最优解的各分量(0,<1,1>76) (0,<1,0>60)PTST(0,<1,0>60) (1,<2,0>70)PTST(0,<1,1>76)(0,<1,0>60) (0,<3,1>69) (0,<3,0>64)PTST(0,<1,1>76) (1,<2,0>70)(0,<1,0>60) (0,<3,0>64) (1,<4,0>65)PTST(0,<1,1>76) (1,<2,0>70) (0,<3,1>69)图图9.1所所示示0/1背背包包问问题题，，为为了了在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构，，设设一一个个表表ST，，在在表表PT中中取取出出最最小小值值结结点点进进行行扩扩充充时时，，将将最最小小值值结结点点存存储储到到表表ST中中，，表表PT和和表表ST的的数数据据结结构构为为(物物品品i-1的的选选择择结结果果，，<物物品品i, 物物品品i的的选选择择结结果果>ub)，，在在搜搜索索过过程中表程中表PT和表和表ST的状态如图的状态如图9.3所示。

所示算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.1.3 分支限界法的时间性能分支限界法的时间性能 分分支支限限界界法法和和回回溯溯法法实实际际上上都都属属于于蛮蛮力力穷穷举举法法，，当当然然不不能能指指望望它它有有很很好好的的最最坏坏时时间间复复杂杂性性，，遍遍历历具具有有指指数数阶阶个个结结点点的的解解空空间间树树，，在在最最坏坏情情况况下下，，时时间间复复杂杂性性肯肯定定为指数阶为指数阶 与与回回溯溯法法不不同同的的是是，，分分支支限限界界法法首首先先扩扩展展解解空空间间树树中中的的上上层层结结点点，，并并采采用用限限界界函函数数，，有有利利于于实实行行大大范范围围剪剪枝枝，，同同时时，，根根据据限限界界函函数数不不断断调调整整搜搜索索方方向向，，选选择择最最有有可可能能取取得得最最优优解解的的子子树树优优先先进进行行搜搜索索所所以以，，如如果果选选择择了了结结点点的的合合理理扩扩展展顺顺序序以以及及设设计计了了一一个个好好的的限限界界函函数数，，分支界限法可以快速得到问题的解分支界限法可以快速得到问题的解算法设计与分析算法设计与分析清华大学出版社清华大学出版社 分支限界法的较高效率是以付出一定代价为基础的，其分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。

首先，一个更好的限工作方式也造成了算法设计的复杂性首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，由于分支限界法对解一个好的限界函数；其次，由于分支限界法对解空间树中结空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表杂；再次，算法要维护一个待处理结点表PTPT，并且需要在表，并且需要在表PTPT中快速查找取得极值的结点，等等这都需要较大的存储中快速查找取得极值的结点，等等这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。

阶 算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.2.1 TSP问题问题 TSPTSP问题是指旅行家要旅行问题是指旅行家要旅行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 无向图及其代价矩阵无向图及其代价矩阵算法设计与分析算法设计与分析清华大学出版社清华大学出版社 采用贪心法求得近似解为采用贪心法求得近似解为1→3→5→4→2→1，其路径，其路径长度为长度为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]需要强调的是，这个解并不是一个合法的选择（可能没有需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。

构成哈密顿回路），它仅仅给出了一个参考下界 算法设计与分析算法设计与分析清华大学出版社清华大学出版社部分解的目标函数值的计算方法部分解的目标函数值的计算方法 例例如如图图9.4所所示示无无向向图图，，如如果果部部分分解解包包含含边边(1, 4)，，则则该该部部分分解的下界是解的下界是lb=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16 算法设计与分析算法设计与分析清华大学出版社清华大学出版社41→2lb=142356781×startlb=141→3lb=141→4lb=161→5lb=192→3lb=162→4lb=162→5lb=193→2lb=163→4lb=153→5lb=14×9115→2lb=195→4lb=1411×4→2lb=1614→2lb=184→5lb=1511×5→2lb=201×分支限界法求解分支限界法求解TSP问题示例问题示例算法设计与分析算法设计与分析清华大学出版社清华大学出版社应用分支限界法求解图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丢弃； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社（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中；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（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；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（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对应的解1→3→5→4→2→1即是TSP问题的最优解，搜索过程结束。

算法设计与分析算法设计与分析清华大学出版社清华大学出版社(g) 扩展结点扩展结点16后的状态，最优解为后的状态，最优解为1→3→5→4→2→1图图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后的状态后的状态算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法9.1——TSP问题问题 1．根据限界函数计算目标函数的下界．根据限界函数计算目标函数的下界down；；采用贪心法得到上界采用贪心法得到上界up；； 2．．将待处理结点表将待处理结点表PT初始化为空；初始化为空； 3．．for (i=1; i<=n; i++) x[i]=0; 4．．k=1; x[1]=1; //从顶点从顶点1出发求解出发求解TSP问题问题 5．．while (k>=1) 5.1 i=k+1; 5.2 x[i]=1; 5.3 while (x[i]<=n) 5.3.1 如果路径上顶点不重复，则如果路径上顶点不重复，则 5.3.1.1 根据式根据式9.2计算目标函数值计算目标函数值lb；； 5.3.1.2 if (lb<=up) 将路径上的顶点和将路径上的顶点和lb值存储在表值存储在表PT中；中； 5.3.2 x[i]=x[i]+1; 5.4 若若i=n且叶子结点的目标函数值在表且叶子结点的目标函数值在表PT中最小中最小 则将该叶子结点对应的最优解输出；则将该叶子结点对应的最优解输出； 5.5否则，若否则，若i=n，，则在表则在表PT中取叶子结点的目标函数值最小的结点中取叶子结点的目标函数值最小的结点lb，， 令令up=lb，，将表将表PT中目标函数值中目标函数值lb超出超出up的结点删除；的结点删除； 5.6 k=表表PT中中lb最小的路径上顶点个数；最小的路径上顶点个数；算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.2.2 多段图的最短路径问题多段图的最短路径问题 设设图图G=(V, E)是是一一个个带带权权有有向向连连通通图图，，如如果果把把顶顶点点集集合合V划划分分成成k个个互互不不相相交交的的子子集集Vi（（2≤k≤n, 1≤i≤k）），，使使得得E中中的的任任何何一一条条边边(u, v)，，必必有有u∈∈Vi，，v∈∈Vi+m（（1≤i＜＜k, 1＜＜i+m≤k）），，则则称称图图G为多段图，称为多段图，称s∈∈V1为源点，为源点，t∈∈Vk为终点。

为终点1203456789492387684756866537多段图的最短路径问题是求从源点到终点的最小代价路径多段图的最短路径问题是求从源点到终点的最小代价路径算法设计与分析算法设计与分析清华大学出版社清华大学出版社 对对 图图 9.7所所 示示 多多 段段 图图 应应 用用 贪贪 心心 法法 求求 得得 近近 似似 解解 为为0→2→5→8→9，，其其路路径径代代价价为为2+7+6+3=18，，这这可可以以作作为为多多段段图图最最短短路路径径问问题题的的上上界界把把每每一一段段最最小小的的代代价价相相加加，，可可以以得得到到一一个个非非常常简简单单的的下下界界，，其其路路径径长长度度为为2+4+5+3=14于是，得到了目标函数的界于是，得到了目标函数的界[14, 18] 由由于于多多段段图图将将顶顶点点划划分分为为k个个互互不不相相交交的的子子集集，，所所以以，，多多段段图图划划分分为为k段段，，一一旦旦某某条条路路径径的的一一些些段段被被确确定定后后，，就就可可以以并并入入这这些些信信息息并并计计算算部部分分解解的的目目标标函函数数值值的的下下界界一一般般情情况况下下，，对对于于一一个个正正在在生生成成的的路路径径，，假假设设已已经经确确定定了了i段段（（1≤i≤k）），，其其路路径径为为(r1, r2, …, ri, ri+1)，，此此时时，，该该部部分分解解的目标函数值的计算方法即限界函数如下：的目标函数值的计算方法即限界函数如下： å åå å+ += =+ +>Î>Î< <= =+ ++ += =+ +kijpiEvrijjjjvrcrrclbpi21,11]}][[{min]][[1段的最短边段的最短边第第＋＋算法设计与分析算法设计与分析清华大学出版社清华大学出版社 应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点1，根据限界函数计算目标函数的值为18；（2）在结点2，第1段选择边<0, 1>，目标函数值为lb=4+8+5+3=20，超出目标函数的界，将结点2丢弃；在结点3，第1段选择边<0, 2>，目标函数值为lb=2+6+5+3=16，将结点3加入待处理结点表PT中；在结点4，第1段选择边<0, 3>，目标函数值为lb=3+4+5+3=15，将结点4加入表PT中；（3）在表PT中选取目标函数值极小的结点4优先进行搜索；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（4）在结点5，第2段选择边<3, 5>，目标函数值为lb=3+4+6+3=16，将结点5加入表PT中；在结点6，第2段选择边<3, 6>，目标函数值为lb=3+7+5+3=18，将结点6加入表PT中；（5）在表PT中选取目标函数值极小的结点3优先进行搜索；（6）在结点7，第2段选择边<2, 4>，目标函数值为lb=2+6+5+3=16，将结点7加入表PT中；在结点8，第2段选择边<2, 5>，目标函数值为lb=2+7+6+3=18，将结点8加入表PT中；在结点9，第2段选择边<2, 6>，目标函数值为lb=2+8+5+3=18，将结点9加入表PT中；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（7）在表PT中选取目标函数值极小的结点5优先进行搜索；（8）在结点10，第3段选择边<5, 7>，可直接确定第4段的边<7, 9>，目标函数值为lb=3+4+8+7=22，为一个可行解但超出目标函数的界，将其丢弃；在结点11，第3段选择边<5, 8>，可直接确定第4段的边<8, 9>，目标函数值为lb=3+4+6+3=16，为一个较好的可行解。

由于结点11是叶子结点，并且其目标函数值是表PT中最小的，所以，结点11代表的解即是问题的最优解，搜索过程结束算法设计与分析算法设计与分析清华大学出版社清华大学出版社640→1lb=20231startlb=180→2lb=160→3lb=15×图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(×表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)72→4lb=1682→5lb=1892→6lb=1853→5lb=163→6lb=181110 5→7lb=225→8lb=16×算法设计与分析算法设计与分析清华大学出版社清华大学出版社 为了在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表ST，，在表在表PT中取出最小值结点进行扩充时，将最小值结点存储到表中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表中，表PT和表和表ST的数据结构为的数据结构为(第第i段，段，<第第i段顶点段顶点, 第第i+1段段顶点顶点>lb)，，在搜索过程中表在搜索过程中表PT和表和表ST的状态如下：的状态如下：(b) 扩展结点扩展结点3后的状态后的状态(d) 扩展结点扩展结点5后的状态，最优解为后的状态，最优解为0→3→5→8→9图图9.9 多段图的最短路径问题最优解的确定多段图的最短路径问题最优解的确定(1,<0,2>16) (1,<0,3>15)(1,<0,2>16) (2,<2,4>16) (2,<2,5>18) (2,<2,6>18)(1,<0,3>15)(2,<2,4>16) (2,<2,5>18) (2,<2,6>18) (2,<3,5>16) (2,<3,6>18)(1,<0,3>15) (1,<0,2>16)(2,<2,4>16) (2,<2,5>18) (2,<2,6>18) (2,<3,6>18) (3,<5,8>16)(1,<0,3>15) (1,<0,2>16) (2,<3,5>16)(a) 扩展根结点后的状态扩展根结点后的状态 PT ST ST PT (c) 扩展结点扩展结点4后的状态后的状态ST ST 回溯过程是：(3,<5, 8>16)→(2,<3, 5>16)→(1,<0, 3>15)。

算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法9.2——多段图的最短路径问题多段图的最短路径问题 1．根据限界函数计算目标函数的下界．根据限界函数计算目标函数的下界down；；采用贪心法得到上界采用贪心法得到上界up；； 2．．将待处理结点表将待处理结点表PT初始化为空；初始化为空； 3．．for (i=1; i<=k; i++) x[i]=0; 4．．i=1; u=0; //求解第求解第i段段 5．．while (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++;算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.1 9.3.1 任务分配问题任务分配问题 9.3.2 9.3.2 批处理作业调度问题批处理作业调度问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.3.1 任务分配问题任务分配问题 任任务务分分配配问问题题要要求求把把n项项任任务务分分配配给给n个个人人，，每每个个人人完完成成每每项项任任务务的的成成本本不不同同，，要要求求分分配配总总成成本本最最小小的的最最优优分分配配方方案案。

如如图图9.10所所示示是是一一个个任任务务分分配配的成本矩阵的成本矩阵 C＝＝9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵算法设计与分析算法设计与分析清华大学出版社清华大学出版社求最优分配成本的上界和下界求最优分配成本的上界和下界考虑任意一个可行解，例如矩阵中的对角线是一个合法的选考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务择，表示将任务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]之间的某个值之间的某个值算法设计与分析算法设计与分析清华大学出版社清华大学出版社设当前已对人员设当前已对人员1～～i分配了任务，并且获得了成本分配了任务，并且获得了成本v，，则限界函数可以定义为：则限界函数可以定义为： （式（式9.4）） 算法设计与分析算法设计与分析清华大学出版社清华大学出版社（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； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社（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丢弃；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（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对应的解即是问题的最优解，搜索结束。

算法设计与分析算法设计与分析清华大学出版社清华大学出版社4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=173→clb=134→dlb=13图图9.11 分支限界法求解任务分配问题示例分支限界法求解任务分配问题示例(×表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)23567891213111××××算法设计与分析算法设计与分析清华大学出版社清华大学出版社 为了在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表ST，，在表在表PT中取出最小值结点进行扩充时，将最小值结点中取出最小值结点进行扩充时，将最小值结点存储到表存储到表ST中，表中，表PT和表和表ST的数据结构为的数据结构为(人员人员i- -1分配的分配的任务任务,<任务任务k, 人员人员i>lb)(e) 扩展结点扩展结点11后的状态，最优解为后的状态，最优解为2→a 1→b 3→c 4→d图图9.12 任务分配问题最优解的确定任务分配问题最优解的确定(0,<2, a>10)(2,<1, b>13) (2,<3, b>10) (2,<4, b>14)(0,<2, a>10)(2,<1, b>13) (2,<4, b>14) (3,<1, c>14)(0,<2, a>10) (2,<3, b>10) (2,<4, b>14) (3,<1, c>14) (1,<3, c>13)(0,<2, a>10) (2,<3, b>10) (2,<1, b>13) (0,<2, a>10) (2,<3, b>10) (2,<1, b>13) (1,<3, c>13)(a) 扩展根结点后的状态扩展根结点后的状态 (b) 扩展结点扩展结点3后的状态后的状态 PTSTPTST PT (c) 扩展结点扩展结点7后的状态后的状态 (d) 扩展结点扩展结点6后的状态后的状态(2,<4, b>14) (3,<1, c>14) (3,<4, d>13)PTSTPTST ST 回溯过程是：(3,<4, d>13)→(1,<3, c>13)→(2,<1, b>13)→(0,<2, a>10) 。

算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法9.3——任务分配问题任务分配问题 1．根据限界函数计算目标函数的下界．根据限界函数计算目标函数的下界down；；采用贪心法得到上界采用贪心法得到上界up；； 2．．将待处理结点表将待处理结点表PT初始化为空；初始化为空； 3．．for (i=1; i<=n; i++) x[i]=0; 4．．k=1; i=0; //为第为第k个人分配任务，个人分配任务，i为第为第k-1个人分配的任务个人分配的任务 5．．while (k>=1) 5.1 x[k]=1; 5.2 while (x[k]<=n) 5.2.1 如果人员如果人员k分配任务分配任务x[k]不发生冲突，则不发生冲突，则 5.2.1.1 根据式根据式9.4计算目标函数值计算目标函数值lb; 5.2.1.2 若若lb<=up，，则将则将i,lb存储在表存储在表PT中；中； 5.2.2 x[k]=x[k]+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最小的结点的最小的结点的x[k]值；值； 5.6 k=表表PT中中lb最小的结点的最小的结点的k值；值；k++;算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.3.2 批处理作业调度问题批处理作业调度问题 给给定定n个个作作业业的的集集合合J={J1, J2, …, Jn}，，每每个个作作业业都都有有3项项任任务务分分别别在在3台台机机器器上上完完成成，，作作业业Ji需需要要机机器器j的的处处理理时时间间为为tij（（1≤i≤n, 1≤j≤3）），，每每个个作作业业必必须须先先由由机机器器1处处理理，，再再由由机机器器2处处理理，，最最后后由由机机器器3处处理理。

批批处处理理作作业业调调度度问问题题要要求求确确定定这这n个个作作业业的的最最优优处处理理顺顺序序，，使使得得从从第第1个个作作业业在在机机器器1上上处处理理开开始始，，到到最最后后一一个个作作业业在在机机器器3上上处处理理结结束束所所需需的的时时间间最少 显显然然，，批批处处理理作作业业的的一一个个最最优优调调度度应应使使机机器器1没没有有空空闲闲时时间间，，且且机机器器2和和机机器器3的的空空闲闲时时间间最最小小可可以以证证明明，，存存在在一一个个最最优优作作业业调调度度使使得得在在机机器器1、、机机器器2和和机机器器3上上作作业业以以相相同同次序完成次序完成 算法设计与分析算法设计与分析清华大学出版社清华大学出版社T＝ 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4机器1 机器2 机器3 若处理顺序为若处理顺序为(J2, J3, J1, J4)，，则从作业则从作业2在机器在机器1处理开处理开始到作业始到作业4在机器在机器3处理完成的调度方案如图处理完成的调度方案如图9.14所示。

所示 J2:10 J3:9 J1:5 J4:7机器机器1机器机器2机器机器3 图图9.14 批处理调度问题的调度方案批处理调度问题的调度方案空闲空闲:10 J2:5 J3:9 J1:7 J4:8空闲空闲:15 J2:2 J3:5 J1:9 J4:10 设设J={J1, J2, J3, J4}是是4个待处理的作业，每个作业的处个待处理的作业，每个作业的处理顺序相同，即先在机器理顺序相同，即先在机器1上处理，然后在机器上处理，然后在机器2上处理，最上处理，最后在机器后在机器3上处理，需要的处理时间如图上处理，需要的处理时间如图9.13所示算法设计与分析算法设计与分析清华大学出版社清华大学出版社 一般情况下，对于一个已安排的作业集合M {1, 2, …, n}，|M|=k，即已安排了k个作业，设sum1[k]表示机器1完成k个作业的处理时间，sum2[k]表示机器2完成k个作业的处理时间，现在要处理作业k+1，此时，该部分解的目标函数值的下界计算方法如下：（1）sum1[k+1]=sum1[k]+ tk1（2）（3）sum2[k+1]=max{sum1[k+1], sum2[k]} + tk2 批处理作业调度问题的限界函数批处理作业调度问题的限界函数考虑理想情况，机器1和机器2无空闲，最后处理的恰好是在机器3上处理时间最短的作业。

例如，以作业Ji开始的处理顺序，估算处理所需的最短时间是：算法设计与分析算法设计与分析清华大学出版社清华大学出版社应用分支限界法求解图9.13所示批处理作业调度问题，其搜索空间如图9.15所示，具体的搜索过程如下： （1）在根结点，将sum1[0]和sum2[0]分别初始化为0； （2）在结点2，以作业J1开始处理，则sum1[1]=5，目标函数值为5+(7+5+9+8)+2=36，sum2[1]=5+7=12，将结点2加入待处理结点表PT中；在结点3，以作业J2开始处理， 则sum1[1]=10，目标函数值为10+(7+5+9+8)+5=44，sum2[1]=10+2=12，将结点3加入表PT中；在结点4，以作业J3开始处理，则sum1[1]=9，目标函数值为9+(7+5+9+8)+2=40，sum2[1]=9+9=18，将结点4加入表PT中；在结点5，以作业J4开始处理，则sum1[1]=7，目标函数值为7+(7+5+9+8)+2=38，sum2[1]=7+8=15，将结点5加入表PT中；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（3）在表PT中选取目标函数值极小的结点2优先进行搜索；（4）在结点6，准备处理作业J2，则sum1[2]=5+10=15，目标函数值为15+(5+9+8)+5=42，sum2[2]=15+5=20，将结点6加入表PT中；在结点7，准备处理作业J3，则sum1[2]=5+9=14，目标函数值为14+(5+9+8)+2=38，sum2[2]=14+9=22，将结点7加入表PT中；在结点8，准备处理作业J4，则sum1[2]=5+7=12，目标函数值为12+(5+9+8)+2=36，sum2[2]=12+8=20，将结点8加入表PT中；（5）在表PT中选取目标函数值极小的结点8优先进行搜索；（6）在结点9，准备处理作业J2，则sum1[3]=12+10=22，目标函数值为22+(5+9)+5=41，sum2[3]=22+5=27，将结点9加入表PT中；在结点10，准备处理作业J3，则sum1[3]=12+9=21，目标函数值为21+(5+9)+2=37，sum2[3]=21+9=30，将结点10加入表PT中；算法设计与分析算法设计与分析清华大学出版社清华大学出版社（7）在表PT中选取目标函数值极小的结点10优先进行搜索；（8）在结点11，准备处理作业J2，则sum1[4]=21+10=31，目标函数值为31+5=36，sum2[4]=31+5=36，由于结点11是叶子结点，并且目标函数值在表PT中最小，则结点11代表的解即是问题的最优解，sum2[4]是机器2完成所有4个作业的时间，则机器3完成所有4个作业的时间是sum2[4]+t23=36+2=38。

搜索过程结束算法设计与分析算法设计与分析清华大学出版社清华大学出版社J4, sum1=7lb=38sum2=152J1, sum1=5lb=36sum2=12图图9.15 分支限界法求解批处理作业调度问题的示例分支限界法求解批处理作业调度问题的示例1startsum1=0, sum2=03J2, sum1=10lb=44sum2=124J3, sum1=9lb=40sum2=1856J1J2, sum1=15lb=42sum2=207J1J3, sum1=14lb=38sum2=228J1J4, sum1=12lb=36sum2=209J1J4J2, sum1=22lb=41sum2=2710J1J4J3, sum1=21lb=37sum2=3011J1J4J3J2, sum1=31lb=36sum2=36算法设计与分析算法设计与分析清华大学出版社清华大学出版社9.4 实验项目实验项目——电路布线问题电路布线问题 1. 实验题目实验题目 印刷电路板将布线区域划分成n×n个方格精确的电路布线问题要求确定连接方格a到方格b的最短布线方案在布线时，电路只能沿着直线或直角布线，也就是不允许线路交叉。

2. 实验目的实验目的 （1）进一步掌握分支限界法的设计思想，掌握限界函数的设计技巧； （2）考察分支限界法求解问题的有效程度，并与回溯法进行对比；算法设计与分析算法设计与分析清华大学出版社清华大学出版社 （3）理解这样一个观点：好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解 3. 实验要求实验要求 （1）对电路布线问题建立合理的模型，通过实验确定一个合理的限界函数； （2）设计算法实现电路布线问题； （3）设计测试数据，统计搜索空间的结点数。