zhōng guó yóu dì yuán wèn tí
中國郵遞員問題
用圖論的語言描述就是指在壹個邊賦權的圖中找壹個閉道，使得這個閉道經過每壹條邊，並且閉道上所有邊的權和最小。如果圖本身就是壹個歐拉圖，那麽這個閉道就是歐拉閉道。如果圖不是歐拉圖，那麽就有壹些邊可能會經過至少兩次。對於歐拉圖，找這樣壹個閉道的算法是由Fleury在1921年給出的，對於壹般圖的算法由Edmonds和Johnson在1973年給出。
此圖圖論中和中國郵遞員問題類似的是旅行商問題，區別於中國郵遞員問題，旅行商問題是說在邊賦權的完全圖中找壹個權和最小的哈密爾頓圈。
TSP問題（Traveling Salesman Problem），即旅行商問題，是數學領域中著名問題之壹。假設有壹個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪壹次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值，這是壹個NP難問題。
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格壹次且僅壹次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線形規劃這壹新方法的出現使得TSP成為壹個知名且流行的問題。