Travelling salesman problems

給定一個有 n個城市的集合，一些城市之間有路徑相連。推銷員問題(Travelling salesman problems)就是，一個推銷員要從其中某一個城市出發，唯一走遍所有的城市，再回到他出發的城市，求最短的路線。

以下是一個例子(圖中沒有標明路徑之間的確實數字)


圖片參考：http://mathworld.wolfram.com/images/eps-gif/TravelingSalesmanProblem_800.gif


推銷員問題可以追溯到十七世紀漢米爾頓循環（Hamiltonain Cycle） 的問題。

以一個有42個城市的推銷員問題為例，如果我們需要列舉所有的路徑才能確定何者最短，那麼總共會有 (42-1)!/2 = 1.67 * 1049 的可能方式。比較：全宇宙總共才有 1048 個粒子。

有了電腦的幫助，我們可以奇蹟似地解決遠比上面來得大的推銷員問題（世界記錄：米飯大學（Rice）的包柏‧比克司拜爾特（ Bob Bixbyet）等人用了50台接在一起的工作站解決了3038個城市的推銷員問題）。

在電腦的發展歷程中，就因為推銷員問題的簡單性和 NP-problem 的代表性 (Travelling salesman problems 是NP-hard problem)，推銷員問題總是做為新機器的鍊金石。