TSM

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

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

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