iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
自我挑戰組

30天不怕演算法:白話文版系列 第 26

Day 26:旅行推銷員問題(TSP)

之前在貪婪演算法的文章中有提到,現實生活中並不是所有問題都能用演算法快狠準地解決,有些困難的問題只有非常慢的解法。旅行推銷員問題(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。例如以任意城市為起點,接著不斷選擇距離最近的城市,直到去過所有的城市。這樣執行時間縮短很多,但也可以想像得出的解不會永遠正確。

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


上一篇
Day 25:動態規劃(dynamic programming)
下一篇
Day 27:碰到困難問題,演算法也救不了?
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言