1 2 3 4 5 6 7 8 9 10 11 12 Contents
推銷員的旅程問題（Traveling Salesperson Problem, TSP）就是一個哈米爾頓圖的經典應用問題：推銷員得去拜訪每一個客戶，為了節省時間和車資，他當然希望能先規劃出最經濟的路程。一般而言，最短的路程通常也是最經濟的路程。推銷員的旅程問題的變化形式很多，例如：
．迴路設計
．行車路線安排——油罐車到各個加油站巡迴加油
．工作安排——旅行團替觀光客們規劃行程
這個問題，以下簡稱TSP，是個十分困難的問題，於1934年由數學家Whitney提出，直到1954年才有突破，Dontzig, Fulkerson及 Johnson三位數學家針對美國的49個重要城市的圖形，提出了一個幾近完美的答案。到了1980年，有了更大的突破，Crowder及 Padborg對於美國的318個重要城市的圖形，提出了一個幾近完美的答案；而且他們只花了6分鐘左右。以一個318點的完全圖而言，固定起點一共有317! 個不同的哈米爾頓迴圈。若是以苦力方式，把所有可能的路線都比較一次，即使每秒鐘能完成10億條路線的計算，也得花上10639年哩！
然而解決此類問題最直覺的方法就是最近點法（Nearest Neighborhood Algorithm） ——選擇最近但尚未去過的地點。
讓我們用下面的例子來說明：
小智是個推銷員，他經手各式各樣的書籍。這天他來到新竹，選定了幾個地點，要在那附近拜訪客戶。地圖中的數字為兩地之間的路程，如果他由火車站出發，並且最後回到火車站的話，最短的公里數是多少？
此方法是先前往離起點「火車站」最近的地點 ——也就是「省立新竹醫院」，然後再看看剩下的地點中，最靠近省立新竹醫院的為何，就選定該地為下一站，以此類推…
起點：火車站
最靠近「火車站」的地點 —— 省立新竹醫院
最靠近「省立新竹醫院」的地點 —— 交大
最靠近「交大」的地點 —— 世界工商
最靠近「世界工商」的地點 —— 青草湖因此我們得到這樣的路徑：
火車站→省立新竹醫院→交大→世界工商→青草湖→火車站。
如此，我們得到總路程為2 + 4 + 3 + 8 + 6 = 23公里。這是最短的路徑嗎？
從火車站出發通過上述地點各一次的迴圈一共有24種（從火車站出發時有條路可選，下一站則有3條路可選，再下一站則有2條路可選，之後只能回到起點別無選擇。）有興趣計算這24條路徑的長度嗎？請加油！
但是若小智是由省立新竹醫院出發，利用這種方法找出來的路徑卻是25公里，如下：
我們發現：不過是選擇不同的起點，利用同樣的方法卻找到不同的路徑。由此可見這個方法並不保證能夠找到所謂的最短路徑；然而不可否認地，這的確提供了一個不太壞的走法。你可以自行試試看，選哪一地為起點可以得到最短的路徑。
數學家們曾耗費許多心思在解這個問題上，但到目前為止尚未成功。現在可以確定的是在最短的路徑中，各個路線彼此不可交錯。每次他們找到了一個方法，卻發現只要經過的地點增加，這個方法就又不適用了。
