TSM(旅行商問題(Travelling SalesMan problem))

TSM，即Traveling SalesMan problem，也就是旅行商問題，又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，也簡稱為TSM問題，是最基本的路線規劃問題，也是一個經典的NP-Hard問題。該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。最早的旅行商問題的數學規劃是由Dantzig（1959）等人提出。

基本介紹

• 中文名：旅行商問題、貨郎擔問題
• 外文名：TSM、TSP

TSM，即Traveling SaleMan problem，也就是旅行商問題，又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，也簡稱為TSM問題，是最基本的路線規劃問題，也是一個經典的NP-Hard問題。該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。最早的旅行商問題的數學規劃是由Dantzig（1959）等人提出。

最明顯的算法就是窮舉法，即尋找一切組合併取其最短。這種算法的排列數為n!(其中n為節點個數)。用動態規劃技術，我們可以在O(n^2·2^n)的時間內解決此問題。雖然這仍然是指數級的，但要比快得多。

它也有諸多的近似解法，例如最基本的模擬退火算法、貪心方法、遺傳算法、蟻群算法等等。