用演算法找出最省錢的路線

credit: 123RF

推銷員要走遍美國所有的主要城市，如果要求每個城市恰好訪問一次，然後返回總部，怎樣才能找到開銷最小的行程路線？這就是著名的旅行商問題，在規劃理論和數值計算科學裡一般縮寫為TSP(Travelling Salesman Problem)。現今學界普遍認為，TSP最優路線的演算法很有可能是不存在的(計算不可行的)。不過，好消息是計算機科學家早已發現了一條相當不錯的路線——開銷不超過理論最低成本的1.5倍的路線。

TSP假設在兩個城市之間旅行，不管從哪座城市出發，成本都是一樣的。但是真實情況並非如此。例如，也許從芝加哥飛往丹佛的航班比從丹佛飛往芝加哥的航班更便宜(或需要更少的時間)。在這些條件下找到最佳旅行路線——稱為不對稱TSP問題——顯然也是計算上不可行的。但是，與解決經典的TSP不同的是，研究人員尚不知道如何找到一條近乎最優的路線通過大量城市。或者準確地說，是直到上個月，三位計算機科學家宣布他們設計了一種在所有情況下仍然有效的近似演算法之前，尚不知道。

為什麼不對稱TSP如此艱難？簡而言之，當行程在一個方向比另一個方向更昂貴時，就有更多路線要考慮。增加難度意味著，到目前為止，用於解決不對稱TSP的所有演算法或用時過久或導致不可用的路徑。而新演算法「解決了這個長期存在的開放性問題，是第一階段的突破，」布法羅大學的George Regan和喬治亞理工大學的Dick Lipton在名為G?del』s Lost Letter and P=NP博客上寫到。這是一個專門發布當代演算法研究成果的技術性博客。

「我最開始思考這個問題是在我讀博的時候，2008年，」新文章的三位作者之一Ola Svensso說。與這個問題交手七年之後，Svensso轉而去解決了一個簡單點的問題，將一些城市集中在一起作為一個整體城市團，並且至少訪問整體團中的一個城市。找到了訪問所有城市團的最優路徑演算法。

然後Svensso招募了他後來的合作者Jakub Tarnawski和LászlóVégh，他們幫助他開發出一種嶄新的演算法，在一系列城市內反覆形成較小的子群組，直到確定每個群組內的最佳路線。然後使用Svensson以前的研究，將組內的路線拼接在一起，以構建完整的路線。雖然以前也有人在嘗試解決不對稱TSP時採用過類似的方法，但是他們都沒有成功地找到可以拼接到一起的低成本路線組。

雖然該論文尚未通過同行評審，但Regan認為，它有很大幾率通過計算機科學界的審查。「證明中的想法很清楚，」Regan說，「有潛在的敏感技術點……但非常紮實，很有前途，結構良好，是很好地突破。」

Svensso說，他和他的合作者計劃將其論文提交給即將舉行的第五十屆計算理論年度研討會，以便正式的接受同行評議。

本文譯自 quantamagazine.org，由譯者 majer 基於創作共用協議(BY-NC)發布。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！