第9章分支限界法精选PPT.ppt

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