1、2022-12-16第9章 分支限界法 Page 19.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法9.4 实验项目实验项目电路布线问题电路布线问题第第9 9章章 分支限界法分支限界法 2022-12-16第9章 分支限界法 Page 29.1.1 解空间树的动态搜索（解空间树的动态搜索（2）9.1.2 分支限界法的设计思想分支限界法的设计思想9.1.3 分支限界法的时间性能分支限界法的时间性能9.1 9.1 概概 述述 2022-12-16第9章 分支限界法 Page 3 分支限界法首先确定一个合理的限界函数，并根据限界
2、分支限界法首先确定一个合理的限界函数，并根据限界函数函数确定目标函数的界确定目标函数的界down,up。然后，按照。然后，按照广度优先策广度优先策略略遍历问题的解空间树，在分支结点上，依次搜索该结点的遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结
3、点表（以下简称经得到的解更好；否则，将其加入待处理结点表（以下简称表表PT）中。依次从表）中。依次从表PT中选取使目标函数的值取得极值的中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。结点成为当前扩展结点，重复上述过程，直到找到最优解。9.1.1 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2 2）2022-12-16第9章 分支限界法 Page 4 随着这个遍历过程的不断深入，随着这个遍历过程的不断深入，表表PT中所估算的目标函中所估算的目标函数的界越来越接近问题的最优解。数的界越来越接近问题的最优解。当搜索到一个叶子结点时当搜索到一个叶子结点时，如
4、果该结点的目标函数值是表，如果该结点的目标函数值是表PT中的极值（对于最小化问中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表问题，调整下界），依次考察表PT中的结点，将超出目标函中的结点，将超出目标函数界的结点丢弃，然后从表数界的结点丢弃，然后从表PT中选取使目标函数取得极值的中选取
5、使目标函数取得极值的结点继续进行扩展。结点继续进行扩展。2022-12-16第9章 分支限界法 Page 5 例：例：0/1背包问题。假设有背包问题。假设有4个物品，其重量分别为个物品，其重量分别为(4,7,5,3)，价值分别为，价值分别为(40,42,25,12)，背包容量，背包容量W=10。首先，将给。首先，将给定物品按单位重量价值从大到小排序，结果如下：定物品按单位重量价值从大到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)1440102742635255431242022-12-16第9章 分支限界法 Page 6 应用贪心法求得近似解为应用贪心法求
6、得近似解为(1,0,0,0)，获得的价，获得的价值为值为40，这可以作为，这可以作为0/1背包问题的下界。背包问题的下界。如何求得如何求得0/1背包问题的一个合理的上界呢？考背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第虑最好情况，背包中装入的全部是第1个物品且可以个物品且可以将背包装满，则可以得到一个非常简单的上界的计将背包装满，则可以得到一个非常简单的上界的计算方法：算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界于是，得到了目标函数的界40,100。2022-12-16第9章 分支限界法 Page 7假设背包中已装入物品的重量是假设背包中已装入物
7、品的重量是w，获得的价值是，获得的价值是v，计算该结点的目标函数上界的一个简单方法是把，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值已经装入背包中的物品取得的价值v，加上背包剩余，加上背包剩余容量容量W-w与剩下物品的最大单位重量价值与剩下物品的最大单位重量价值的积，于是，得到限界函数为：的积，于是，得到限界函数为：)()(11 iiwvwWvub11 iiwv2022-12-16第9章 分支限界法 Page 8w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解无效解w=4,v=40ub=70w=9,v=65ub=69w=4,
8、v=40ub=64w=12无效解无效解w=9,v=65ub=65234567891分支限界法求解分支限界法求解0/1背包问题背包问题2022-12-16第9章 分支限界法 Page 9 分支限界法求解分支限界法求解0/1背包问题，其搜索空间如图背包问题，其搜索空间如图9.1所所示，具体的搜索过程如下：示，具体的搜索过程如下：（1）在根结点）在根结点1，没有将任何物品装入背包，因此，背包，没有将任何物品装入背包，因此，背包的重量和获得的价值均为的重量和获得的价值均为0，根据限界函数计算结点，根据限界函数计算结点1的目的目标函数值为标函数值为1010=100；（2）在结点）在结点2，将物品，将物品
9、1装入背包，因此，背包的重量为装入背包，因此，背包的重量为4，获得的价值为获得的价值为40，目标函数值为，目标函数值为40+(10-4)6=76，将结，将结点点2加入待处理结点表加入待处理结点表PT中；在结点中；在结点3，没有将物品，没有将物品1装入装入背包，因此，背包的重量和获得的价值仍为背包，因此，背包的重量和获得的价值仍为0，目标函数，目标函数值为值为10660，将结点，将结点3加入表加入表PT中；中；（3）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进优先进行搜索；行搜索；2022-12-16第9章 分支限界法 Page 10（4）在结点）在结点4，
10、将物品，将物品2装入背包，因此，背包的重量为装入背包，因此，背包的重量为11，不满足约束条件，将结点，不满足约束条件，将结点4丢弃；在结点丢弃；在结点5，没有将，没有将物物品品2装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点2相相同，目标函数值为同，目标函数值为40+(10-4)5=70，将结点，将结点5加入表加入表PT中；中；（5）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5优先进行优先进行搜索；搜索；（6）在结点）在结点6，将物品，将物品3装入背包，因此，背包的重量为装入背包，因此，背包的重量为9，获得的价值为获得的
11、价值为65，目标函数值为，目标函数值为65+(10-9)4=69，将结，将结点点6加入表加入表PT中；在结点中；在结点7，没有将物品，没有将物品3装入背包，因此，装入背包，因此，背包的重量和获得的价值与结点背包的重量和获得的价值与结点5相同，目标函数值为相同，目标函数值为40+(10-4)464，将结点，将结点6加入表加入表PT中；中；2022-12-16第9章 分支限界法 Page 11（7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行优先进行搜索；搜索；（8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，背包的重量为1
12、2，不满足约束条件，将结点，不满足约束条件，将结点8丢弃；在结点丢弃；在结点9，没有将物，没有将物品品4装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点6相相同，同，目标函数值为目标函数值为65；（9）由于结点）由于结点9是叶子结点，同时结点是叶子结点，同时结点9的目标函数值是表的目标函数值是表PT中的极大值，所以，结点中的极大值，所以，结点9对应的解即是问题的最优解，对应的解即是问题的最优解，搜索结束。搜索结束。2022-12-16第9章 分支限界法 Page 12 假设求解最大化问题，解向量为假设求解最大化问题，解向量为X=(x1,x2,xn)，其，
13、其中，中，xi的取值范围为某个有穷集合的取值范围为某个有穷集合Si，|Si|=ri（1in）。在）。在使用分支限界法搜索问题的解空间树时，首先根据限界函使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界数估算目标函数的界down,up，然后从根结点出发，扩展，然后从根结点出发，扩展根结点的根结点的r1个孩子结点，从而构成分量个孩子结点，从而构成分量x1的的r1种可能的取值种可能的取值方式。对这方式。对这r1个孩子结点分别估算可能取得的个孩子结点分别估算可能取得的目标函数值目标函数值bound(x1)，其含义是以该孩子结点为根的子树所可能取得，其含义是以该孩子结点为根的子树所可
14、能取得的目标函数值不大于的目标函数值不大于bound(x1)，也就是部分解应满足：也就是部分解应满足：bound(x1)bound(x1,x2)bound(x1,x2,xk)bound(x1,x2,xn)9.1.2 9.1.2 分支限界法的设计思想分支限界法的设计思想 2022-12-16第9章 分支限界法 Page 13 若某孩子结点的目标函数值超出目标函数的界，若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表待处理结点表PT中。从表中。从表PT中选取使目标函数取得中选取使目标函数取得极大值的结点作
15、为下一次扩展的根结点，重复上述极大值的结点作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行过程，当到达一个叶子结点时，就得到了一个可行解解X=(x1,x2,xn)及其目标函数值及其目标函数值bound(x1,x2,xn)。2022-12-16第9章 分支限界法 Page 14q 如果如果bound(x1,x2,xn)是表是表PT中目标函数值最大中目标函数值最大的结点，则的结点，则bound(x1,x2,xn)就是所求问题的最就是所求问题的最大值，大值，(x1,x2,xn)就是问题的最优解；就是问题的最优解；q 如果如果bound(x1,x2,xn)不是表不是表PT中
16、目标函数值最中目标函数值最大的结点，说明还存在某个部分解对应的结点，大的结点，说明还存在某个部分解对应的结点，其上界大于其上界大于bound(x1,x2,xn)。于是，。于是，用用bound(x1,x2,xn)调整目标函数的下界，即令调整目标函数的下界，即令down=bound(x1,x2,xn)，并将表，并将表PT中超出目标中超出目标函数下界函数下界down的结点删除，的结点删除，然后选取目标函数值然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表续搜索，直到某个叶子结点的目标函数值在表PT中最大。中
17、最大。2022-12-16第9章 分支限界法 Page 15分支限界法求解最大化问题的一般过程分支限界法求解最大化问题的一般过程分支限界法的一般过程分支限界法的一般过程1根据限界函数确定目标函数的界根据限界函数确定目标函数的界down,up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的目标函数值value;3.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最
18、大中最大 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=
19、value，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除；2022-12-16第9章 分支限界法 Page 16应用分支限界法的关键问题应用分支限界法的关键问题（1）如何确定合适的）如何确定合适的限界函数限界函数（2）如何组织）如何组织待处理结点表待处理结点表（3）如何确定最优解中的）如何确定最优解中的各个分量各个分量 2022-12-16第9章 分支限界法 Page 17分支限界法对问题的解空间树中结点的处理是跳跃式的，回分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当溯也不是单纯地沿着双亲结点一层一层向上
20、回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表搜索到某个叶子结点且该叶子结点的目标函数值在表PT中中最大时（假设求解最大化问题），求得了问题的最优值，但最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。这是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方法解决：个问题可以用如下方法解决：对每个扩展结点保存该结点到根结点的路径；对每个扩展结点保存该结点到根结点的路径；在搜索过程中构建搜索经过的树结构，在求得最优解时，在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各
21、个分量。从叶子结点不断回溯到根结点，以确定最优解中的各个分量。对于（对于（3）：如何确定最优解中的各个分量：）：如何确定最优解中的各个分量：2022-12-16第9章 分支限界法 Page 18(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
22、(1)76 (0)60(0)60 (1,0)70 方法一：方法一：例如图例如图9.1所示所示0/1背包问题，为了对每个扩展结点保存该结背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解点到根结点的路径，将部分解(x1,xi)和该部分解的目标和该部分解的目标函数值都存储在待处理结点表函数值都存储在待处理结点表PT中，在搜索过程中表中，在搜索过程中表PT的状态如图的状态如图9.2所示。所示。2022-12-16第9章 分支限界法 Page 19(a)扩展根结点后扩展根结点后 (b)扩展结点扩展结点2后后(c)扩展结点扩展结点5后后 (d)扩展结点扩展结点6后，最优解为后，最优解为(1,
23、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中，表中
24、，表PT和表和表ST的数据结构的数据结构为为(物品物品i-1的选择结果，的选择结果，ub)，在搜，在搜索过程中表索过程中表PT和表和表ST的状态如图的状态如图9.3所示。所示。2022-12-16第9章 分支限界法 Page 20 分支限界法和回溯法实际上都属于蛮力穷举法，当然不分支限界法和回溯法实际上都属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。的解空间树，在最坏情况下，时间复杂性肯定为指数阶。与回溯法不同的是，分支限界法首先扩展解空间树中的与回溯法不同的是，分
25、支限界法首先扩展解空间树中的上层结点，并上层结点，并采用限界函数，有利于实行大范围剪枝采用限界函数，有利于实行大范围剪枝，同时，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索的子树优先进行搜索。所以，如果选择了结点的合理扩展顺。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。问题的解。9.1.3 9.1.3 分支限界法的时间性能分支限界法的时间性能 2022-12-16第9章 分支限界法 Page 21 分支限界法的
26、较高效率是以付出一定代价为基础的，其分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，一个更好的限工作方式也造成了算法设计的复杂性。首先，一个更好的限界函数通常需要花费更多的时间界函数通常需要花费更多的时间计算相应的目标函数值计算相应的目标函数值，而，而且对于具体的问题实例，通常需要进行大量实验，才能确定且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，由于分支限界法对解空间树中结一个好的限界函数；其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最点的处理是跳跃式的，因此，在搜索到某个叶子结点得
27、到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点需要对每个扩展结点保存该结点到根结点的路径保存该结点到根结点的路径，或者在搜，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表杂；再次，算法要维护一个待处理结点表PTPT，并且需要在表，并且需要在表PTPT中中快速查找取得极值的结点快速查找取得极值的结点，等等。这都需要较大的存储，等等。这都需要较大的存储空间，空间，在最坏情况下，分支限界法需要的空间复杂性是指数在最坏
28、情况下，分支限界法需要的空间复杂性是指数阶。阶。2022-12-16第9章 分支限界法 Page 229.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题9.2 9.2 图问题中的分支限界法图问题中的分支限界法 2022-12-16第9章 分支限界法 Page 23 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。的路程最短。271563134253984C=3 1 5 8 3 6 7 9 1 6 4 2 5 7 4
29、 3 8 9 2 3 (a)一个无向图一个无向图 (b)无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵9.2.1 TSP9.2.1 TSP问题问题2022-12-16第9章 分支限界法 Page 24 采用贪心法求得近似解为采用贪心法求得近似解为135421，其路径，其路径长度为长度为1+2+3+7+3=16，这可以作为，这可以作为TSP问题的上界。问题的上界。把矩阵中每一行最小的元素相加，可以得到一个简单把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为的下界，其路径长度为1+3+1+3+2=10，但是还有一个信息，但是还有一个信息量更大的下
30、界：考虑一个量更大的下界：考虑一个TSP问题的完整解，在每条路径问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以小的两个元素相加再除以2，如果图中所有的代价都是整数，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。再对这个结果向上取整，就得到了一个合理的下界。lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目标函数的界于是，得到了目标
31、函数的界14,16。需要强调的是，这个解并不是一个合法的选择（可能没有需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。构成哈密顿回路），它仅仅给出了一个参考下界。2022-12-16第9章 分支限界法 Page 25部分解的目标函数值的计算方法部分解的目标函数值的计算方法 例如图例如图9.4所示无向图，如果部分解包含边所示无向图，如果部分解包含边(1,4)，则该部分，则该部分解的下界是解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。UrUrjikiiiijrrrrclb2/)2(111行最小的两个元素素行不在路
32、径上的最小元2022-12-16第9章 分支限界法 Page 26412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=149101152lb=1954lb=14121342lb=161442lb=1845lb=15151652lb=2017分支限界法求解分支限界法求解TSP问题示例问题示例2022-12-16第9章 分支限界法 Page 27应用分支限界法求解图应用分支限界法求解图9.4所示无向图的所示无向图的TSP问题，其搜索空间问题，其搜索空间如图如图9.5所示，具体的搜
33、索过程如下（加黑表示该路径上已经确所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：定的边）：（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，目，目标函数的值
34、为标函数的值为(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丢弃；丢弃；2022-12-16第9
35、章 分支限界法 Page 28（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+
36、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中中；在
37、结点；在结点11，从城市，从城市3到城市到城市5，目标函数值为，目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点，将结点11加入表加入表PT中中；2022-12-16第9章 分支限界法 Page 29（7）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点11优先进行搜索；优先进行搜索；（8）在结点）在结点12，从城市，从城市5到城市到城市2，目标函数值为，目标函数值为(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19，超出目标函数的界，超出目标函数的界，将结点将结点12丢弃；在结点丢弃；在结点13，从城市，从城市5到城
38、市到城市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为叶子结点，得到一个可行解，
39、其路径长度为为叶子结点，得到一个可行解，其路径长度为16；2022-12-16第9章 分支限界法 Page 30（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，将结点，将
40、结点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问题的最优解，问题的最优解，搜索过程结束。搜索过程结束。2022-1
41、2-16第9章 分支限界法 Page 31(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)
42、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后的状态后的状态2022-12-16第9章 分支限界法 Page 32算法算法
43、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 kijpiEvrijjjjvrcrrclbpi21,11min1段的最短边段的最短边第第2022-12-16第9章 分支限界法 Page 35 应用分支
44、限界法求解图应用分支限界法求解图9.7所示多段图的最短路径问题，所示多段图的最短路径问题，其搜索空间如图其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：路径上已经确定的边）：（1）在根结点）在根结点1，根据限界函数计算目标函数的值为，根据限界函数计算目标函数的值为14；（2）在结点）在结点2，第，第1段选择边段选择边，目标函数值为，目标函数值为lb=4+8+5+3=20，超出目标函数的界，将结点，超出目标函数的界，将结点2丢弃；在结点丢弃；在结点3，第，第1段选择边段选择边，目标函数值为，目标函数值为lb=2+7+5+3=17，
45、将结，将结点点3加入待处理结点表加入待处理结点表PT中；在结点中；在结点4，第，第1段选择边段选择边，目标函数值为目标函数值为lb=3+4+5+3=15，将结点，将结点4加入表加入表PT中；中；（3）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点4优先进行搜索；优先进行搜索；2022-12-16第9章 分支限界法 Page 36（4）在结点）在结点5，第，第2段选择边段选择边，目标函数值为，目标函数值为lb=3+4+6+3=16，将结点，将结点5加入表加入表PT中；在结点中；在结点6，第，第2段选择段选择边边，目标函数值为，目标函数值为lb=3+7+5+3=18，将结点，将
46、结点6加入表加入表PT中；中；（5）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点5优先进行搜索；优先进行搜索；（6）在结点）在结点7，第，第3段选择边段选择边，可直接确定第，可直接确定第4段的边段的边，目标函数值为，目标函数值为lb=3+4+8+7=22，为一个可行解但超出目标，为一个可行解但超出目标函数的界，将其丢弃；在结点函数的界，将其丢弃；在结点8，第，第3段选择边段选择边，可直接确定第，可直接确定第4段的边段的边，目标函数值为，目标函数值为lb=3+4+6+3=16，为一个较好的可行解。由于结点，为一个较好的可行解。由于结点8是叶子结是叶子结点，并且其目标函数值是
47、表点，并且其目标函数值是表PT中最小的，所以，结点中最小的，所以，结点8代表的代表的解即是问题的最优解，搜索过程结束。解即是问题的最优解，搜索过程结束。2022-12-16第9章 分支限界法 Page 376401lb=20231startlb=1402lb=1703lb=15图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)535lb=1636lb=188757lb=2258lb=162022-12-16第9章 分支限界法 Page 38 为了在搜索过程中构建搜索
48、经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表在表PT中取出最小值结点进行扩充时，将最小值结点存储到表中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表中，表PT和表和表ST的数据结构为的数据结构为(第第i段，段，lb)，在搜索过程中表，在搜索过程中表PT和表和表ST的状态如下：的状态如下：(b)扩展结点扩展结点4后的状态后的状态(c)扩展结点扩展结点5后的状态，最优解为后的状态，最优解为0358图图9.9 多段图的最短路径问题最优解的确定多段图的最短路径问题最优解的确定(1,17)(1,15)(1,17)(2,16)(2,18)(1,15)(1,17)
49、(2,18)(3,16)(1,15)(2,16)(a)扩展根结点后的状态扩展根结点后的状态 PT ST ST PT ST 回溯过程是：(3,16)(2,16)(1,15)。PT 2022-12-16第9章 分支限界法 Page 39算法算法9.2多段图的最短路径问题多段图的最短路径问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3for(i=1;i=1)5.1 对顶点对顶点u的所有邻接点的所有邻接点v 5.1.1 根据式根据式9.3计算目标函数值计算目标函数值lb
50、;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最小的结点的最小的结
