第9章 分支限界法完PPT讲稿.ppt

《第9章 分支限界法完PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第9章 分支限界法完PPT讲稿.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9章章 分支限界法完分支限界法完第1页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 29.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法9.4 实验项目实验项目电路布线问题电路布线问题第第9 9章章 分支限界法分支限界法 第2页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 39.1.1 解空间树的动态搜索（解空间树的动态搜索（2）9.1.2 分支限界法的设计思想分支限界法的设计思想9.1.3 分支限界法的时间性能分支限界法的时间性能9.1 9

2、.1 概概 述述 第3页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 4 分分支支限限界界法法首首先先确确定定一一个个合合理理的的限限界界函函数数，并并根根据据限限界界函函数数确确定定目目标标函函数数的的界界down,up。然然后后，按按照照广广度度优优先先策策略略遍遍历历问问题题的的解解空空间间树树，在在分分支支结结点点上上，依依次次搜搜索索该该结结点点的的所所有有孩孩子子结结点点，分分别别估估算算这这些些孩孩子子结结点点的的目目标标函函数数的的可可能能取取值值，如如果果某某孩孩子子结结点点的的目目标标函函数数可可能能取取得得的的值值超超出出目目标标函

3、函数数的的界界，则则将将其其丢丢弃弃，因因为为从从这这个个结结点点生生成成的的解解不不会会比比目目前前已已经经得得到到的的解解更更好好；否否则则，将将其其加加入入待待处处理理结结点点表表（以以下下简简称称表表PT）中中。依依次次从从表表PT中中选选取取使使目目标标函函数数的的值值取取得得极极值值的的结结点点成为当前扩展结点，重复上述过程，直到找到最优解。成为当前扩展结点，重复上述过程，直到找到最优解。9.1.1 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2 2）第4页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 5 随着这个遍历过程的不断深入，

4、随着这个遍历过程的不断深入，表表PT中所估算的目标函数的界中所估算的目标函数的界越来越接近问题的最优解。越来越接近问题的最优解。当搜索到一个叶子结点时当搜索到一个叶子结点时，如果该结点，如果该结点的目标函数值是表的目标函数值是表PT中的极值（对于最小化问题，是极小值；中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依于最小化问题，调整上界；对

5、于最大化问题，调整下界），依次考察表次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。中选取使目标函数取得极值的结点继续进行扩展。第5页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 6 例例：0/1背背包包问问题题。假假设设有有4个个物物品品，其其重重量量分分别别为为(4,7,5,3)，价价值值分分别别为为(40,42,25,12)，背背包包容容量量W=10。首首先先，将将给给定定物物品品按按单单位位重重量价值从大到小排序，结果如下：量价值从大到小排序，

6、结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124第6页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 7 应用贪心法求得近似解为应用贪心法求得近似解为(1,0,0,0)，获得的价值为，获得的价值为40，这可以作为，这可以作为0/1背包问题的下界。背包问题的下界。如何求得如何求得0/1背包问题的一个合理的上界呢？考虑最好背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第情况，背包中装入的全部是第1个物品且可以将背包装满，个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方

7、法：则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界于是，得到了目标函数的界40,100。第7页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 8假设背包中已装入物品的重量是假设背包中已装入物品的重量是w，获得的价值是，获得的价值是v，计算，计算该结点的目标函数上界的一个简单方法是把已经装入背该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值包中的物品取得的价值v，加上背包剩余容量，加上背包剩余容量W-w与剩下与剩下物品的最大单位重量价值物品的最大单位重量价值的积，于是，得到限界函

8、数为：的积，于是，得到限界函数为：第8页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 9w=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背包问题背包问题第9页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 10 分分支支限限界界法法求求解解0/1背背包包问问题题，其其搜搜索索空空间间如如图图9.1

9、所所示示，具体的搜索过程如下：具体的搜索过程如下：（1）在在根根结结点点1，没没有有将将任任何何物物品品装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值均均为为0，根根据据限限界界函函数数计计算算结结点点1的的目目标标函函数数值值为为1010=100；（2）在在结结点点2，将将物物品品1装装入入背背包包，因因此此，背背包包的的重重量量为为4，获获得得的的价价值值为为40，目目标标函函数数值值为为40+(10-4)6=76，将将结结点点2加加入入待待处处理理结结点点表表PT中中；在在结结点点3，没没有有将将物物品品1装装入入背背包包，因因此此，背背包包的的重重量量和和获获

