第9章分支限界法

1、算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.4 实验项目实验项目电路布线问题电路布线问题 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 9.1 概概 述述 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2） 9.1.2 分支限界法的设计思想分支限界法的设计思想 9.1.3 分支限界法的时间性能分支限界法的时间性能 算法设计与分析算法设计与分析清华大学出版社清华大学出版

2、社 第9章分支限界法 分支限界法首先确定一个合理的限界函数，并根据限分支限界法首先确定一个合理的限界函数，并根据限 界函数确定目标函数的界界函数确定目标函数的界down, up 。然后，按照广度优先。然后，按照广度优先 策略遍历问题的解空间树，在分支结点上，依次搜索该结策略遍历问题的解空间树，在分支结点上，依次搜索该结 点的所有孩子结点，分别估算这些孩子结点的目标函数的点的所有孩子结点，分别估算这些孩子结点的目标函数的 可能取值，如果某孩子结点的目标函数可能取得的值超出可能取值，如果某孩子结点的目标函数可能取得的值超出 目标函数的界，则将其丢弃，因为从这个结点生成的解不目标函数的界，则将其丢弃

3、，因为从这个结点生成的解不 会比目前已经得到的解更好；否则，将其加入待处理结点会比目前已经得到的解更好；否则，将其加入待处理结点 表（以下简称表表（以下简称表PT）中。依次从表）中。依次从表PT中选取使目标函数的中选取使目标函数的 值取得极值的结点成为当前扩展结点，重复上述过程，直值取得极值的结点成为当前扩展结点，重复上述过程，直 到找到最优解。到找到最优解。 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2） 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 随着这个遍历过程的不断深入，表随着这个遍历过程的不断深入，表PT中所估算的目标函中所估算的目标函 数的

4、界越来越接近问题的最优解。当搜索到一个叶子结点时数的界越来越接近问题的最优解。当搜索到一个叶子结点时 ，如果该结点的目标函数值是表，如果该结点的目标函数值是表PT中的极值（对于最小化问中的极值（对于最小化问 题，是极小值；对于最大化问题，是极大值），则该叶子结题，是极小值；对于最大化问题，是极大值），则该叶子结 点对应的解就是问题的最优解；否则，根据这个叶子结点调点对应的解就是问题的最优解；否则，根据这个叶子结点调 整目标函数的界（对于最小化问题，调整上界；对于最大化整目标函数的界（对于最小化问题，调整上界；对于最大化 问题，调整下界），依次考察表问题，调整下界），依次考察表PT中的结点，将超

5、出目标函中的结点，将超出目标函 数界的结点丢弃，然后从表数界的结点丢弃，然后从表PT中选取使目标函数取得极值的中选取使目标函数取得极值的 结点继续进行扩展。结点继续进行扩展。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 例：例：0/1背包问题。假设有背包问题。假设有4个物品，其重量分别为个物品，其重量分别为(4, 7, 5, 3)，价值分别为，价值分别为(40, 42, 25, 12)，背包容量，背包容量W=10。首先，将给。首先，将给 定物品按单位重量价值从大到小排序，结果如下：定物品按单位重量价值从大到小排序，结果如下： 物品物品重量重量(w)价值价值(v)

6、 价值价值/重量重量 (v/w) 144010 27426 35255 43124 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 应用贪心法求得近似解为应用贪心法求得近似解为(1, 0, 0, 0)，获得的价，获得的价 值为值为40，这可以作为，这可以作为0/1背包问题的下界。背包问题的下界。 如何求得如何求得0/1背包问题的一个合理的上界呢？考背包问题的一个合理的上界呢？考 虑最好情况，背包中装入的全部是第虑最好情况，背包中装入的全部是第1个物品且可以个物品且可以 将背包装满，则可以得到一个非常简单的上界的计将背包装满，则可以得到一个非常简单的上界的计 算方法：

