中國(guó)郵遞員問(wèn)題的求解實(shí)例

1、中國(guó)郵遞員問(wèn)題的求解實(shí)例前面已經(jīng)講過(guò)，對(duì)于歐拉圖，可以直接用Fleury算法找出一條歐拉巡回路線；對(duì)于半歐拉圖，可以先求出奇點(diǎn)u和v之間的最短路徑 P,令G =G P，貝U G *為歐拉圖，然后用Fleury算法來(lái)確定一個(gè) G *的歐拉巡回，它就是 G的最優(yōu)巡回。當(dāng)G有2n個(gè)奇點(diǎn)(n>1),可以用Edmonds算法解決，步驟如下：(1) 用Floyd算法求出所有奇點(diǎn)之間的最短路徑和距離矩陣。(2) 用匈牙利法或0-1規(guī)劃法求出所有奇點(diǎn)之間的最佳配對(duì)。(3) 在原圖上添加最佳配對(duì)所包含的兩兩頂點(diǎn)之間的最短路得到歐拉圖G *。用Fleury算法確定一個(gè) G *的歐拉巡回，這就是 G的最優(yōu)巡回

2、。以上步驟的關(guān)鍵是找出2n個(gè)奇點(diǎn)的最佳配對(duì)，舉例如下。例 圖3是某區(qū)街道示意圖，各邊的長(zhǎng)度數(shù)據(jù)如下表所示?，F(xiàn)在需要對(duì)每條街道 都巡視到(至少走一次)，求一條總路程最短的巡回路線。序號(hào)頂點(diǎn)頂點(diǎn)邊長(zhǎng)序號(hào)頂點(diǎn)頂點(diǎn)邊 長(zhǎng)序號(hào)頂點(diǎn)頂點(diǎn)邊長(zhǎng)序號(hào)頂點(diǎn)頂點(diǎn)邊長(zhǎng)1121026171117163332324432493031342214402188928934232819850313264832310261981524535232210851313625342739820923396362221414523332486531145021121330637254281053333825264121812212182

3、723825241095432372357452542313191993924291845535361808109289241617199402132432563540180910112352517252354127263265736376481010161632615143604227313065837384681156414271522217432630271593741184125131482814212194428294146042411063136203822919203444528332356140417921467253301918332462934181624039198157

4、825231182614447343341816714219322021308483039432解：該圖有42個(gè)頂點(diǎn)和62條邊，有26個(gè)頂點(diǎn)為奇點(diǎn)，因而不是歐拉圖，為了尋 找最優(yōu)巡回，需要先求 26個(gè)奇點(diǎn)的最佳配對(duì)。先用Floyd算法求出所有42個(gè)頂點(diǎn)之間的最短路距離和路徑。程序如下：E=12102614402 注：每一行代表一條邊(兩個(gè)頂點(diǎn)和邊長(zhǎng))，此處省略59行4039198;for i=1:42for j=1:42if j=ia(i,j)=0;elsea(i,j)=inf;endendendfor k=1:62 i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)

5、=E(k,3);endD,R=floyd(a);4U12°26"30 O353940510152420192223413*2721323136374128*3338仆2934O11 1742圖3某區(qū)街道示意圖然后求26個(gè)奇點(diǎn)的最優(yōu)配對(duì)，這可以用Lin go求解，編寫(xiě)程序如下:MODEL:SETS:3dot/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;ENDSETSDATA:C=1319 10

6、65 651 650 939 1228 1463 1500 1213 617 895 1590 1709 1377 10331112 1652 17611853 1418 1832 2124 2151 2479 1687254 668 1173 1462 1751 198 181 402 1140 1418 2113 453 601 945 1635 2175 2284 597 1941 23558681463 1498 2104414 919 1208 1497 1732 435 148 886 11641859 679 347 691 1381 19212030 823 1687 2101

7、 10941689 1724 1850505 794 1083 1318 849 562 472 750 1445 1058 726 382 967 1507 16161202 1273 1687 1473 200521031541289 578 813 1354 1067 471 245 940 1563 1231 887 462 1002 1111 1707 768 1182 1978 2005 2333 1541289 524 1643 1356 760 534 651 1852 1520 1176 504 828 886 1996 594 1008 2267 2197 2525 173

8、3235 1932 1645 1049 823 362 21411809 1465 793 706 597 2285 883 890 2556 2486 2814 20222167 1880 1284 1058 163 2376 2044 1700 1028 507 398 2520 1105 691 2766 2658 2986 2194306 1321 1599 2294 272 505 849 1571 2111 2220 416 18772291 687 1282 1317 20081034 1312 2007 531 199 543 1265 1805 1914 675 1571 1

9、985 946 1541 1576 1702360 1411 1203 871 527 577 1117 1226 1347 883 1297 1618 1534 1862 10701101 1563 1231 887 217 757 866 1707 523 937 1978 1894 2222 14302282 1950 1606 884 344 235 2426 942 528 2603 2495 2823 2031332 676 1398 1938 2047 144 1704 2118 415 1010 1045 1824344 1066 1606 1715 476 1372 1786

10、 747 1342 1377 1503722 1262 1371 820 1028 1442 1091 1623 1721 1159540 649 1542 306 720 1813 1729 2057 1265109 2082 598 184 2259 2151 2479 16872191 707 293 2368 2260 2588 17961848 2262 271 866 901 1680414 1711 1603 1931 11392075 1967 2295 1503595 630 1409360 832792;ENDDATA圖426個(gè)奇點(diǎn)的最優(yōu)配對(duì)MIN=SUM(LINKS:C

11、*X);FOR(LINKS:BIN(X);FOR(dot(l):SUM(LINKS(J,K)| J #EQ# I #OR# K #EQ# I:X(J,K)=1);END運(yùn)行以上程序，得到最優(yōu)配對(duì)結(jié)果為：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條邊的基礎(chǔ)上增加 13條邊，得到如圖4所示的圖形，它有 42個(gè)頂點(diǎn)和75條邊，是歐拉圖。對(duì)該圖運(yùn)行運(yùn)行eu,cEu=arEuler(E)，其中輸入?yún)?shù) E是75行2列矩陣(代表75條邊)，得到一條歐拉巡回如圖5所示，總里程為25983。該巡回路線所經(jīng)過(guò)的頂點(diǎn)序列為：1 23t|1 t|0T 8T 2宀(經(jīng)過(guò)7)6T54 12 13 V 13 19 20 T 7 14 1