1、分支限界法1.分支限界法的基本思想2.分支限界法在各种问题中的应用 分支限界法首先确定一个合理的分支限界法首先确定一个合理的限界函数限界函数，并根据限界，并根据限界函数确定目标函数的界函数确定目标函数的界 downdown,upup 。然后，按照然后，按照广度优先策略广度优先策略遍历问题的解空间树，在分支结点遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入
2、取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表待处理结点表（表（表PTPT）中。）中。依次从表依次从表PTPT中选取使目标函数的值取得极值的结点成为中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。当前扩展结点，重复上述过程，直到找到最优解。9.1 9.1 概述概述9.1.1 9.1.1 解空间树的动态搜索（解空间树的动态搜索（2 2）随着遍历过程的深入，表随着遍历过程的深入，表PTPT中所估算的目标函数的界越中所估算的目标函数的界越来越接近问题的最优解。来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是当搜索到一个叶子结点
3、时，如果该结点的目标函数值是表表PTPT中的极值，则该叶子结点对应的解就是问题的最优解；中的极值，则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表题，调整上界；对于最大化问题，调整下界），依次考察表PTPT中的结点，将超出目标函数界的结点丢弃，然后从表中的结点，将超出目标函数界的结点丢弃，然后从表PTPT中中选取使目标函数取得极值的结点继续进行扩展。选取使目标函数取得极值的结点继续进行扩展。例：例：0/10/1背包问题。假设有背包问题。假设有4 4个
4、物品，其重量分别为个物品，其重量分别为(4,7,5,3)(4,7,5,3)，价值分别为价值分别为(40,42,25,12)(40,42,25,12)，背包容量，背包容量WW=10=10。首先，将给定物品按单位重量价值从大到小排序：首先，将给定物品按单位重量价值从大到小排序：物品物品重量重量(w w)价值价值(v v)价值价值/重量重量(v v/w w)1 14 4404010102 27 742426 63 35 525255 54 43 312124 4（1 1）应用贪心法求得近似解为）应用贪心法求得近似解为(1,0,0,0)(1,0,0,0)，获得的价值为，获得的价值为4040-作为作为0
5、/10/1背包问题的背包问题的下界下界。（2 2）0/10/1背包问题的背包问题的上界上界：最好情况下，背包中装入的全部是第：最好情况下，背包中装入的全部是第1 1个物品且可以将背个物品且可以将背包装满，则包装满，则ubub=WW(v v1 1/w w1 1)=10)=1010=10010=100。（3 3）目标函数的界目标函数的界40,10040,100。限界函数限界函数为：为：)()(11iiwvwWvubw=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无效
6、解无效解w=9,v=65ub=65234567891分支限界法求解分支限界法求解0/10/1背包问题背包问题 分支限界法求解分支限界法求解0/10/1背包问题，其搜索空间如图背包问题，其搜索空间如图9.19.1所示，所示，具体的搜索过程如下：具体的搜索过程如下：（1 1）在根结点）在根结点1 1，没有将任何物品装入背包，因此，背包的重，没有将任何物品装入背包，因此，背包的重量和获得的价值均为量和获得的价值均为0 0，根据限界函数计算结点，根据限界函数计算结点1 1的目标函数值的目标函数值为为101010=10010=100；（2 2）在结点）在结点2 2，将物品，将物品1 1装入背包，因此，背
7、包的重量为装入背包，因此，背包的重量为4 4，获，获得的价值为得的价值为4040，目标函数值为，目标函数值为40+(10-4)40+(10-4)6=766=76，将，将结点结点2 2加入加入待处理结点表待处理结点表PTPT中；在结点中；在结点3 3，没有将物品，没有将物品1 1装入背包，因此，装入背包，因此，背包的重量和获得的价值仍为背包的重量和获得的价值仍为0 0，目标函数值为，目标函数值为10106 66060，将，将结点结点3 3加入表加入表PTPT中；中；（3 3）在表）在表PTPT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2 2优先进行搜索；优先进行搜索；（4 4）
8、在结点）在结点4 4，将物品，将物品2 2装入背包，因此，背包的重量为装入背包，因此，背包的重量为1111，不满足约束条件，将结点不满足约束条件，将结点4 4丢弃；在结点丢弃；在结点5 5，没有将物品，没有将物品2 2装入装入背包，因此，背包的重量和获得的价值与结点背包，因此，背包的重量和获得的价值与结点2 2相同，目标函相同，目标函数值为数值为40+(10-4)40+(10-4)5=705=70，将结点，将结点5 5加入表加入表PTPT中；中；（5 5）在表）在表PTPT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5 5优先进行搜索；优先进行搜索；（6 6）在结点）在结点6
9、6，将物品，将物品3 3装入背包，因此，背包的重量为装入背包，因此，背包的重量为9 9，获，获得的价值为得的价值为6565，目标函数值为，目标函数值为65+(10-9)65+(10-9)4=694=69，将结点，将结点6 6加入加入表表PTPT中；在结点中；在结点7 7，没有将物品，没有将物品3 3装入背包，因此，背包的重量装入背包，因此，背包的重量和获得的价值与结点和获得的价值与结点5 5相同，目标函数值为相同，目标函数值为40+(10-4)40+(10-4)4 46464，将结点将结点7 7加入表加入表PTPT中；中；（7 7）在表）在表PTPT中选取目标函数值取得极大的结点中选取目标函数
10、值取得极大的结点6 6优先进行搜索；优先进行搜索；（8 8）在结点）在结点8 8，将物品，将物品4 4装入背包，因此，背包的重量为装入背包，因此，背包的重量为1212，不，不满足约束条件，将结点满足约束条件，将结点8 8丢弃；在结点丢弃；在结点9 9，没有将物品，没有将物品4 4装入背包，装入背包，因此，背包的重量和获得的价值与结点因此，背包的重量和获得的价值与结点6 6相同，目标函数值为相同，目标函数值为6565；（9 9）由于结点）由于结点9 9是叶子结点，同时结点是叶子结点，同时结点9 9的目标函数值是表的目标函数值是表PTPT中中的极大值，所以，结点的极大值，所以，结点9 9对应的解即
11、是问题的最优解，搜索结束。对应的解即是问题的最优解，搜索结束。9.1.2 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（11i in n）。）。在使用分支限界法搜索问题的解空间树时，首先根据限在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界界函数估算目标函数的界 downdown,upup，然后从根结点出发，然后从根结点出发，扩展根
12、结点的扩展根结点的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
13、x2 2,x xk k)boundbound(x x1 1,x x2 2,x xn n)若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表将该孩子结点保存在待处理结点表PTPT中。中。从表从表PTPT中选取使目标函数取得极大值的结点作为下一次扩展的根结点，重复上中选取使目标函数取得极大值的结点作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行解述过程，当到达一个叶子结点时，就得到了一个可行解X X=(=(x x1 1,x x2 2,x xn n)及其目标
14、函数及其目标函数值值boundbound(x x1 1,x x2 2,x xn n)。如果如果boundbound(x x1 1,x x2 2,x xn n)是表是表PTPT中目标函数值最大的结点，则中目标函数值最大的结点，则boundbound(x x1 1,x x2 2,x xn n)就是所求问题的最大值，就是所求问题的最大值，(x x1 1,x x2 2,x xn n)就是问题的最优解；就是问题的最优解；如果如果boundbound(x x1 1,x x2 2,x xn n)不是表不是表PTPT中目标函数值最大的结点，说明还存在某个部中目标函数值最大的结点，说明还存在某个部分解对应的结点
15、，其上界大于分解对应的结点，其上界大于boundbound(x x1 1,x x2 2,x xn n)。于是，用。于是，用boundbound(x x1 1,x x2 2,x xn n)调整目调整目标函数的下界，即令标函数的下界，即令downdown=boundbound(x x1 1,x x2 2,x xn n)，并将表，并将表PTPT中超出目标函数下界中超出目标函数下界downdown的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表续搜索，直到某个叶子结点
16、的目标函数值在表PTPT中最大。中最大。分支限界法求解最大化问题的一般过程分支限界法求解最大化问题的一般过程分支限界法的一般过程分支限界法的一般过程1 1根据限界函数确定目标函数的界根据限界函数确定目标函数的界down,updown,up；2 2将待处理结点表将待处理结点表PTPT初始化为空；初始化为空；3 3对根结点的每个孩子结点对根结点的每个孩子结点x x执行下列操作执行下列操作 3.1 3.1 估算结点估算结点x x的目标函数值的目标函数值value;value;3.2 3.2 若若(value=down)(value=down)，则将结点，则将结点x x加入表加入表PTPT中；中；4
17、4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PTPT中最大中最大 4.1 i=4.1 i=表表PTPT中值最大的结点；中值最大的结点；4.2 4.2 对结点对结点i i的每个孩子结点的每个孩子结点x x执行下列操作执行下列操作 4.2.1 4.2.1 估算结点估算结点x x的目标函数值的目标函数值value;value;4.2.2 4.2.2 若若(value=down)(value=down)，则将结点，则将结点x x加入表加入表PTPT中；中；4.2.3 4.2.3 若若(结点结点x x是叶子结点且结点是叶子结点且结点x x的的valuevalue值在表值在表
18、PTPT中最大中最大)，则将结点则将结点x x对应的解输出，算法结束；对应的解输出，算法结束；4.2.4 4.2.4 若若(结点结点x x是叶子结点但结点是叶子结点但结点x x的的valuevalue值在表值在表PTPT中不是最大中不是最大)，则令则令down=valuedown=value，并且将表，并且将表PTPT中所有小于中所有小于valuevalue的结点删除；的结点删除；应用分支限界法的关键问题应用分支限界法的关键问题（1 1）确定合适的）确定合适的限界函数限界函数（2 2）组织）组织待处理结点表待处理结点表PTPT（3 3）确定最优解中的）确定最优解中的各个各个分量分量 分支限界法
19、对问题的解空间树中结点的处理是跳跃式的，分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯。回溯也不是单纯地沿着双亲结点一层一层向上回溯。当搜索到某个叶子结点且该叶子结点的目标函数值在表当搜索到某个叶子结点且该叶子结点的目标函数值在表PTPT中最大时（假设求解最大化问题），求得了问题的最优值。中最大时（假设求解最大化问题），求得了问题的最优值。但是，却无法求得该叶子结点对应的最优解中的各个分量。这但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下个问题可以用如下2 2种种方法解决：方法解决：对每个扩展结点保存该结点到根结点的路径；
20、对每个扩展结点保存该结点到根结点的路径；在搜索过程中构建搜索经过的树结构，在求得最优解时，在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。从叶子结点不断回溯到根结点，以确定最优解中的各个分量。(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背包问题最优解的各分量背包问题最优解的各
21、分量(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 例如图例如图9.19.1所示所示0/10/1背包问题，为了对每个扩展结点保存该背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解结点到根结点的路径，将部分解(x x1 1,x xi i)和该部分解的目和该部分解的目标函数值都存储在待处理结点表标函数值都存储在待处理结点表PTPT中，在搜索过程中表中，在搜索过程中表PTPT的状态如图的状态如图9.29.2所示。所示。(a)扩展根结点后扩展根结点后 (b)扩展结点扩展结点2后后(c)扩展结点扩展结点5后后 (d)扩展结点扩展结点6后，
22、最优解为后，最优解为(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.19.1所示所示0/10/1背包问题，为了在搜索过程中构建搜索经过的背包问题，为了在搜索过程中构建搜索经过的树结构，设一个表树结构，设一个表STST，在表，在表PTPT中取出最大值结点进行扩充时，中取出最大值结点进行扩充时，将最大值结点存储到表将
23、最大值结点存储到表STST中，表中，表PTPT和表和表STST的数据结构为的数据结构为(物物品品i i-1-1的选择结果，的选择结果，ubub)，在搜索过，在搜索过程中表程中表PTPT和表和表STST的状态如图的状态如图9.39.3所示。所示。9.1.3 9.1.3 分支限界法的时间性能分支限界法的时间性能 分支限界法和回溯法实际上都属于蛮力穷举法。分支限界法和回溯法实际上都属于蛮力穷举法。与回溯法不同的是，分支限界法首先扩展解空间树中与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点（的上层结点（广度优先广度优先），并采用），并采用限界函数限界函数，有利于实，有利于实行大范围剪枝，同时
24、，根据限界函数不断调整搜索方向，行大范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。选择最有可能取得最优解的子树优先进行搜索。关键点：结点的合理扩展顺序、好的限界函数关键点：结点的合理扩展顺序、好的限界函数分支限界法的较高效率是以付出一定代价为基础的，其分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。工作方式也造成了算法设计的复杂性。首先首先，通常需要进行大量实验确定，通常需要进行大量实验确定限界函数限界函数其次，由于分支限界法对解空间树中结点的处理是跳跃式的，其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，
25、在搜索到某个叶子结点得到最优值时，为了从该叶子因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的保存该结点到根结点的路径路径，或者在搜索过程中构建搜索经，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个再次，算法要维护一个待处理结点表待处理结点表PTPT，并且需要在表，并且需要在表PTPT中快中快速查找取得极值的结点，等等。这都需要较大的存储空间，速查找取得极值的结点，等等。这都需要较大的存储空间
26、，在最坏情况下，分支限界法需要的空间复杂性是指数阶。在最坏情况下，分支限界法需要的空间复杂性是指数阶。9.2 9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP9.2.1 TSP问题问题 9.2.2 9.2.2 多段图的最短路径问题多段图的最短路径问题9.2.1 TSP9.2.1 TSP问题问题 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城市个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的经历且仅经历一次然后回到出发城市，并要求所走的路程最短。路程最短。271563134253984C=3 1 5 8 3 6 7 9 1 6
27、 4 2 5 7 4 3 8 9 2 3 (a)一个无向图一个无向图 (b)无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵 采用贪心法求得近似解为采用贪心法求得近似解为135421135421，其路径，其路径长度为长度为1+2+3+7+3=161+2+3+7+3=16，这可以作为，这可以作为TSPTSP问题的上界。问题的上界。把矩阵中每一行最小的元素相加，可以得到一个简单把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为的下界，其路径长度为1+3+1+3+2=101+3+1+3+2=10，但是还有一个信，但是还有一个信息量更大的下界：考虑一个息
28、量更大的下界：考虑一个TSPTSP问题的完整解，在每条路问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以小的两个元素相加再除以2 2，如果图中所有的代价都是整数，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。再对这个结果向上取整，就得到了一个合理的下界。lb lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14=(1+3)+(3+6)+(1+2)+
29、(3+4)+(2+3)/2=14 于是，得到了目标函数的界于是，得到了目标函数的界14,1614,16。需要强调的是，这个解并不是一个合法的选择（可能没有需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。构成哈密顿回路），它仅仅给出了一个参考下界。部分解的目标函数值的计算方法部分解的目标函数值的计算方法 图图9.49.4所示无向图，如果部分解包含边所示无向图，如果部分解包含边(1,4)(1,4)，则该部，则该部分解的下界是分解的下界是lb lb=(1+=(1+5 5)+(3+6)+(1+2)+(3+)+(3+6)+(1+2)+(3+5 5)+(2+3
30、)/2=16)+(2+3)/2=16。UrUrjikiiiijrrrrclb2/)2(111行最小的两个元素素行不在路径上的最小元412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=149101152lb=1954lb=14121342lb=161442lb=1845lb=15151652lb=2017分支限界法求解分支限界法求解TSPTSP问题示例问题示例应用分支限界法求解图应用分支限界法求解图9.49.4所示无向图的所示无向图的TSPTSP问题，其搜索空间问题，其搜索空间
31、如图如图9.59.5所示，具体的搜索过程如下（加黑表示该路径上已经确所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：定的边）：（1 1）在）在根结点根结点1 1，根据限界函数计算目标函数的值为，根据限界函数计算目标函数的值为lb lb=(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）在）在结点结点2 2，从城市，从城市1 1到城市到城市2 2，路径长度为，路径长度为3 3，目标函数的值，目标函数的值为为(1+(1+3 3)+()+(3 3+6)+(1+2)+(3+4)+(2+3)/2
32、=14+6)+(1+2)+(3+4)+(2+3)/2=14，将结点，将结点2 2加入待处理加入待处理结点表结点表PTPT中；在中；在结点结点3 3，从城市，从城市1 1到城市到城市3 3，路径长度为，路径长度为1 1，目标，目标函数的值为函数的值为(1 1+3)+(3+6)+(+3)+(3+6)+(1 1+2)+(3+4)+(2+3)/2=14+2)+(3+4)+(2+3)/2=14，将结点，将结点3 3加加入表入表PTPT中；在中；在结点结点4 4，从城市，从城市1 1到城市到城市4 4，路径长度为，路径长度为5 5，目标函，目标函数的值为数的值为(1+(1+5 5)+(3+6)+(1+2)
33、+(3+)+(3+6)+(1+2)+(3+5 5)+(2+3)/2=16)+(2+3)/2=16，将结点，将结点4 4加入加入表表PTPT中；在中；在结点结点5 5，从城市，从城市1 1到城市到城市5 5，路径长度为，路径长度为8 8，目标函数，目标函数的值为的值为(1+(1+8 8)+(3+6)+(1+2)+(3+4)+(2+)+(3+6)+(1+2)+(3+4)+(2+8 8)/2=19)/2=19，超出目标函数，超出目标函数的界，将结点的界，将结点5 5丢弃；丢弃；（3 3）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点2 2优先进行搜索；优先进行搜索；（4 4）
34、在）在结点结点6 6，从城市，从城市2 2到城市到城市3 3，目标函数值为，目标函数值为(1+(1+3 3)+()+(3 3+6 6)+(1+)+(1+6 6)+(3+4)+(2+3)/2=16)+(3+4)+(2+3)/2=16，将结点，将结点6 6加入表加入表PTPT中；中；在在结点结点7 7，从城市，从城市2 2到城市到城市4 4，目标函数值为，目标函数值为(1+(1+3 3)+()+(3 3+7 7)+(1+2)+(3+)+(1+2)+(3+7 7)+(2+3)/2=16)+(2+3)/2=16，将结点，将结点7 7加入表加入表PTPT中；中；在在结点结点8 8，从城市，从城市2 2到
35、城市到城市5 5，目标函数值为，目标函数值为(1+(1+3 3)+()+(3 3+9 9)+(1+2)+(3+4)+(2+)+(1+2)+(3+4)+(2+9 9)/2=19)/2=19，超出目标函数的界，将结，超出目标函数的界，将结点点8 8丢弃；丢弃；（5 5）在表）在表PTPT中选取目标函数值极小的中选取目标函数值极小的结点结点3 3优先进行搜索优先进行搜索；（6 6）在）在结点结点9 9，从城市，从城市3 3到城市到城市2 2，目标函数值为，目标函数值为(1 1+3)+(3+3)+(3+6 6)+()+(1 1+6 6)+(3+4)+(2+3)/2=16)+(3+4)+(2+3)/2=
36、16，将结点，将结点9 9加入表加入表PTPT中；中；在在结点结点1010，从城市，从城市3 3到城市到城市4 4，目标函数值为，目标函数值为(1 1+3)+(3+6)+(+3)+(3+6)+(1 1+4 4)+(3+)+(3+4 4)+(2+3)/2=15)+(2+3)/2=15，将结点，将结点1010加入表加入表PTPT中；中；在在结点结点1111，从城市，从城市3 3到城市到城市5 5，目标函数值为，目标函数值为(1 1+3)+(3+6)+(+3)+(3+6)+(1 1+2 2)+(3+4)+()+(3+4)+(2 2+3)/2=14+3)/2=14，将结点，将结点1111加入表加入表P
37、TPT中；中；（7 7）在表）在表PTPT中选取目标函数值极小的中选取目标函数值极小的结点结点1111优先进行搜索优先进行搜索；（8 8）在）在结点结点1212，从城市，从城市5 5到城市到城市2 2，目标函数值为，目标函数值为(1 1+3)+(3+3)+(3+9 9)+()+(1 1+2 2)+(3+4)+()+(3+4)+(2 2+9 9)/2=19)/2=19，超出目标函数的界，超出目标函数的界，将结点将结点1212丢弃；丢弃；在在结点结点1313，从城市，从城市5 5到城市到城市4 4，目标函数值为，目标函数值为(1 1+3)+(3+6)+(+3)+(3+6)+(1 1+2 2)+()
38、+(3 3+4)+(+4)+(2 2+3 3)/2=14)/2=14，将结点，将结点1313加入表加入表PTPT中；中；（9 9）在表）在表PTPT中选取目标函数值极小的中选取目标函数值极小的结点结点1313优先进行搜索优先进行搜索；（1010）在）在结点结点1414，从城市，从城市4 4到城市到城市2 2，目标函数值为，目标函数值为(1 1+3)+(3+3)+(3+7 7)+()+(1 1+2 2)+()+(3 3+7 7)+()+(2 2+3 3)/2=16)/2=16，最后从城市，最后从城市2 2回到城回到城市市1 1，目标函数值为，目标函数值为(1 1+3 3)+()+(3 3+7 7
39、)+()+(1 1+2 2)+()+(3 3+7 7)+()+(2 2+3 3)/2=16)/2=16，由于结点由于结点1414为叶子结点，得到一个可行解，其路径长度为为叶子结点，得到一个可行解，其路径长度为1616；（1111）在表）在表PTPT中选取目标函数值极小的中选取目标函数值极小的结点结点1010优先进行搜索优先进行搜索；（1212）在）在结点结点1515，从城市，从城市4 4到城市到城市2 2，目标函数的值为，目标函数的值为(1 1+3)+(3+3)+(3+7 7)+()+(1 1+4 4)+()+(7 7+4 4)+(2+3)/2=18)+(2+3)/2=18，超出目标函数的界，
40、将，超出目标函数的界，将结点结点1515丢弃；丢弃；在在结点结点1616，从城市，从城市4 4到城市到城市5 5，目标函数值为，目标函数值为(1 1+3)+(3+6)+(+3)+(3+6)+(1 1+4 4)+()+(3 3+4 4)+(2+)+(2+3 3)/2=15)/2=15，将结点，将结点1616加入表加入表PTPT中；中；（1313）在表）在表PTPT中选取目标函数值极小的中选取目标函数值极小的结点结点1616优先进行搜索优先进行搜索；（1414）在）在结点结点1717，从城市，从城市5 5到城市到城市2 2，目标函数的值为，目标函数的值为(1 1+3)+(3+3)+(3+9 9)+
41、()+(1 1+4 4)+()+(3 3+4 4)+()+(9 9+3 3)/2=20)/2=20，超出目标函数的界，将，超出目标函数的界，将结点结点1717丢弃；丢弃；（1515）表）表PTPT中目标函数值均为中目标函数值均为1616，且有一个是，且有一个是叶子结点叶子结点1414，所以，所以，结点结点1414对应的解对应的解135421135421即是即是TSPTSP问题的最优解，搜索问题的最优解，搜索过程结束。过程结束。(g)扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421图图9.6 TSP问题最优解的确定问题最优解的确定(1,2)14 (1,3)14 (1,4)16
42、(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)16 (1,3,4)
43、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后的状态后的状态算法算法9.1TSP问题问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3for(i=1;i=1)5.1 i=k+1;5.2 xi=1;5.3
44、 while(xi=n)5.3.1 如果路径上顶点不重复，则如果路径上顶点不重复，则 5.3.1.1 根据式根据式9.2计算目标函数值计算目标函数值lb；5.3.1.2 if(lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短边段的最短边第第 应用分支限界法求解图应用分支限界法求解图9.79.7所示多段图的最短路径问题，所示多段图的最短路径问题，其搜索空间如图其搜索空间如图9.89.8所示，具体的搜索过程如下（加黑表示该所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：路径上已经确定的边）：（1 1）在根结点）在根结点1 1，根据限界函数计算目标函数的值为，
45、根据限界函数计算目标函数的值为1818；（2 2）在结点）在结点2 2，第，第1 1段选择边段选择边，目标函数值为，目标函数值为lb lb=4 4+8 8+5+3=20+5+3=20，超出目标函数的界，将结点，超出目标函数的界，将结点2 2丢弃；在结点丢弃；在结点3 3，第，第1 1段选择边段选择边，目标函数值为，目标函数值为lb lb=2 2+6 6+5+3=16+5+3=16，将结，将结点点3 3加入待处理结点表加入待处理结点表PTPT中；在结点中；在结点4 4，第，第1 1段选择边段选择边，目标函数值为目标函数值为lb lb=3 3+4 4+5+3=15+5+3=15，将结点，将结点4
46、4加入表加入表PTPT中；中；（3 3）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点4 4优先进行搜索；优先进行搜索；（4 4）在结点）在结点5 5，第，第2 2段选择边段选择边，目标函数值为，目标函数值为lb lb=3 3+4 4+6 6+3=16+3=16，将结点，将结点5 5加入表加入表PTPT中；在结点中；在结点6 6，第，第2 2段选择段选择边边，目标函数值为，目标函数值为lb lb=3 3+7 7+5 5+3=18+3=18，将结点，将结点6 6加入表加入表PTPT中；中；（5 5）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点3
47、3优先进行搜索；优先进行搜索；（6 6）在结点）在结点7 7，第，第2 2段选择边段选择边，目标函数值为，目标函数值为lb lb=2 2+6 6+5 5+3=16+3=16，将结点，将结点7 7加入表加入表PTPT中；在结点中；在结点8 8，第，第2 2段选择段选择边边，目标函数值为，目标函数值为lb lb=2+7+6+3=18=2+7+6+3=18，将结点，将结点8 8加入表加入表PTPT中；在结点中；在结点9 9，第，第2 2段选择边段选择边，目标函数值为，目标函数值为lb lb=2 2+8 8+5 5+3=18+3=18，将结点，将结点9 9加入表加入表PTPT中；中；（7 7）在表）在
48、表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点5 5优先进行搜索；优先进行搜索；（8 8）在结点）在结点1010，第，第3 3段选择边段选择边，可直接确定第，可直接确定第4 4段的边段的边，目标函数值为，目标函数值为lb lb=3 3+4 4+8 8+7 7=22=22，为一个可行解但超出，为一个可行解但超出目标函数的界，将其丢弃；在结点目标函数的界，将其丢弃；在结点1111，第，第3 3段选择边段选择边5,8，可直接确定第，可直接确定第4 4段的边段的边，目标函数值为，目标函数值为lb lb=3 3+4 4+6 6+3 3=16=16，为一个较好的可行解。由于结点，为一个较好
49、的可行解。由于结点1111是叶子结是叶子结点，并且其目标函数值是表点，并且其目标函数值是表PTPT中最小的，所以，结点中最小的，所以，结点1111代表代表的解即是问题的最优解，搜索过程结束。的解即是问题的最优解，搜索过程结束。6401lb=20231startlb=1802lb=1603lb=15图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)724lb=16825lb=18926lb=18535lb=1636lb=181110 57lb=2258lb=16 为了
50、在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表STST，在，在表表PTPT中取出最小值结点进行扩充时，将最小值结点存储到表中取出最小值结点进行扩充时，将最小值结点存储到表STST中，表中，表PTPT和表和表STST的数据结构为的数据结构为(第第i i段，段，lb)lb)，在搜索过程中表，在搜索过程中表PTPT和表和表STST的状态如下：的状态如下：(b)扩展结点扩展结点3后的状态后的状态(d)扩展结点扩展结点5后的状态，最优解为后的状态，最优解为03589图图9.9 多段图的最短路径问题最优解的确定多段图的最短路径问题最优解的确定(1,16)(1,15
