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