中国邮递员问题

(重定向自中国邮差问题

中国邮递员问题(也称路线检查问题,Route Inspection Problem)是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑,且此路徑需通過所有邊至少一次。现实意义中,中国邮递员问题就是在一個已知的地區,郵差要設法找到一條最短路徑,走過此地區所有的街道,且最後要回到出發點。

此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的,是P问题;而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出,而美國國家標準和技術研究院(NIST)的 Alan Goldman 首先將此問題命名为中国邮递员问题。[1]

无向图上中国邮递员问题的解法

若圖中有歐拉迴路,因為歐拉迴路通過所有的邊,因此任何一個歐拉迴路即為此問題的解。

若圖中不存在歐拉迴路,其中必存在有奇數個邊的端點,且這類的端點一定大於等于2個。因此有些邊需要再重覆一次,使奇數邊的端點變為偶數邊的端點。

 
用圖來模擬一個鎮的街道,標示紅色的路口有奇數條路通過。

假設有一個鎮有14條路及9個路口(路口分別編號為 1,2, …,9),其路和路口對應的圖(右邊第 1 圖,邊上的數字是各邊的 cost)中有4個端點(編號 1, 3, 6 及9)有奇數個邊通過,因此這個圖不存在歐拉迴路。後續要作的在圖中使幾個邊重覆,使圖中所有的端點均有偶數邊通過。例如若圖中 {1,3} 及 {6.9} 邊重覆,所有的端點均有偶數邊通過。不過增加的長度不一定最少。

 
所有奇數邊端點組成的 完全圖。

為了要確定重覆哪個邊可以使原圖的端點都有偶數邊通過,且增加長度最少。先畫出所有奇數邊的端點的完全圖   (右邊第 2 圖),邊上的數字是從一端點到另一端點(可以經過其他完全圖   中省略的點)的最短長度。若選擇邊 {1,6} 及 {3,9},所有端點都經過一次,而總長度  最短。

 
最後的解,紅色部份是新增的邊及其對應的長度。

因此原來的圖中,連接端點 1 和 6, 端點 3 和 9 的邊再重覆一次,所有端點均有偶數個邊通過(右邊第 3 圖)。因此任一個歐拉路徑即為此問題的解答,如以下的端點順序 (1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1) 即為一解。圖中紅色的部份即為重複的邊。

参考文献

  1. ^ "Chinese Postman Problem". [2009-02-19]. (原始内容存档于2008-10-17). 

參見

外部連結