7、算方法：ub=W(v1/w1)=1010=100。于是，得到。于是，得到 了目标函数的界了目标函数的界40, 100。 限界函数为：限界函数为： )()( 11 ii wvwWvub 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 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 23 45 6 7 8 9 1 分支限界法求解分支限界法求解0/1背包

8、问题背包问题 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 分支限界法求解分支限界法求解0/1背包问题，其搜索空间如图背包问题，其搜索空间如图9.1所所 示，具体的搜索过程如下：示，具体的搜索过程如下： （1）在根结点）在根结点1，没有将任何物品装入背包，因此，背包，没有将任何物品装入背包，因此，背包 的重量和获得的价值均为的重量和获得的价值均为0，根据限界函数计算结点，根据限界函数计算结点1的目的目 标函数值为标函数值为1010=100； （2）在结点）在结点2，将物品，将物品1装入背包，因此，背包的重量为装入背包，因此，背包的重量为4， 获得的价值为获得的价值

9、为40，目标函数值为，目标函数值为40 + (10-4)6=76，将结，将结 点点2加入待处理结点表加入待处理结点表PT中；在结点中；在结点3，没有将物品，没有将物品1装入装入 背包，因此，背包的重量和获得的价值仍为背包，因此，背包的重量和获得的价值仍为0，目标函数，目标函数 值为值为10660，将结点，将结点3加入表加入表PT中；中； （3）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进优先进 行搜索；行搜索； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （4）在结点）在结点4，将物品，将物品2装入背包，因此，背包的重量为装

10、入背包，因此，背包的重量为 11，不满足约束条件，将结点，不满足约束条件，将结点4丢弃；在结点丢弃；在结点5，没有将，没有将物物 品品2装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点2相相 同，目标函数值为同，目标函数值为40 + (10-4)5=70，将结点，将结点5加入表加入表PT 中；中； （5）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5优先进行优先进行 搜索；搜索； （6）在结点）在结点6，将物品，将物品3装入背包，因此，背包的重量为装入背包，因此，背包的重量为9， 获得的价值为获得的价值为65，目标函数值为，

11、目标函数值为65 + (10-9)4=69，将结，将结 点点6加入表加入表PT中；在结点中；在结点7，没有将物品，没有将物品3装入背包，因此，装入背包，因此， 背包的重量和获得的价值与结点背包的重量和获得的价值与结点5相同，目标函数值为相同，目标函数值为40 + (10-4)464，将结点，将结点6加入表加入表PT中；中； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行优先进行 搜索；搜索； （8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，

12、背包的重量为 12，不满足约束条件，将结点，不满足约束条件，将结点8丢弃；在结点丢弃；在结点9，没有将物，没有将物 品品4装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点6相相 同，同，目标函数值为目标函数值为65； （9）由于结点）由于结点9是叶子结点，同时结点是叶子结点，同时结点9的目标函数值是表的目标函数值是表 PT中的极大值，所以，结点中的极大值，所以，结点9对应的解即是问题的最优解，对应的解即是问题的最优解， 搜索结束。搜索结束。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 9.1.2 分支限界法的设计思想分支限

13、界法的设计思想 假设求解最大化问题，解向量为假设求解最大化问题，解向量为X=(x1, x2, , xn)，其，其 中，中，xi的取值范围为某个有穷集合的取值范围为某个有穷集合Si，|Si|=ri（1in）。在）。在 使用分支限界法搜索问题的解空间树时，首先根据限界函使用分支限界法搜索问题的解空间树时，首先根据限界函 数估算目标函数的界数估算目标函数的界down, up，然后从根结点出发，扩展，然后从根结点出发，扩展 根结点的根结点的r1个孩子结点，从而构成分量个孩子结点，从而构成分量x1的的r1种可能的取值种可能的取值 方式。对这方式。对这r1个孩子结点分别估算可能取得的目标函数值个孩子结点分

14、别估算可能取得的目标函数值 bound(x1)，其含义是以该孩子结点为根的子树所可能取得，其含义是以该孩子结点为根的子树所可能取得 的目标函数值不大于的目标函数值不大于bound(x1)，也就是部分解应满足：，也就是部分解应满足： bound(x1)bound(x1, x2) bound(x1, x2, , xk) bound(x1, x2, , xn) 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 若某孩子结点的目标函数值超出目标函数的界，则将该孩若某孩子结点的目标函数值超出目标函数的界，则将该孩 子结点丢弃；否则，将该孩子结点保存在待处理结点表子结点丢弃；否则

15、，将该孩子结点保存在待处理结点表PT 中。从表中。从表PT中选取使目标函数取得极大值的结点作为下一中选取使目标函数取得极大值的结点作为下一 次扩展的根结点，重复上述过程，当到达一个叶子结点时，次扩展的根结点，重复上述过程，当到达一个叶子结点时， 就得到了一个可行解就得到了一个可行解X=(x 1, x2, , xn)及其目标函数值 及其目标函数值 bound(x1, x2, , xn)。 如果如果bound(x1, x2, , xn)是表是表PT中目标函数值最大的结点，中目标函数值最大的结点， 则则bound(x1, x2, , xn)就是所求问题的最大值，就是所求问题的最大值，(x1, x2,

16、 , xn) 就是问题的最优解；就是问题的最优解； 如果如果bound(x1, x2, , xn)不是表不是表PT中目标函数值最大的结中目标函数值最大的结 点，说明还存在某个部分解对应的结点，其上界大于点，说明还存在某个部分解对应的结点，其上界大于 bound(x1, x2, , xn)。于是，用。于是，用bound(x1, x2, , xn)调整目标调整目标 函数的下界，即令函数的下界，即令down=bound(x1, x2, , xn)，并将表，并将表PT中中 超出目标函数下界超出目标函数下界down的结点删除，然后选取目标函数值的结点删除，然后选取目标函数值 取得极大值的结点作为下一次扩

17、展的根结点，继续搜索，直取得极大值的结点作为下一次扩展的根结点，继续搜索，直 到某个叶子结点的目标函数值在表到某个叶子结点的目标函数值在表PT中最大。中最大。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 分支限界法求解最大化问题的一般过程分支限界法求解最大化问题的一般过程 分支限界法的一般过程分支限界法的一般过程 1根据限界函数确定目标函数的界根据限界函数确定目标函数的界down, up； 2将待处理结点表将待处理结点表PT初始化为空；初始化为空； 3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的

18、目标函数值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中最大中最大)， 则

