文档介绍：(Ⅲ)
图论
1
旅行商问题
1. 旅行商问题: 对正权完全图G,求G总长最短的H回路。
(区别Euler回路与H回路)
2. 求解算法:分支定界法
分支定界法是一种用较好方式搜索的准枚举法,实质上就是按字典序枚举所有可能情形并结合剪枝(过滤)的办法。
例由A,B,C,D,E中的三个不同字母构成的全部字符串,按字典序的排列:
ABC,ABD,ABE,ACD,ACE,ADE,BCD,BDE,CDE
2
3. 分支定界法
初始阶段:1. 将全部边按权由小到大排列;
2. 取前n边作为S,置d0:=∞。
(d0为已考察的H回路中最短的路长)
迭代阶段:3. 若S构成H回路且其路长d(S)<d0,则d0:= d(S)。跳过比当前d0差的后续情形后, 用剩下未考察的第一组边作为S,返回3。
全部情形考察完毕时的d0即为最短H回路长度,取其值的那个S就是问题的解。
(将一条边看作一个字符,步骤1已得各字符间的先后关系。对于长为n且各字符互异的所有字符串,本算法要按字典序的顺序逐一考察每一字符串)
3
1) 边按权排序(由小到大), d0:=∞
边: a35 a24 a15 a14 a12 a13 a34 a23 a45 a25
权: 3 4 4 9 10 10 11 13 16 20
1
4
2
3
5
4
10
13
11
16
9
10
20
4
3
例
4
边: a35 a24 a15 a14 a12 a13 a34 a23 a45 a25
权: 3 4 4 9 10 10 11 13 16 20
分支定界:
S1: a35 a24 a15 a14 a12 , 非H回路,d(S1)=30;
S2: a35 a24 a15 a14 a13 , 非H回路,d(S2)= 30;
S3: a35 a24 a15 a14 a34 , 非H回路,d(S3)=31 ;
S4: a35 a24 a15 a14 a23 , H回路, d0:= 33;
S5: a35 a24 a15 a12 a13 , 非H回路,d(S5)=31;
S6: a35 a24 a15 a12 a34 , H回路,d(S6)=32, d0:= 32;
S7: a35 a24 a15 a13 a34 , 非H回路,d(S6)=32;
S8: a35 a24 a14 a12 a13 , 非H回路,d(S6)=36;
继续下去所得组长度会比S8差,故可终止计算。
5
故最优解为S6 ,其长度为32。
计算要掌握两个要点:
1. 按字典序逐一考察各边集;
2. 每次考察完一个边集后,应考虑是否可以用过滤条件(当前d0值)跳过一些不必要情形的考察,因为比当前d0值差的情形不需考虑。
6
4. 近似算法--“便宜”算法
分支定界法虽可求得旅行售货员问题的准确最优解,但计算复杂度为O(n!),故对大型问题需寻找近似算法求解。
需采用近似算法往往需要增加一些限制,以便能够提高计算速度和近似程度:
(1) G是无向正权图。
(2) 对图中任意的三点构成的三角形,其中任何两边之和大于第三边。
7
求解思路:给v1一个自环,得到第一个回路。以后反复执行以下过程:寻找与已得回路距离最近的点,将之插入到回路中;回路以外无结点时终止。
j
t1
t
t2
插入办法:设待插入点为j, 有两种选择: (1) 加入(j,t1)和(j,t)、删除(t,t1); (2) 加入(j,t2)和(j,t)、删除(t,t2).
选使回路长度增加量小的那种办法作插入。
8
例
(1)
t1
0
(2)
找出回路外到v1最近的点(在第一行找)v2 ,插入回路:
v2
v1
18
18
(3)
找出到v1 ,v2最近的点(第1,2行去掉第1,2列后,在此范围找)v5 ,插入回路:
v5
v2
v1
27
18
19
9
(4)
找出到v1 ,v2 ,v5最近的点(第1,2,5行去掉第1,2,5列后,在此范围找)v4 ,插入回路:
v2
v1
v5
v4
18
24
27
21
(5)
找出到v1 ,v2 ,v5 ,v4最近的点(第1,2,4,5行去掉第1,2,4,5列后,在此范围找)v3 ,插入回路:
17
v4
24
v2
v1
v5
v3
18
27
23
10