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

2013-09-26 03:26:24汪海森卓彩娥閩江學院數學系福建福州350108

長江大學學報(自科版) 2013年25期

汪海森，林耿，卓彩娥（閩江學院數學系，福建福州 350108）

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

1 預備知識

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

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

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

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

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

2 求解算法

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

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

Step 2 從G′中任意一個頂點i出發，尋找與它相鄰的權為最小的邊｛i，j｝。如果邊｛i，j｝也是頂點j關聯的邊中權最小的邊，轉Step 3；否則，令i＝j，轉Step 2。

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

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

3 實例分析

圖1 例1示意圖

圖2 預處理后的圖

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

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

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

（3）根據配對原則，在原圖即圖1中添加重復邊，如圖4所示，經檢驗，此配對方案最優，所重復的邊的權之和為7。