19、将结点则将结点x对应的解输出，算法结束；对应的解输出，算法结束； 4.2.4 若若(结点结点x是叶子结点但结点是叶子结点但结点x的的value值在表值在表PT中不是最大中不是最大)， 则令则令down=value，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 应用分支限界法的关键问题应用分支限界法的关键问题 （1）如何确定合适的限界函数）如何确定合适的限界函数 （2）如何组织待处理结点表）如何组织待处理结点表 （3）如何确定最优解中的各个分量）如何确定最优解中的各个分量 算法设计与分析算

20、法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 分支限界法对问题的解空间树中结点的处理是跳跃式的，回分支限界法对问题的解空间树中结点的处理是跳跃式的，回 溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当 搜索到某个叶子结点且该叶子结点的目标函数值在表搜索到某个叶子结点且该叶子结点的目标函数值在表PT中中 最大时（假设求解最大化问题），求得了问题的最优值，但最大时（假设求解最大化问题），求得了问题的最优值，但 是，却无法求得该叶子结点对应的最优解中的各个分量。这是，却无法求得该叶子结点对应的最优解中的各个分量。这 个问题可以用如

21、下方法解决：个问题可以用如下方法解决： 对每个扩展结点保存该结点到根结点的路径；对每个扩展结点保存该结点到根结点的路径； 在搜索过程中构建搜索经过的树结构，在求得最优解时，在搜索过程中构建搜索经过的树结构，在求得最优解时， 从叶子结点不断回溯到根结点，以确定最优解中的各个分量。从叶子结点不断回溯到根结点，以确定最优解中的各个分量。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 (0)60 (1,0,0)64 (1,0,1,0)65 (a) 扩展根结点后表扩展根结点后表PT状态状态 (b) 扩展结点扩展结点2后表后表PT状态状态 (c) 扩展结点扩展结点5后表后表P

