中國郵遞員問題是郵遞員在某一地區的信件投遞路程問題。郵遞員每天從郵局出發，走遍該地區所有街道再返回郵局，問題是他應如何安排送信的路線可以使所走的總路程最短。這個問題由中國學者管梅谷在1960年首先提出，並給出了解法——“奇偶點圖上作業法”，被國際上統稱為“中國郵遞員問題”。用圖論的語言描述，給定一個連通圖G，每邊e有非負權)，要求一條迴路經過每條邊至少一次，且滿足總權最小。
基本介紹
定義,圖論語言,TSP問題,
定義
一個郵遞員從郵局出發，要走完他所管轄範圍內的每一條街道，至少一次再返回郵局，如何選擇一條儘可能短的路線？這就是中國郵遞員問題（CPP），其命名是因為中國數學家管梅谷在1962年首先提出了這個問題。如果用頂點表示交叉路口，用邊表示街道，那么郵遞員所管轄的範圍可用一個賦權圖來表示，其中邊的權重表示對應街道的長度。
圖論語言
中國郵遞員問題可用圖論語言敘述為：在一個具有非負權的賦權連通圖G中，找出一條權最小的環遊。這種環遊稱為最優環遊。若G是歐拉圖，則G的任意歐拉環遊都是最優環遊，從而可利用弗勒里算法求解。若G不是歐拉圖，則G的任意一個環遊必定通過某些邊不止一次。將邊e的兩個端點再用一條權為w(e)的新邊連線時，稱邊e為重複的。此時CPP與下述問題等價，若G是給定的有非賦權的賦權連通圖，
（1）用添加重複邊的方法求G的一個歐拉賦權母圖
，使得
儘可能小；
（2）求 的歐拉環遊。
埃德蒙茲（J.Edmonds）和詹森（E.L.Johnson)在1973年給出了求解（1）的多項式時間算法。
如果郵遞員所通過的街道都是單向道，則對應的圖應為有向圖。1973年，埃德蒙茲和詹森證明此時CPP也有多項式時間算法。帕帕季米特裡屋（C.H.Papadimitrious）在1976年證明，如果既有雙向道，又有單向道，則CPP是NP困難的。
TSP問題
Traveling Salesman Problem，即旅行商問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值，這是一個NP難問題。
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士週遊問題，即對於西洋棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線形規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
