中国邮递员问题的求解实例.doc

中国邮递员问题的求解实例
前面已经讲过，对于欧拉图，可以直接用Fleury算法找出一条欧拉巡回路线；对于半欧拉图，可以先求出奇点u和v之间的最短路径P，令，则G *为欧拉图，然后用Fleury算法来确定一个G *的欧拉巡回，它就是G的最优巡回。
当G有2n个奇点（n>1），可以用Edmonds算法解决，步骤如下：
(1) 用Floyd算法求出所有奇点之间的最短路径和距离矩阵。
(2) 用匈牙利法或0-1规划法求出所有奇点之间的最佳配对。
(3) 在原图上添加最佳配对所包含的两两顶点之间的最短路得到欧拉图G *。
(4) 用Fleury算法确定一个G *的欧拉巡回，这就是G的最优巡回
以上步骤的关键是找出2n个奇点的最佳配对，举例如下。
例 图3是某区街道示意图，各边的长度数据如下表所示。现在需要对每条街道都巡视到（至少走一次），求一条总路程最短的巡回路线。
序号
顶点
顶点
边长
序号
顶点
顶点
边长
序号
顶点
顶点
边长
序号
顶点
顶点
边长
1
1
2
1026
17
11
17
163
33
23
24
432
49
30
31
342
2
1
4
402
18
8
9
289
34
23
28
198
50
31
32
648
3
2
3
1026
19
8
15
245
35
23
22
108
51
31
36
253
4
2
7
398
20
9
23
396
36
22
21
414
52
33
32
486
5
3
11
450
21
12
13
306
37
25
42
810
53
33
38
252
6
4
12
181
22
12
18
272
38
25
24
109
54
32
37
235
7
4
5
254
23
13
19
199
39
24
29
184
55

35
36
180
8
10
9
289
24
16
17
199
40
21
32
432
56
35
40
180
9
10
11
235
25
17
25
235
41
27
26
326
57
36
37
648
10
10
16
163
26
15
14
360
42
27
31
306
58
37
38
468
11
5
6
414
27
15
22
217
43
26
30
271
59
37
41
184
12
5
13
148
28

14
21
219
44
28
29
414
60
42
41
1063
13
6
20
382
29
19
20
344
45
28
33
235
61
40
41
792
14
6
7
253
30
19
18
332
46
29
34
181
62
40
39
198
15
7
8
252
31
18
26
144
47
34
33
418

16
7
14
219
32
20
21
308
48
30
39
432

解：该图有42个顶点和62条边，有26个顶点为奇点，因而不是欧拉图，为了寻找最优巡回，需要先求26个奇点的最佳配对。
先用Floyd算法求出所有42个顶点之间的最短路距离和路径。程序如下：
E=[1 2 1026
1 4 402
…………… 注：每一行代表一条边（两个顶点和边长），此处省略59行
40 39 198];
for i=1:42
for j=1:42
if j==i
a(i,j)=0;
else
a(i,j)=inf;
end
end
end
for k=1:62
i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)=E(k,3);
end

图3 某区街道示意图
[D,R]=floyd(a);
然后求26个奇点的最优配对，这可以用Lingo求解，编写程序如下：
MODEL:
SETS:
dot/2,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20,22,24,25,26,28,29,30,36,40,41/;
LINKS(dot,dot)| &2 GT # &1:C,X;
ENDSETS
DATA:
C=1319 1065 651 650 939 1228 1463 1500 1213 617 895 1590 1709 1377 1033 1112 1652 1761 1853 1418 1832 2124 2151 2479 1687
254 668 1173 1462 1751 198 181 402 1140 1418 2113 453 601 945 1635 2175 2284 597 1941 2355 868 1463 1498 2104
414 919 1208 1497 1732 435 148 886 1164 1859 679 347 691 1381 1921 2030 823 1687 2101 1094 1689 1724 1850
505 794 1083 1318 849 562 472 750 1445 1058 726 382 967 1507 1616 1202 1273 1687 1473 2005 2103 1541
289 578 813 1354 1067 471 245 940 1563 1231 887 462 1002 1111 1707 768 1182 1978 2005 2333 1541
289 524 1643 1356 760 534 651 1852 1520 1176 504 828 886 1996 594 1008 2267 2197 2525 1733
235 1932 1645 1049 823 362 2141 1809 1465 793 706 597 2285 883 890 2556 2486 2814 2022
2167 1880 1284 1058 163 2376 2044 1700 1028 507 398 2520 1105 691 2766 2658 2986 2194
306 1321 1599 2294 272 505 849 1571 2111 2220 416 1877 2291 687 1282 1317 2008
1034 1312 2007 531 199 543 1265 1805 1914 675 1571 1985 946 1541 1576 1702
360 1411 1203 871 527 577 1117 1226 1347 883 1297 1618 1534 1862 1070
1101 1563 1231 887 217 757 866 1707 523 937 1978 1894 2222 1430
2282 1950 1606 884 344 235 2426 942 528 2603 2495 2823 2031
332 676 1398 1938 2047 144 1704 2118 415 1010 1045 1824
344 1066 1606 1715 476 1372 1786 747 1342 1377 1503
722 1262 1371 820 1028 1442 1091 1623 1721 1159
540 649 1542 306 720 1813 1729 2057 1265
109 2082 598 184 2259 2151 2479 1687
2191 707 293 2368 2260 2588 1796
1848 2262 271 866 901 1680
414 1711 1603 1931 1139
2075 1967 2295 1503
595 630 1409
360 832
792;

图4 26个奇点的最优配对

ENDDATA
MIN=@SUM(LINKS:C*X);
@FOR(LINKS:@BIN(X));
@FOR(dot(I):@SUM(LINKS(J,K)| J #EQ# I #OR# K #EQ# I:X(J,K))=1);
END
运行以上程序，得到最优配对结果为：2与6、4与12、5与13、8与9、10与11、14与15、17与25、18与26、19与20、22与28、24与29、30与36、40与41。
在原图62条边的基础上增加13条边，得到如图4所示的图形，它有42个顶点和75条边，是欧拉图。对该图运行运行[eu,cEu]=arEuler(E)，其中输入参数E是75行2列矩阵（代表75条边），得到一条欧拉巡回如图5所示，总里程为25983。

图5 一条欧拉巡回
该巡回路线所经过的顶点序列为：1→2→3→11→10→9→8→7→2→（经过7）→6→5→4→12→13→5→13→19→20→6→7→14→15→8→9→23→24→25→17→11→10→16→17→25→42→41→37→32→21→14→15→22→23→28→29→24→29→34→33→28→(经过23)→22→21→20→19→18→26→27→31→30→39→40→41→40→35→36→31→32→33→38→37→36→（经过31）→30→26→18→12→4→1。

4