22、T状态状态 (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的的 状

23、态如图状态如图9.2所示。所示。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 (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,7

24、6) (1,70) (0,69) 图图9.1所示所示0/1背包问题，为了在搜索过程中构建搜索经过的树背包问题，为了在搜索过程中构建搜索经过的树 结构，设一个表结构，设一个表ST，在表，在表PT中取出最小值结点进行扩充时，中取出最小值结点进行扩充时， 将最小值结点存储到表将最小值结点存储到表ST中，表中，表PT和表和表ST的数据结构为的数据结构为(物物 品品i-1的选择结果，的选择结果，ub)，在搜索过，在搜索过 程中表程中表PT和表和表ST的状态如图的状态如图9.3所示。所示。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 9.1.3 分支限界法的时间性能分支限界

25、法的时间性能 分支限界法和回溯法实际上都属于蛮力穷举法，当分支限界法和回溯法实际上都属于蛮力穷举法，当 然不能指望它有很好的最坏时间复杂性，遍历具有指数然不能指望它有很好的最坏时间复杂性，遍历具有指数 阶个结点的解空间树，在最坏情况下，时间复杂性肯定阶个结点的解空间树，在最坏情况下，时间复杂性肯定 为指数阶。为指数阶。 与回溯法不同的是，分支限界法首先扩展解空间树与回溯法不同的是，分支限界法首先扩展解空间树 中的上层结点，并采用限界函数，有利于实行大范围剪中的上层结点，并采用限界函数，有利于实行大范围剪 枝，同时，根据限界函数不断调整搜索方向，选择最有枝，同时，根据限界函数不断调整搜索方向，选

26、择最有 可能取得最优解的子树优先进行搜索。所以，如果选择可能取得最优解的子树优先进行搜索。所以，如果选择 了结点的合理扩展顺序以及设计了一个好的限界函数，了结点的合理扩展顺序以及设计了一个好的限界函数， 分支界限法可以快速得到问题的解。分支界限法可以快速得到问题的解。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 分支限界法的较高效率是以付出一定代价为基础的，其分支限界法的较高效率是以付出一定代价为基础的，其 工作方式也造成了算法设计的复杂性。首先，一个更好的限工作方式也造成了算法设计的复杂性。首先，一个更好的限 界函数通常需要花费更多的时间计算相应的目标函数值，

27、而界函数通常需要花费更多的时间计算相应的目标函数值，而 且对于具体的问题实例，通常需要进行大量实验，才能确定且对于具体的问题实例，通常需要进行大量实验，才能确定 一个好的限界函数；其次，由于分支限界法对解空间树中结一个好的限界函数；其次，由于分支限界法对解空间树中结 点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最 优值时，为了从该叶子结点求出对应的最优解中的各个分量，优值时，为了从该叶子结点求出对应的最优解中的各个分量， 需要对每个扩展结点保存该结点到根结点的路径，或者在搜需要对每个扩展结点保存该结点到根结点的路径，或者在搜 索过程中构

28、建搜索经过的树结构，这使得算法的设计较为复索过程中构建搜索经过的树结构，这使得算法的设计较为复 杂；再次，算法要维护一个待处理结点表杂；再次，算法要维护一个待处理结点表PTPT，并且需要在表，并且需要在表 PTPT中快速查找取得极值的结点，等等。这都需要较大的存储中快速查找取得极值的结点，等等。这都需要较大的存储 空间，在最坏情况下，分支限界法需要的空间复杂性是指数空间，在最坏情况下，分支限界法需要的空间复杂性是指数 阶。阶。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP问题问题 9.2.2 多

29、段图的最短路径问题多段图的最短路径问题 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 9.2.1 TSP问题问题 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城个城市，要求各个城 市经历且仅经历一次然后回到出发城市，并要求所走市经历且仅经历一次然后回到出发城市，并要求所走 的路程最短。的路程最短。 2 71 56 3 1 34 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 无向图及其代价

30、矩阵无向图及其代价矩阵 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 采用贪心法求得近似解为采用贪心法求得近似解为135421，其路径，其路径 长度为长度为1+2+3+7+3=16，这可以作为，这可以作为TSP问题的上界。问题的上界。 把矩阵中每一行最小的元素相加，可以得到一个简单的把矩阵中每一行最小的元素相加，可以得到一个简单的 下界，其路径长度为下界，其路径长度为1+3+1+3+2=10，但是还有一个信息量，但是还有一个信息量 更大的下界：考虑一个更大的下界：考虑一个TSP问题的完整解，在每条路径上，问题的完整解，在每条路径上， 每个城市都有两条邻接边，一条是

31、进入这个城市的，另一每个城市都有两条邻接边，一条是进入这个城市的，另一 条是离开这个城市的，那么，如果把矩阵中每一行最小的条是离开这个城市的，那么，如果把矩阵中每一行最小的 两个元素相加再除以两个元素相加再除以2，如果图中所有的代价都是整数，再，如果图中所有的代价都是整数，再 对这个结果向上取整，就得到了一个合理的下界。对这个结果向上取整，就得到了一个合理的下界。 lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目标函数的界于是，得到了目标函数的界14, 16。 需要强调的是，这个解并不是一个合法的选择（可能没有需要强调的是，这个解并不是一个合法的选择（

32、可能没有 构成哈密顿回路），它仅仅给出了一个参考下界。构成哈密顿回路），它仅仅给出了一个参考下界。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 部分解的目标函数值的计算方法部分解的目标函数值的计算方法 例如图例如图9.4所示无向图，如果部分解包含边所示无向图，如果部分解包含边(1, 4)，则该部分，则该部分 解的下界是解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。 UrUr ji k i ii ij rrrrclb2/ )2( 1 1 1 行最小的两个元素素行不在路径上的最小元 算法设计与分析算法设计与分析清华大学出版社清

33、华大学出版社 第9章分支限界法 4 12 lb=14 235 678 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 911 52 lb=19 54 lb=14 11 42 lb=16 1 42 lb=18 45 lb=15 11 52 lb=20 1 分支限界法求解分支限界法求解TSP问题示例问题示例 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 应用分支限界法求解图9.4所示无向图的TSP问题，其搜索空间 如图9.5所示

34、，具体的搜索过程如下（加黑表示该路径上已经确 定的边）： （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)+

