中國郵遞員問題的匹配算法

汪海森，林 耿，卓彩娥 （閩江學(xué)院數(shù)學(xué)系，福建 福州 350108）

在20世紀(jì)60年代，著名數(shù)學(xué)家管梅谷先生[1]提出一個關(guān)于中國郵遞員的問題：一個郵遞員從郵局出發(fā)，到所管轄的街道投遞郵件，最后返回郵局，若必須走遍所轄各街道中每一條至少一次，怎樣選擇投遞路線使所走的路程最短？把該問題抽象成數(shù)學(xué)圖論問題，可以描述為：在一個賦權(quán)圖G＝（V，E）中，能否找到一條回路C，使C包含G的每條邊至少一次且C的長度最短？目前，學(xué)者們根據(jù)不同思想提出了許多求解中國郵遞員問題的算法。這些方法大致可以分成基于圖論方法[2－3]和基于智能搜索方法[4－5]2類。筆者提出了一種基于奇度頂點匹配的算法求解中國郵遞員問題。首先收縮圖中的偶點，形成一個由偶數(shù)個奇度頂點組成的新圖；然后應(yīng)用貪心方法找出圖的一個配對，加入這些配對點間的邊后，得到中國郵遞員問題的一個近似最優(yōu)的投遞方案。

1 預(yù)備知識

定義1[6]圖G的環(huán)游是指經(jīng)過圖G每條邊至少一次的閉途徑，歐拉回路是指經(jīng)過圖G每條邊恰好一次的環(huán)游。一個圖若包含歐拉回路，則這個圖稱為歐拉圖。

引理1[6]圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖，且G中沒有奇度頂點。

由引理1可知，如果G中沒有奇度頂點，則G是歐拉圖，那么歐拉回路就是最小的投遞路線。當(dāng)圖G中只有2個奇度頂點時，找出這2個點間的最短路徑并加入圖G中，此時圖為歐拉圖，且圖中的歐拉回路為最小投遞路線。當(dāng)圖G中的奇度頂點多于2個時，則奇度頂點的個數(shù)為偶數(shù)個。對這些奇度頂點進行配對，可以找出一條投遞路線。

定義2[7]設(shè)圖G＝（V，E），E′是E的子集，若E′中任何2條邊均不相鄰，則稱E′為G中的匹配。若在E′中再添加任意一條邊，所得集合都不是匹配了，則稱E′為極大匹配。邊數(shù)最多的匹配稱為最大匹配。

定義3[7]設(shè)M為圖G的一個匹配，若存在M中的邊以v為端點，則稱v是M-飽和點；否則稱v是M-不飽和點。若G中的每個節(jié)點都是M-飽和的，則稱M是完全匹配。

2 求解算法

當(dāng)圖G中包含多于2個奇度頂點時，通過如下方法對它們進行配對：首先，去掉原圖G中的偶度頂點，得到一個只包含原圖中奇度頂點的新圖G′。然后，初始化M＝?，從圖G′中的任意一個頂點出發(fā)，找到一條權(quán)最小的邊｛i，j｝，將該邊加入M，并將與頂點i，j關(guān)聯(lián)的邊從G′中刪除。重復(fù)以上步驟，直到找到一個完全匹配。基于以上分析，筆者提出求解中國郵遞員問題的匹配算法，具體算法描述如下：

Step 1 除去原圖G中的偶度頂點，那么，所得到的新圖G′只包含原奇度數(shù)結(jié)點與它們之間的路徑；初始化M＝?。

Step 2 從G′中任意一個頂點i出發(fā)，尋找與它相鄰的權(quán)為最小的邊｛i，j｝。如果邊｛i，j｝也是頂點j關(guān)聯(lián)的邊中權(quán)最小的邊，轉(zhuǎn)Step 3；否則，令i＝j(luò)，轉(zhuǎn)Step 2。

Step 3 令M＝M∪｛i，j｝并將與頂點i，j關(guān)聯(lián)的邊從G′中刪除。如果G′非空且連通，轉(zhuǎn)Step 2；如果G′不連通，則增加一條最短路，使得G′連通，轉(zhuǎn)Step 2；如果G′為空，轉(zhuǎn)Step 4。

Step 4 將M加入圖G后，所得圖為歐拉圖，歐拉回路為近似最小投遞路線。

3 實例分析

圖1 例1示意圖

圖2 預(yù)處理后的圖

例1 求如圖1所示的中國郵路問題。

解 （1）去掉如圖1中的偶度 數(shù) 結(jié) 點，即 V1，V3，V9，V11，V13得到新的圖，如圖2所示。

（2）從任意一點出發(fā)，假設(shè)從V2出發(fā)，由圖2可知以它為頂點的權(quán)最小的邊為｛V2，V6｝，而以V6為頂點的邊的權(quán)并沒有比邊｛V2，V6｝小，故邊｛V2，V6｝就是一個配對。去掉以V2，V6為頂點的關(guān)聯(lián)邊，再從其他點出發(fā)，可知以V4為頂點的權(quán)為最小的邊為｛V4，V8｝，以V5為頂點的權(quán)為最小的邊為｛V5，V12｝，以V7為頂點的權(quán)為最小的邊為｛V7，V10｝。即可得到如圖3所示的配對方法。

（3）根據(jù)配對原則，在原圖即圖1中添加重復(fù)邊，如圖4所示，經(jīng)檢驗，此配對方案最優(yōu)，所重復(fù)的邊的權(quán)之和為7。

圖3 配對情況

圖4 配對后的圖

4 結(jié) 語

提出了一種求解中國郵遞員問題的匹配算法。算法利用貪心方法快速找到原圖中奇度頂點的配對，將配對后的邊加入原圖得到一個歐拉圖，它的歐拉回路就是近似最小的投遞路線。該算法的復(fù)雜度較低，速度快，易于實現(xiàn)，且可以得到質(zhì)量較高的近似最優(yōu)解。

[1]管梅谷 .中國投遞員問題綜述 [J].數(shù)學(xué)研究與評論，1984，4（1）：113-119.

[2]李念祖 .關(guān)于中國郵遞員問題的最優(yōu)完全子圖算法 [J].上海師范大學(xué)學(xué)報，2006，35（4）：26-29.

[3]吳杰 .求解中國郵遞員問題的一中思路 [J].科技資訊，2007，14：211-211.

[4]李瑋，王雷 .中國郵遞員問題的DNA計算 [J].計算機應(yīng)用，2009，29（7）：1880-1883.

[5]于紅斌，薛占熬 .基于螞蟻算法的中國郵遞員問題 [J].河南師范大學(xué)學(xué)報，2011，39（5）：169-171.

[6]耿素云，屈婉玲，王捍平 .離散數(shù)學(xué)教程 [M].北京：北京大學(xué)出版社，2002.

[7]田豐，馬仲蕃 .圖與網(wǎng)絡(luò)流理論 [M].第2版 .北京：中國經(jīng)濟出版社，2000.