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

中国邮递员问题的求解实例 前面已经讲过，对于欧拉图，可以直接用Fleury算法找出一条欧拉巡回路线；对于半欧拉图，可以先求出奇点u和v之间的最短路径P，令，则G *为欧拉图，然后用Fleury算法来确定一个G *的欧拉巡回，它就是G的最优巡回。 当G有2n个奇点（n1），可以用Edmonds算法解决，步骤如下： (1) 用Floyd算法求出所有奇点之间的最短路径和距离矩阵。 (2) 用匈牙利法或0-1规划法求出所有奇点之间的最佳配对。 (3) 在原图上添加最佳配对所包含的两两顶点之间的最短路得到欧拉图G *。 (4) 用Fleury算法确定一个G *的欧拉巡回，这就是G的最优巡回。 以上步骤的关键是找出2n个奇点的最佳配对，举例如下。 例 图3一条巡回。 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 [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