之前在貪婪演算法的文章中有提到，現實生活中並不是所有問題都能用演算法快狠準地解決，有些困難的問題只有非常慢的解法。旅行推銷員問題(travelling salesman problem)就是這樣的一個問題。

旅行推銷員問題是：給定一系列城市及任兩個城市間的距離，找出造訪每個城市一次並回到起始城市的最短路線。

最直接的解法就是把所有可能的路線都列出來，再比較哪一個路線是最短的。我們會發現：

兩個城市的路線數：2

三個城市的路線數：3個不同的起點 * 兩個城市的路線數 = 6

四個城市的路線數：4個不同的起點 * 三個城市的路線數 = 24

也就是以n個城市來說，會有n!條路線，找出其中的最短路線就需要O(n!)，即所謂階層時間(factorial time)。如果對大O符號的圖有印象的話，O(n!)的線正是最陡的那一條，代表執行時間隨著輸入n變大會急遽增加，光是十個城市，路線數就會增加到3628800。這樣的演算法已經不是慢可以形容，往往不是合理範圍的資源可以進行的方法。

除了暴力解法外，也可以嘗試用上一回提到的動態規劃。例如選定任一個城市為起點，從小範圍開始，計算並記錄起點與任一個城市的最小距離、任兩個城市的最小距離...這樣作法的執行時間為會是O(n²2^n)，雖然比階層時間快，仍然是指數時間(exponential time)，也就是隨著n增加執行時間會指數成長。

旅行推銷員問題是個NP困難問題，目前還沒有快速的演算法可以解決。這點可能有些令人好奇，畢竟這個問題看起來那麼簡單，而且還跟我們討論過的Dijkstra演算法或最小生成樹的問題非常相像。

事實上我們也可以像Dijkstra演算法一樣，用貪婪演算法來解TSP。例如以任意城市為起點，接著不斷選擇距離最近的城市，直到去過所有的城市。這樣執行時間縮短很多，但也可以想像得出的解不會永遠正確。

下一回會寫到所謂困難問題的意義，以及如何面對困難問題。