《分支限界法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《分支限界法PPT讲稿.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、分支限界法第1页，共51页，编辑于2022年，星期五9.1 概概 述述 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2）9.1.2 分支限界法的设计思想分支限界法的设计思想9.1.3 分支限界法的时间性能分支限界法的时间性能第2页，共51页，编辑于2022年，星期五 回回溯溯法法从从根根结结点点出出发发，按按照照深深度度优优先先策策略略遍遍历历问问题题的的解解空空间间树树。例例如如，图图8.4所所示示对对0/1背背包包问问题题的的搜搜索索，如如果果某某结结点点所所代代表表的的部部分分解解不不满满足足约约束束条条件件（即即超超过过背背包包容容量量），则则对对以以该该结结点点为为根根的的子
2、子树树实实行行剪剪枝枝；否否则则，继继续续按按深深度度优优先先策策略略遍遍历历以以该该结结点点为为根根的的子子树树。这这种种遍遍历历过过程程一一直直进进行行，当当搜搜索索到到一一个个满满足足约约束束条条件件的的叶叶子子结结点点时时，就就找找到到了了一一个个可可行行解解。对对整整个个解解空空间间树树的的遍遍历历结结束束后后，所所有有可可行行解解中中价价值值最最大大的的就就是是问问题题的的最最优优解解。回回溯溯法法求求解解0/1背背包包问问题题，虽虽然然实实行行剪剪枝枝减减少少了了搜搜索索空空间间，但但是是，整整个个搜搜索索过过程程是是按按深深度度优优先先策策略略机机械械地进行，所以，这种搜索是盲
3、目的。地进行，所以，这种搜索是盲目的。分分支支限限界界法法首首先先确确定定一一个个合合理理的的限限界界函函数数，并并根根据据限限界界函函数数确确定定目标函数的界目标函数的界down,up（对于最小化问题，根据（对于最小化问题，根据9.1.1 解空间树的动态搜索（解空间树的动态搜索（2）第3页，共51页，编辑于2022年，星期五限界函数确定目标函数的下界限界函数确定目标函数的下界down，目标函数的上界，目标函数的上界up可以用某种启发可以用某种启发式方法得到。例如贪心法，对于最大化问题，根据限界函数确定目标函数的式方法得到。例如贪心法，对于最大化问题，根据限界函数确定目标函数的上界上界up，目
4、标函数的下界，目标函数的下界down可以用某种启发式方法得到）。然后，按可以用某种启发式方法得到）。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对于最小化问有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对于最小化问题，估算结点的下界；对于最大化问题，估算结点的上界），如果某孩子结题，估算结点的下界；对于最大化问题，估算结点的上界），如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点的目标函数可能取得的值超出目
5、标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表（以下简称表PT）中。依次从表）中。依次从表PT中选取使目标函数的值取得极值中选取使目标函数的值取得极值（对于最小化问题，是极小值；对于最大化问题，是极大值）的（对于最小化问题，是极小值；对于最大化问题，是极大值）的结点成为当前扩展结点，重复上述过程，直到找到最优解。结点成为当前扩展结点，重复上述过程，直到找到最优解。随随着着这这个个遍遍历历过过程程的的不不断断深深入入，表表PT中中所所估估算算的的目目标标函函数数的的界
6、界越越来来越接近问题的最优解。当搜索到一个叶子结点时越接近问题的最优解。当搜索到一个叶子结点时第4页，共51页，编辑于2022年，星期五，如如果果该该结结点点的的目目标标函函数数值值是是表表PT中中的的极极值值（对对于于最最小小化化问问题题，是是极极小小值值；对对于于最最大大化化问问题题，是是极极大大值值），则则该该叶叶子子结结点点对对应应的的解解就就是是问问题题的的最最优优解解；否否则则，根根据据这这个个叶叶子子结结点点调调整整目目标标函函数数的的界界（对对于于最最小小化化问问题题，调调整整上上界界；对对于于最最大大化化问问题题，调调整整下下界界），依依次次考考察察表表PT中中的的结结点点，
7、将将超超出出目目标标函函数数界界的的结结点点丢丢弃弃，然然后后从从表表PT中选取使目标函数取得极值的结点继续进行扩展。中选取使目标函数取得极值的结点继续进行扩展。下面以下面以0/1背包问题为例介绍分支限界法的搜索过程。假设有背包问题为例介绍分支限界法的搜索过程。假设有4个物品，其重量分别为个物品，其重量分别为(4,7,5,3)，价值分别为，价值分别为(40,42,25,12)，背，背包容量包容量W=10。首先，将给定物品按单位重量价值从大到小排序，。首先，将给定物品按单位重量价值从大到小排序，结果如表结果如表9.1所示。所示。物品重量(w)价值(v)价值/重量(v/w)144010274263
8、525543124表9.1 0/1背包问题的价值/重量排序结果第5页，共51页，编辑于2022年，星期五 这样，第这样，第1个物品给出了单位重量的最大价值，最后一个物品给出个物品给出了单位重量的最大价值，最后一个物品给出了单位重量的最小价值。应用贪心法求得近似解为了单位重量的最小价值。应用贪心法求得近似解为(1,0,0,0)，获得的价，获得的价值为值为40，这可以作为，这可以作为0/1背包问题的下界。如何求得背包问题的下界。如何求得0/1背包问题的一个背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以个物品且可以将背包装
9、满，则可以得到一个非常简单的上界的计算方法：将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界。于是，得到了目标函数的界40,100。一般情况下，解空间树中第一般情况下，解空间树中第i层的每个结点，都代表了对物品层的每个结点，都代表了对物品1i做出做出的某种特定选择，这个特定选择由从根结点到该结点的路径唯一确定：左分的某种特定选择，这个特定选择由从根结点到该结点的路径唯一确定：左分支表示装入物品，右分支表示不装入物品。对于第支表示装入物品，右分支表示不装入物品。对于第i层的某个结点，假设背层的某个结点，假设背包中已装入物品的重
10、量是包中已装入物品的重量是w，获得，获得的价值是的价值是v，计算该结点的目标函数上，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值界的一个简单方法是把已经装入背包中的物品取得的价值v，加上背包，加上背包剩余容量剩余容量W-w与剩下物品的最大单位重量价值与剩下物品的最大单位重量价值vi+1/wi+1的积，于是，得的积，于是，得到限界函数：到限界函数：（式（式9.1）第6页，共51页，编辑于2022年，星期五 分分支支限限界界法法求求解解0/1背背包包问问题题，其其搜搜索索空空间间如如图图9.1所所示示，具具体体的的搜索过程如下：搜索过程如下：（1）在在根根结结点点1，没
11、没有有将将任任何何物物品品装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值均均为为0，根根据据限限界界函函数数计计算算结结点点1的的目目标标函函数数值值为为1010=100；（2）在在结结点点2，将将物物品品1装装入入背背包包，因因此此，背背包包的的重重量量为为4，获获得得的的价价值值为为40，目目标标函函数数值值为为40+(10-4)6=76，将将结结点点2加加入入待待处处理理结结点点表表PT中中；在在结结点点3，没没有有将将物物品品1装装入入背背包包，因因此此，背背包包的的重重量量和和获获得的价值仍为得的价值仍为0，目标函数值为，目标函数值为10660，将结点，将结
12、点3加入表加入表PT中；中；（3）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进行搜索；优先进行搜索；（4）在在结结点点4，将将物物品品2装装入入背背包包，因因此此，背背包包的的重重量量为为11，不不满满足足约束条件，将结点约束条件，将结点4丢弃；在结点丢弃；在结点5，没有将，没有将第7页，共51页，编辑于2022年，星期五物物品品2装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值与与结结点点2相相同同，目目标标函函数数值为值为40+(10-4)5=70，将结点，将结点5加入表加入表PT中；中；（5）在表）在表PT中选取目标函数值取得
13、极大的结点中选取目标函数值取得极大的结点5优先进行搜索；优先进行搜索；（6）在在结结点点6，将将物物品品3装装入入背背包包，因因此此，背背包包的的重重量量为为9，获获得得的的价价值值为为65，目目标标函函数数值值为为65+(10-9)4=69，将将结结点点6加加入入表表PT中中；在在结结点点7，没没有有将将物物品品3装装入入背背包包，因因此此，背背包包的的重重量量和和获获得得的的价价值值与与结结点点5相相同，目标函数值为同，目标函数值为40+(10-4)464，将结点，将结点6加入表加入表PT中；中；（7）在表）在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6优先进行搜索
14、；优先进行搜索；（8）在在结结点点8，将将物物品品4装装入入背背包包，因因此此，背背包包的的重重量量为为12，不不满满足足约约束束条条件件，将将结结点点8丢丢弃弃；在在结结点点9，没没有有将将物物品品4装装入入背背包包，因因此此，背背包包的的重量和获得的价值与结点重量和获得的价值与结点6相同，相同，第8页，共51页，编辑于2022年，星期五目标函数值为目标函数值为65；（9）由由于于结结点点9是是叶叶子子结结点点，同同时时结结点点9的的目目标标函函数数值值是是表表PT中中的的极极大大值，所以，结点值，所以，结点9对应的解即是问题的最优解，搜索结束。对应的解即是问题的最优解，搜索结束。w=0,v
15、=0ub=100图9.1 分支限界法求解0/1背包问题示例（表示该结点被丢弃，结点上方的序号表示搜索顺序）w=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第9页，共51页，编辑于2022年，星期五9.1.2 分支限界法的设计思想分支限界法的设计思想 假假设设求求解解最最大大化化问问题题，问问题题的的解解向向量量为为X X=(=(x x1 1,x x2 2,x xn n)，其其中中，x xi i的的取取值值范范围围为为某某个个有有穷穷
16、集集合合S Si i，|S Si i|=|=r ri i（1 1i in n）。在在使使用用分分支支限限界界法法搜搜索索问问题题的的解解空空间间树树时时，首首先先根根据据限限界界函函数数估估算算目目标标函函数数的的界界 downdown,upup，然然后后从从根根结结点点出出发发，扩扩展展根根结结点点的的r r1 1个个孩孩子子结结点点，从从而而构构成成分分量量x x1 1的的r r1 1种种可可能能的的取取值值方方式式。对对这这r r1 1个个孩孩子子结结点点分分别别估估算算可可能能取取得得的的目目标标函函数数值值boundbound(x x1 1)，其其含含义义是是以以该该孩孩子子结结点点
17、为为根根的的子树所可能取得的目标函数值不大于子树所可能取得的目标函数值不大于boundbound(x x1 1)，也就是部分解应满足：，也就是部分解应满足：boundbound(x x1 1)boundbound(x x1,1,x x2 2)boundbound(x x1 1,x x2 2,x xk k)boundbound(x x1 1,x x2 2,x xn n)第10页，共51页，编辑于2022年，星期五若若某某孩孩子子结结点点的的目目标标函函数数值值超超出出目目标标函函数数的的界界，则则将将该该孩孩子子结结点点丢丢弃弃；否否则则，将将该该孩孩子子结结点点保保存存在在待待处处理理结结点点
18、表表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)不不是是表表
19、PT中中目目标标函函数数值值最最大大的的结结点点，说说明明还还存存在在某某个个部部分分解解对对应应的的结结点点，其其上上界界大大于于bound(x1,x2,xn)。于于是是，用用bound(x1,x2,xn)调调整整目目标标函函数数的的下下界界，即即令令down=bound(x1,x2,xn)，并并将将表表PT中中超超出出目目标标函函数数下下界界down的的结结点点删删除除，然然后后选选取取目目标标函函数数值值取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点，继续搜索，直到某个叶子结点的目标函数值在表继续搜索，直到某个叶子结点的目标函数值在表PT中最大。中最大。第1
20、1页，共51页，编辑于2022年，星期五 分支限界法求解最大化问题的一般过程如下：分支限界法求解最大化问题的一般过程如下：分支限界法的一般过程分支限界法的一般过程1根据限界函数确定目标函数的界根据限界函数确定目标函数的界down,up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作3.1 估算结点估算结点x的目标函数值的目标函数值value;3.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大
21、 3.1 i=表表PT中值最大的结点；中值最大的结点；3.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作3.2.1 估算结点估算结点x的目标函数值的目标函数值value;3.2.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；3.2.3 若若(结点结点x是叶子结点且结点是叶子结点且结点x的的value值在表值在表PT中最大中最大)，则，则将结点将结点x对应的解输出，算法结束；对应的解输出，算法结束；3.2.4 若若(结结点点x是是叶叶子子结结点点但但结结点点x的的value值值在在表表PT中中不不是是最最大大)，则则令令down=valu
22、e，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除；第12页，共51页，编辑于2022年，星期五 应用分支限界法的关键问题是：应用分支限界法的关键问题是：（1）如何确定合适的限界函数）如何确定合适的限界函数 分分支支限限界界法法在在遍遍历历过过程程中中根根据据限限界界函函数数估估算算某某结结点点的的目目标标函函数数的的可可能能取取值值。好好的的限限界界函函数数不不仅仅计计算算简简单单，还还要要保保证证最最优优解解在在搜搜索索空空间间中中，更更重重要要的的是是能能在在搜搜索索的的早早期期对对超超出出目目标标函函数数界界的的结结点点进进行行丢丢弃弃，减减少少搜搜索索空空
23、间间，从从而而尽尽快快找找到到问问题题的的最最优优解解。有有时时，对对于于具具体体的的问问题题实实例例需需要要进行大量实验，才能确定一个合理的限界函数。进行大量实验，才能确定一个合理的限界函数。（2）如何组织待处理结点表）如何组织待处理结点表 为为了了能能在在待待处处理理结结点点表表PT中中选选取取使使目目标标函函数数取取得得极极值值（极极大大或或极极小小）的的结结点点时时提提高高查查找找效效率率，表表PT可可以以采采用用堆堆的的形形式式，也也可可以以采采用用优优先先队队列列的形式存储。的形式存储。（3）如何确定最优解中的各个分量）如何确定最优解中的各个分量 第13页，共51页，编辑于2022
24、年，星期五分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表子结点的目标函数值在表PT中最大时（假设求解最大化问题），求得了问中最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方法解决：这个问题可以用如下方法解决：对每个扩展结点保存该结
25、点到根结点的路径；对每个扩展结点保存该结点到根结点的路径；在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构，在在求求得得最最优优解解时时，从从叶叶子结点不断回溯到根结点，以确定最优解中的各个分量。子结点不断回溯到根结点，以确定最优解中的各个分量。例如图例如图9.19.1所示所示0/10/1背包问题，为了对每个扩展结点保存该结点到根背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解结点的路径，将部分解(x x1 1,x xi i)和该部分解的目标函数值都存储在和该部分解的目标函数值都存储在待处理结点表待处理结点表PTPT中，在搜索过程中表中，在搜索过程中表PTPT的状
26、态如图的状态如图9.29.2所示。所示。第14页，共51页，编辑于2022年，星期五(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背背包包问问题题，为为了了在在搜搜索索过过程程中中构构建建搜搜
27、索索经经过过的的树树结结构构，设设一一个个表表ST，在在表表PT中中取取出出最最小小值值结结点点进进行行扩扩充充时时，将将最最小小值值结结点点存存储储到到表表ST中中，表表PT和和表表ST的的数数据据结结构构为为(物物品品i-1的的选选择择结结果果，ub)，在在搜搜索索过过程程中中表表PT和和表表ST的的状状态态如如图图9.3所示。所示。在扩展结点在扩展结点6求得最优值求得最优值65时，可知物品时，可知物品4没有被装入背包，而物没有被装入背包，而物品品3被装入背包，在表被装入背包，在表ST中回溯，物品中回溯，物品2没有被装入背包，物品没有被装入背包，物品1被装入被装入背包，回溯所经过的路线是：
28、背包，回溯所经过的路线是：1,650,691,700,76。第15页，共51页，编辑于2022年，星期五(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)第16页，共51页，编辑于2022
29、年，星期五9.1.3 分支限界法的时间性能分支限界法的时间性能 一一般般情情况况下下，在在问问题题的的解解向向量量X=(x1,x2,xn)中中，分分量量xi(1in)的的取取值值范范围围为为某某个个有有限限集集合合Si=ai1,ai2,airi，因因此此，问问题题的的解解空空间间由由笛笛卡卡儿儿积积A=S1S2Sn构构成成，并并且且第第1层层的的根根结结点点有有|S1|棵棵子子树树，则则第第2层层共共有有|S1|个个结结点点，第第2层层的的每每个个结结点点有有|S2|棵棵子子树树，则则第第3层层共共有有|S1|S2|个个结结点点，依依此此类类推推，第第n+1层层共共有有|S1|S2|Sn|个个
30、结结点点，他他们都是叶子结点，代表问题的所有可能解。们都是叶子结点，代表问题的所有可能解。分支限界法和回溯法实际上都属于蛮力穷举法，当然不能指望分支限界法和回溯法实际上都属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。与回溯法不同的是，分在最坏情况下，时间复杂性肯定为指数阶。与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，有利支限界法首先扩展解空间树中的上层结点，并采用限界函数，有利于实行大于实行大第17页，共51页，编辑于2022年，
31、星期五范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。分分支支限限界界法法可可以以对对许许多多组组合合问问题题的的较较大大规规模模的的输输入入实实例例在在合合理理的的时时间间内内求求解解，然然而而，对对于于具具体体的的问问题题实实例例，很很难难预预测测分分支支限限界界法法的的搜搜索索
32、行行为为，无无法法从从实实质质上上预预先先判判定定，哪哪些些实实例例可可以以在在合合理理的的时时间间内内求求解解，哪些实例不能在合理的时间内求解。哪些实例不能在合理的时间内求解。分支限界法的较高效率是以付出一定代价为基础的，其工分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，一个更好的限界函作方式也造成了算法设计的复杂性。首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的具体的问题实例，通常需要进行大量实验，才能确定一个好
33、的限界函数；其次，由于分支限界法对解限界函数；其次，由于分支限界法对解第18页，共51页，编辑于2022年，星期五空间树中结点的处理是跳跃式的，因此，在搜索到某个空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表为复杂；再次，
34、算法要维护一个待处理结点表PTPT，并且需要在，并且需要在表表PTPT中快速查找取得极值的结点，等等。这都需要较大的存储空间，中快速查找取得极值的结点，等等。这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。在最坏情况下，分支限界法需要的空间复杂性是指数阶。第19页，共51页，编辑于2022年，星期五9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题第20页，共51页，编辑于2022年，星期五9.2.1 TSP问题问题 TSPTSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各
35、个城市经历且仅个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。经历一次然后回到出发城市，并要求所走的路程最短。图图9.4(a)9.4(a)所示是一个带权无向图，所示是一个带权无向图，(b)(b)是该图的代价矩阵。是该图的代价矩阵。271563134253984C=3 1 5 83 6 7 91 6 4 25 7 4 38 9 2 3 (a)一个无向图一个无向图 (b)无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵 对图对图9.4所示无向图采用贪心法求得近似解为所示无向图采用贪心法求得近似解为135421，其路径长度为，其路径长度为1
36、+2+3+7+3=16，这可以作为，这可以作为TSP问题的上界。问题的上界。第21页，共51页，编辑于2022年，星期五把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为路径长度为1+3+1+3+2=10，但是还有一个信息量更大的下界：考虑，但是还有一个信息量更大的下界：考虑一个一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最
37、小的两个元素相加再除以中每一行最小的两个元素相加再除以2 2，如果图中所有的代价都是整，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。需要强调数，再对这个结果向上取整，就得到了一个合理的下界。需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。对图它仅仅给出了一个参考下界。对图9.49.4所示无向图，目标函数的下界所示无向图，目标函数的下界是：是：lblb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14=(1+3)+(3+6)+(1+2)+(3
38、+4)+(2+3)/2=14。于是，得。于是，得到了目标函数的界到了目标函数的界14,1614,16。某某条条路路径径的的一一些些边边被被确确定定后后，就就可可以以并并入入这这些些信信息息并并计计算算部部分分解解的的目目标标函函数数值值的的下下界界。一一般般情情况况下下，对对于于一一个个正正在在生生成成的的路路径径，假假设设已已确确定定的的顶点集合顶点集合U U=(=(r r1 1,r r2 2,rk)，即路径上已确定了，即路径上已确定了k个顶点个顶点。第22页，共51页，编辑于2022年，星期五该部分解的目标函数值的计算方法如下：该部分解的目标函数值的计算方法如下：（式（式9.29.2）例例
39、如如图图9.4所所示示无无向向图图，如如果果部部分分解解包包含含边边(1,4)，则则该该部部分分解解的的下下界界是是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。应应用用分分支支限限界界法法求求解解图图9.4所所示示无无向向图图的的TSP问问题题，其其搜搜索索空空间间如如图图9.5所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点）在根结点1，根据限界函数计算目标函数的值为，根据限界函数计算目标函数的值为lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14；（2
40、2）在结点）在结点2 2，从城市，从城市1 1到城市到城市2 2，路径长度为，路径长度为3 3，目标函数，目标函数第23页，共51页，编辑于2022年，星期五的值为的值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点，将结点2 2加入待处加入待处理结点表理结点表PTPT中；在结点中；在结点3 3，从城市，从城市1 1到城市到城市3 3，路径长度为，路径长度为1 1，目标函数，目标函数的值为的值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14(1+3)+(3+6)+(1+2)+
41、(3+4)+(2+3)/2=14，将结点，将结点3 3加入表加入表PTPT中；在结点中；在结点4 4，从城市，从城市1 1到城市到城市4 4，路径长度为，路径长度为5 5，目标函数的值为，目标函数的值为(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16，将结点，将结点4 4加入表加入表PTPT中；中；在结点在结点5 5，从城市，从城市1 1到城市到城市5 5，路径长度为，路径长度为8 8，目标函数的值为，目标函数的值为(1+8)+(3+6)+(1+2)+(3+5)+(2+8)/2=19(1+8)+(3+6)+
42、(1+2)+(3+5)+(2+8)/2=19，超出目标函数的界，将结点，超出目标函数的界，将结点5 5丢弃；丢弃；（3 3）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点2 2优先进行搜索；优先进行搜索；（4 4）在结点）在结点6 6，从城市，从城市2 2到城市到城市3 3，目标函数值为，目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，将结点，将结点6 6加入表加入表PTPT中；在中；在结点结点7 7，从城市，从城市2 2到城市到城市4 4，目标函数值为，目标函数值为(
43、1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16，将结点，将结点7 7加入表加入表PTPT中；在结中；在结点点8 8，从城市，从城市2 2到城市到城市5 5，目标函数值为，目标函数值为第24页，共51页，编辑于2022年，星期五(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19，超出目标函数的界，将结，超出目标函数的界，将结点点8 8丢弃；丢弃；（5 5）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点
44、3 3优先进行搜索；优先进行搜索；（6 6）在结）在结点点9 9，从城市，从城市3 3到城市到城市2 2，目标函数值为，目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，将结点，将结点9 9加入表加入表PTPT中；在结中；在结点点1010，从城市，从城市3 3到城市到城市4 4，目标函数值为，目标函数值为(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15，将结点，将结点1010加入表加入表PTPT中；在中；在结
45、点结点1111，从城市，从城市3 3到城市到城市5 5，目标函数值为，目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点，将结点1111加入表加入表PTPT中；中；（7 7）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点1111优先进行搜索；优先进行搜索；（8 8）在结点）在结点1212，从城市，从城市5 5到城市到城市2 2，目标函数值为，目标函数值为(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19(1+3)+(3+9)+(1+2)+(3+4)
46、+(2+9)/2=19，超出目标函数的界，将结点，超出目标函数的界，将结点1212丢弃；在结点丢弃；在结点1313，从城市，从城市5 5到城市到城市4 4，目标函数值为，目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点，将结点1313第25页，共51页，编辑于2022年，星期五加入表加入表PTPT中；中；（9）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点13优先进行搜索；优先进行搜索；（10）在结点）在结点14，从城市，从城市4到城市到城市2，目标函数值为，目标函数
47、值为(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，超出目标函数
48、的界，将结点，超出目标函数的界，将结点15丢弃；在结点丢弃；在结点16，从城市，从城市4到城市到城市5，目标函数值为，目标函数值为(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15，将结点，将结点16加入表加入表PT中；中；第26页，共51页，编辑于2022年，星期五（13）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点16优先进行搜索；优先进行搜索；（14）在结点）在结点17，从城市，从城市5到城市到城市2，目标函数的值为，目标函数的值为(1+3)+(3+9)+(1+4)+(3+4)+(9+3)/2=20，超出目标函数的界，将结点，超出目标函数的界，将结
49、点17丢弃；丢弃；（15）表）表PT中目标函数值均为中目标函数值均为16，且有一个是叶子结点，且有一个是叶子结点14，所以，结，所以，结点点14对应的解对应的解135421即是即是TSP问题的最优解，搜索过程结问题的最优解，搜索过程结束。束。第27页，共51页，编辑于2022年，星期五412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=14911图图9.5 分支限界法求解分支限界法求解TSP问题示例问题示例(表示该结点被丢弃，结点上方数字表示搜索顺序表示该结点被丢弃，结点上方
50、数字表示搜索顺序)52lb=1954lb=141142lb=16142lb=1845lb=151152lb=201 为了对每个扩展结点保存该结点到根结点的路径，将部分解为了对每个扩展结点保存该结点到根结点的路径，将部分解(x1,xi)和该部分解的目标函数值都存储在待处理结点表和该部分解的目标函数值都存储在待处理结点表PT中，在中，在搜索过程中表搜索过程中表PT的状态如图的状态如图9.6所示。所示。第28页，共51页，编辑于2022年，星期五(g)扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421图图9.6 TSP问题最优解的确定问题最优解的确定(1,2)14 (1,3)14