10、得得的的价价值值仍仍为为0，目目标标函函数数值值为为10660，将将结结点点3加入表加入表PT中；中；（3）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进行搜索；优先进行搜索；第10页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 11（4）在在结结点点4，将将物物品品2装装入入背背包包，因因此此，背背包包的的重重量量为为11，不不满满足足约约束束条条件件，将将结结点点4丢丢弃弃；在在结结点点5，没没有有将将物物品品2装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值与与结结点点2相相同同，目目标标

11、函函数数值值为为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，将将结结点点

12、6加加入表入表PT中；中；第11页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 12（7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行搜索；优先进行搜索；（8）在结点）在结点8，将物品，将物品4装入背包，因此，背包的重量为装入背包，因此，背包的重量为12，不满足约束条件，将结点不满足约束条件，将结点8丢弃；在结点丢弃；在结点9，没有将物品，没有将物品4装入背装入背包，因此，背包的重量和获得的价值与结点包，因此，背包的重量和获得的价值与结点6相同，相同，目标函数值为目标函数值为65；（9）由由于于结结点点9是是叶叶子

13、子结结点点，同同时时结结点点9的的目目标标函函数数值值是是表表PT中的极大值，所以，结点中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。对应的解即是问题的最优解，搜索结束。第12页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 13 假假设设求求解解最最大大化化问问题题，解解向向量量为为X=(x1,x2,xn)，其其中中，xi的的取取值值范范围围为为某某个个有有穷穷集集合合Si，|Si|=ri（1in）。在在使使用用分分支支限限界界法法搜搜索索问问题题的的解解空空间间树树时时，首首先先根根据据限限界界函函数数估估算算目目标标函函数数的的界界do

14、wn,up，然然后后从从根根结结点点出出发发，扩扩展展根根结结点点的的r1个个孩孩子子结结点点，从从而而构构成成分分量量x1的的r1种种可可能能的的取取值值方方式式。对对这这r1个个孩孩子子结结点点分分别别估估算算可可能能取取得得的的目目标标函函数数值值bound(x1)，其其含含义义是是以以该该孩孩子子结结点点为为根根的的子子树树所所可可能能取取得得的的目目标标函函数数值值不不大大于于bound(x1)，也也就就是是部部分分解解应应满足：满足：bound(x1)bound(x1,x2)bound(x1,x2,xk)bound(x1,x2,xn)9.1.2 9.1.2 分支限界法的设计思想分支

15、限界法的设计思想 第13页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 14 若若某某孩孩子子结结点点的的目目标标函函数数值值超超出出目目标标函函数数的的界界，则则将将该该孩孩子子结结点点丢丢弃弃；否否则则，将将该该孩孩子子结结点点保保存存在在待待处处理理结结点点表表PT中中。从从表表PT中中选选取取使使目目标标函函数数取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，重重复复上上述述过过程程，当当到到达达一一个个叶叶子子结结点点时时，就就得得到到了了一一个个可可行行解解X=(x1,x2,xn)及及其其目目标标函函数值数值bo

16、und(x1,x2,xn)。第14页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 15如如果果bound(x1,x2,xn)是是表表PT中中目目标标函函数数值值最最大大的的结结点点，则则bound(x1,x2,xn)就就是是所所求求问问题题的的最最大大值值，(x1,x2,xn)就是问题的最优解；就是问题的最优解；如如果果bound(x1,x2,xn)不不是是表表PT中中目目标标函函数数值值最最大大的的结结点点，说说明明还还存存在在某某个个部部分分解解对对应应的的结结点点，其其上上界界大大于于bound(x1,x2,xn)。于于是是，用用bound(x1,

17、x2,xn)调调整整目目标标函函数数的的下下界界，即即令令down=bound(x1,x2,xn)，并并将将表表PT中中超超出出目目标标函函数数下下界界down的的结结点点删删除除，然然后后选选取取目目标标函函数数值值取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，继继续搜索，直到某个叶子结点的目标函数值在表续搜索，直到某个叶子结点的目标函数值在表PT中最大。中最大。第15页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 16分支限界法求解最大化问题的一般过程分支限界法求解最大化问题的一般过程分支限界法的一般过程分支限界法的一

18、般过程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 估算结点估

19、算结点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的结点删除；的结点删除；第16页，共57页，编辑于2022年，星期一2022/10/12第9章 分

20、支限界法 Page 17应用分支限界法的关键问题应用分支限界法的关键问题（1）如何确定合适的）如何确定合适的限界函数限界函数（2）如何组织）如何组织待处理结点表待处理结点表（3）如何确定最优解中的）如何确定最优解中的各个分量各个分量 第17页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 18分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数