35、(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丢弃； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （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)/

36、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)

37、+(3+4)+(2+3)/2=14，将结点11加入表PT中； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （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，目标函

38、数值为 (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； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （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)

39、+(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问题的最优解， 搜索过程结束。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 (g) 扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421

40、 图图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 (

41、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后的状态后

42、的状态 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 算法算法9.1TSP问题问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up； 2将待处理结点表将待处理结点表PT初始化为空；初始化为空； 3for (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 ij pi Evr i j jj

43、jvrcrrclb pi 2 1 , 1 1 min 1 段的最短边段的最短边第第 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 应用分支限界法求解图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=

44、3+4+5+3=15，将结点4加入表PT中； （3）在表PT中选取目标函数值极小的结点4优先进行搜索； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （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

45、中； 在结点9，第2段选择边，目标函数值为lb=2+8+5+3=18， 将结点9加入表PT中； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （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代表 的解即是问题的最优解，搜索过程结束。 算

46、法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 6 4 01 lb=20 23 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 1 1 1 0 57 lb=22 58 lb=16 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 为了在搜索过

47、程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表ST， 在表在表PT中取出最小值结点进行扩充时，将最小值结点存储到表中取出最小值结点进行扩充时，将最小值结点存储到表 ST中，表中，表PT和表和表ST的数据结构为的数据结构为(第第i段，段，lb)，在搜索过程中表，在搜索过程中表PT和表和表ST的状态如下：的状态如下： (b) 扩展结点扩展结点3后的状态后的状态 (d) 扩展结点扩展结点5后的状态，最优解为后的状态，最优解为03589 图图9.9 多段图的最短路径问题最优解的确定多段图的最短路径问题最优解的确定 (1,16) (1,15) (1,16) (2,16)

48、 (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)。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 算法算法9.2多段图的最短路径问题多段图的最短路径问题 1根据限界函数计算目标函数的下界根据限界函

49、数计算目标函数的下界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

50、值不是最小，则值不是最小，则 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章分支限界法 9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.1 9.3.1 任务分配问题任务分配问题 9.3.2 9.3.2 批处理作业调度问题批处理作业调度问题 算法设计与分析算法设计与分

51、析清华大学出版社清华大学出版社 第9章分支限界法 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 任务分配问题的成本矩阵任务分配问题的成本矩阵

52、算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 求最优分配成本的上界和下界求最优分配成本的上界和下界 考虑任意一个可行解，例如矩阵中的对角线是一个合法的选考虑任意一个可行解，例如矩阵中的对角线是一个合法的选 择，表示将任务择，表示将任务1分配给人员分配给人员a、任务、任务2分配给人员分配给人员b、任务、任务3 分配给人员分配给人员c、任务、任务4分配给人员分配给人员d，其成本是，其成本是9+4+1+4=18； 或者应用贪心法求得一个近似解：将任务或者应用贪心法求得一个近似解：将任务2分配给人员分配给人员a、任、任 务务3分配给人员分配给人员b、任务、任务1分配给人员

53、分配给人员c、任务、任务4分配给人员分配给人员d， 其成本是其成本是2+3+5+4=14。显然，。显然，14是一个更好的上界。为了获是一个更好的上界。为了获 得下界，考虑人员得下界，考虑人员a执行所有任务的最小代价是执行所有任务的最小代价是2，人员，人员b执执 行所有任务的最小代价是行所有任务的最小代价是3，人员，人员c执行所有任务的最小代价执行所有任务的最小代价 是是1，人员，人员d执行所有任务的最小代价是执行所有任务的最小代价是4。因此，将每一行。因此，将每一行 的最小元素加起来就得到解的下界，其成本是的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。 需要强调的是，这个解并不

54、是一个合法的选择（需要强调的是，这个解并不是一个合法的选择（3和和1来自于来自于 矩阵的同一列），它仅仅给出了一个参考下界，这样，最优矩阵的同一列），它仅仅给出了一个参考下界，这样，最优 值一定是值一定是10, 14之间的某个值。之间的某个值。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 设当前已对人员设当前已对人员1i分配了任务，并且获得了成本分配了任务，并且获得了成本v， 则限界函数可以定义为：则限界函数可以定义为： （式（式9.4） n ik kvlb 1 行的最小值第 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （2）在结

55、点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所示任务分配问题，对解空 间树的搜索

56、如图9.11所示，具体的搜索过程如下： （1）在根结点1，没有分配任务，根据限界函数估算目标函 数值为2+3+1+4=10； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （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加入表P

57、T中； （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丢弃； 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 （7）在表PT中选取目标函数值极小的结点6优先进行搜索； （8）在结点11，将任务3分配给人员c，获得的成本为8+1=9， 目标函数值为9+4=13，将结点11加入表PT中；在结点12，将 任务4分配给

58、人员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对应的 解即是问题的最优解，搜索结束。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 4a lb=16 1 0 4 start lb=10 1a lb=17 2a lb=10 3a lb=15 1b lb=13 3b lb=1

59、0 4b lb=14 1c lb=14 4c lb=17 4c lb=17 3c lb=13 4d lb=13 图图9.11 分支限界法求解任务分配问题示例分支限界法求解任务分配问题示例 (表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序) 235 6 78 91 2 1 3 1 1 1 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 第9章分支限界法 为了在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表 ST，在表，在表PT中取出最小值结点进行扩充时，将最小值结点中取出最小值结点进行扩充时，将最小值结点

60、 存储到表存储到表ST中，表中，表PT和表和表ST的数据结构为的数据结构为(人员人员i- -1分配的分配的 任务任务,lb) (e) 扩展结点扩展结点11后的状态，最优解为后的状态，最优解为2a 1b 3c 4d 图图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) 扩展根结点后的状态扩展根结点后的状态