Euclidian TSP的PTAS實現？

Question

我願意以最有效的方式實現一個算法來解決2-dimensional Euclidian version of the Traveling Salesman Problem（即最準確的結果+最少的時間）。在做我的研究時，我發現了很多算法，但是Arora's 1998 paper及其presentation讓我覺得可能是最好的算法。還有其他版本的解決方案使用了相同的想法，例如2004年的Schultes。解決方案的問題是，它似乎難以置信地難以實現（如果不是不可能的話），並且我發現任何人都無法以可訪問的方式進行記錄儘管該論文首次發表已近20年。

對於這個問題，是否有任何現有的實施或至少一個指導方針？如果不是，那麼現有的和可實現的算法將盡可能地取代它，會是什麼？

Answer 1

當你說你是「準備就緒」來實現這一點時，我會帶你說你的話，但是有很好的理由你沒有找到源代碼。

除了複雜性之外，PTAS的一個實際問題是多項式的指數會隨着ε的收縮而急劇增加，例如如果運行時間是O（n（1 /ε）！）。這導致了更爲嚴格的要求，如EPTAS和FPTAS，但我不認爲TSP目前在這些更嚴格的要求下有解決方案。因此請記住，當您改變近似參數時，PTAS解決方案不一定能消除很大的變化性。

我在您的帖子中找到的最適用論文是An Empirical Analysis of Approximation Algorithms for Euclidean TSP。

Sanjeev Arora給出了一種創新的歐幾里得TSP 的多項式時間近似方案（PTAS）。迄今爲止，沒有證據表明它可以被實施爲實際有用的。在這個光 中，我們提出了基於Arora的PTAS的基本步驟的歐幾里得TSP的實現，其爲 並且增加了一些 啓發式來改進運行時間。

作者沒有提供到他們的C++實現的鏈接，但您可以嘗試給他們發送電子郵件。他們的論文的更重要的方面是他們對基於Arora的方法與Concorde求解器中提供的其他4種競爭算法進行的定量比較。他們的論文得出結論：

實驗結果表明，Arora的PTAS實際上是可行的。 表I和表II表明，儘管性能良好，但它似乎認爲我們的方法必須改進以生成更多近似 的解決方案。 在大多數情況下，由於實施決策，重大理論結果丟失 。我們認爲解決方案 的質量與鏈接到數據結構的實現方面以及 需要提供關於 遊覽必須使用哪些門戶的更多提示。

如果您詳細閱讀他們的論文，您會看到他們做出了各種實施決策和優化，其中許多實施決策和優化可能是次優的和/或沒有嚴格合理的。自己讀取結果，但在我看來，他們的PTAS算法的平均完成時間是其他算法的0.25倍到1.0倍，但結果有時會大大惡化。在我看來，這裏最大的風險就是「實施決策」和啓發式方法，你可能需要試驗和錯誤，希望能夠真正實現這些難以捉摸的性能優勢。