21、值在表该叶子结点的目标函数值在表PT中最大时（假设求解最大化问题），中最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方法解决：解中的各个分量。这个问题可以用如下方法解决：对每个扩展结点保存该结点到根结点的路径；对每个扩展结点保存该结点到根结点的路径；在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构，在在求求得得最最优优解解时时，从从叶叶子子结点不断回溯到根结点，以确定最优解中的各个分量。结点不断回溯到根结点，以确定最优解中的各个分量。对于（对于（3）

22、：如何确定最优解中的各个分量：）：如何确定最优解中的各个分量：第18页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 19(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

23、(1,0)70 方法一：方法一：例如图例如图9.1所示所示0/1背包问题，为了对每个扩展结点保存该结点到根结背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解点的路径，将部分解(x1,xi)和该部分解的目标函数值都存储在待和该部分解的目标函数值都存储在待处理结点表处理结点表PT中，在搜索过程中表中，在搜索过程中表PT的状态如图的状态如图9.2所示。所示。第19页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 20(a)扩展根结点后扩展根结点后 (b)扩展结点扩展结点2后后(c)扩展结点扩展结点5后后 (d)扩展结点扩展结点6后，最优解为后，最优

24、解为(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中中，

25、表表PT和和表表ST的的数数据据结结构构为为(物物品品i-1的的选选择择结结果果，ub)，在在搜搜索索过过程程中中表表PT和和表表ST的的状状态态如图如图9.3所示。所示。第20页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 21 分分支支限限界界法法和和回回溯溯法法实实际际上上都都属属于于蛮蛮力力穷穷举举法法，当当然然不不能能指指望望它它有有很很好好的的最最坏坏时时间间复复杂杂性性，遍遍历历具具有有指指数数阶阶个个结结点点的的解解空空间间树树，在最坏情况下，时间复杂性肯定为指数阶。在最坏情况下，时间复杂性肯定为指数阶。与与回回溯溯法法不不同同的的是是，

26、分分支支限限界界法法首首先先扩扩展展解解空空间间树树中中的的上上层层结结点点，并并采采用用限限界界函函数数，有有利利于于实实行行大大范范围围剪剪枝枝，同同时时，根根据据限限界界函函数数不不断断调调整整搜搜索索方方向向，选选择择最最有有可可能能取取得得最最优优解解的的子子树树优优先先进进行行搜搜索索。所所以以，如如果果选选择择了了结结点点的的合合理理扩扩展展顺顺序序以以及及设设计计了了一一个个好好的的限限界界函函数，分支界限法可以快速得到问题的解。数，分支界限法可以快速得到问题的解。9.1.3 9.1.3 分支限界法的时间性能分支限界法的时间性能 第21页，共57页，编辑于2022年，星期一20

27、22/10/12第9章 分支限界法 Page 22 分支限界法的较高效率是以付出一定代价为基础的，其工作分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，一个更好的限界函数通方式也造成了算法设计的复杂性。首先，一个更好的限界函数通常需要花费更多的时间常需要花费更多的时间计算相应的目标函数值计算相应的目标函数值，而且对于具体的问，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，次，由于分支限界法对解空间树中结点的处理是

28、跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点保存该结点到根结点的路径的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表较为复杂；再次，算法要维护一个待处理结点表PTPT，并且需要在表，并且需要在表PTPT中中快速查找取得极值的结点快速查找取得极值的结点，等等。这都需要较大的存储空间，等等。这都需要较大的

29、存储空间，在最坏情况在最坏情况下，分支限界法需要的空间复杂性是指数阶。下，分支限界法需要的空间复杂性是指数阶。第22页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 239.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题9.2 9.2 图问题中的分支限界法图问题中的分支限界法 第23页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 24 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城市经个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程历

30、且仅经历一次然后回到出发城市，并要求所走的路程最短。最短。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 无向图及其代价矩阵无向图及其代价矩阵9.2.1 TSP9.2.1 TSP问题问题第24页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 25 采用贪心法求得近似解为采用贪心法求得近似解为135421，其路径长度为，其路径长度为1+2+3+7+3=16，这可以作为，这可以作为TSP问题的上界。问题的上界。把矩阵中

31、每一行最小的元素相加，可以得到一个简单的把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为下界，其路径长度为1+3+1+3+2=10，但是还有一个信息量更，但是还有一个信息量更大的下界：考虑一个大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以那么，如果把矩阵中每一行最小的两个元素相加再除以2，如果图中所，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了

32、一个合理的下有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。界。lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目标函数的界于是，得到了目标函数的界14,16。需要强调的是，这个解并不是一个合法的选择（可能没有构需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。成哈密顿回路），它仅仅给出了一个参考下界。第25页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 26部分解的目标函数值的计算方法部分解的目标函数值的计算方法 例例如如图图9.4所所示示无无向向图图，

33、如如果果部部分分解解包包含含边边(1,4)，则则该该部部分分解解的的下下界界是是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。第26页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 27412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=149101152lb=1954lb=14121342lb=161442lb=1845lb=15151652lb=2017分支限界法求解分支限界法求解TSP问题示例问题示例第

34、27页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 28应用分支限界法求解图应用分支限界法求解图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，目标函数的值为，目

35、标函数的值为(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，从城市，从城市

36、1到城市到城市5，路径长度为，路径长度为8，目标函数的值为，目标函数的值为(1+8)+(3+6)+(1+2)+(3+5)+(2+8)/2=19，超出目标函数的界，将结，超出目标函数的界，将结点点5丢弃；丢弃；第28页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 29（3）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点2优先进行搜索；优先进行搜索；（4）在结点）在结点6，从城市，从城市2到城市到城市3，目标函数值为，目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，将结点，将结点6加入表加入表PT中；在结

37、中；在结点点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)

38、+(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中；中；第29页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 30（7）在表）在表PT中选取目标函数值极

39、小的结点中选取目标函数值极小的结点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）在结点）在结点

40、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；第30页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 31（11）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点10优先进行搜索；优先进行搜索；（12）在结点

41、）在结点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

42、+3)+(3+9)+(1+4)+(3+4)+(9+3)/2=20，超出目标函数的界，将结点，超出目标函数的界，将结点17丢丢弃；弃；（15）表）表PT中目标函数值均为中目标函数值均为16，且有一个是叶子结点，且有一个是叶子结点14，所以，结，所以，结点点14对应的解对应的解135421即是即是TSP问题的最优解，搜索过程结束。问题的最优解，搜索过程结束。第31页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 32(g)扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421图图9.6 TSP问题最优解的确定问题最优解的确定(1,2)14 (1,

43、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,

44、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后的状态后的状态第32页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 33算法算法9.1TSP问题问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up；2将待

45、处理结点表将待处理结点表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段的最短边段的最短边第第第35页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 36 应应用用分分支支限限界界法法求求解解图图9.7所所示示多多段段图图的的最最短短路路径径问问题题，其其搜

46、搜索索空空间间如如图图9.8所所示示，具具体体的的搜搜索索过过程程如如下下（加加黑黑表表示示该该路路径径上上已已经经确定的边）：确定的边）：（1）在根结点）在根结点1，根据限界函数计算目标函数的值为，根据限界函数计算目标函数的值为14；（2）在结点）在结点2，第，第1段选择边段选择边，目标函数值为，目标函数值为lb=4+8+5+3=20，超出目标函数的界，将结点，超出目标函数的界，将结点2丢弃；在结点丢弃；在结点3，第，第1段选择边段选择边，目标函数值为目标函数值为lb=2+7+5+3=17，将结点，将结点3加入待处理结点表加入待处理结点表PT中；中；在结点在结点4，第，第1段选择边段选择边，

47、目标函数值为，目标函数值为lb=3+4+5+3=15，将结，将结点点4加入表加入表PT中；中；（3）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点4优先进行搜索；优先进行搜索；第36页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 37（4）在结点）在结点5，第，第2段选择边段选择边，目标函数值为，目标函数值为lb=3+4+6+3=16，将结点将结点5加入表加入表PT中；在结点中；在结点6，第，第2段选择边段选择边，目标函数值为，目标函数值为lb=3+7+5+3=18，将结点，将结点6加入表加入表PT中；中；（5）在表）在表PT中选取目

48、标函数值极小的结点中选取目标函数值极小的结点5优先进行搜索；优先进行搜索；（6）在结点）在结点7，第，第3段选择边段选择边，可直接确定第，可直接确定第4段的边段的边，目，目标函数值为标函数值为lb=3+4+8+7=22，为一个可行解但超出目标函数的界，为一个可行解但超出目标函数的界，将其丢弃；在结点将其丢弃；在结点8，第，第3段选择边段选择边，可直接确定第，可直接确定第4段的边段的边，目标函数值为，目标函数值为lb=3+4+6+3=16，为一，为一个较好的可行解。由于结点个较好的可行解。由于结点8是叶子结点，并且其目标函数值是表是叶子结点，并且其目标函数值是表PT中最小的，所以，结点中最小的，

49、所以，结点8代表的解即是问题的最优解，搜索过程结代表的解即是问题的最优解，搜索过程结束。束。第37页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 386401lb=20231startlb=1402lb=1703lb=15图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)535lb=1636lb=188757lb=2258lb=16第38页，共57页，编辑于2022年，星期一2022/10/12第9章 分支限界法 Page 3

50、9 为了在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表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,