欧几里德 TSP 的 PTAS 实施？
PTAS implementation for Euclidian TSP?
我愿意在 2004 年实施一种算法来解决 2-dimensional Euclidian version of the Traveling Salesman Problem in the most efficient way (i.e. most accurate result + least time). While doing my research I found plenty of algorithms but Arora's 1998 paper and its presentation struck me as maybe the best ones for that purpose. There are other versions of the solution using the same idea such as the one by Schultes。问题是实施它似乎非常困难（如果不是不可能的话），而且我没有发现任何人这样做的记录以一种易于访问的方式，即使自该论文首次发表以来已经将近 20 年了。
是否有任何现有的实施或至少有相关指南？如果不是，现有且可实施的算法是什么来尽可能地替代它？
当你说你是 "ready" 来实现这个时，我会相信你的话，但是你有充分的理由找不到源代码.
除了复杂性之外，"practical problem with PTAS is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O(n(1/ε)!)." 这会导致更严格的要求，例如 EPTAS 和 FPTAS，尽管我认为 TSP 目前没有满足这些更严格要求的解决方案。因此请记住，当您改变近似参数时，PTAS 解决方案不一定会消除广泛的可变性。
我发现最适合您 post 的论文是 An Empirical Analysis of Approximation Algorithms for Euclidean TSP 。
An innovative Polynomial-Time Approximation Scheme (PTAS) for the
Euclidean TSP was given by Sanjeev Arora. To date, there is no
evidence that it can be implemented to be practically useful. In light
of this, we propose an implementation of the Euclidean TSP that is
based on the essential steps of the Arora’s PTAS and adds some
heuristics to improve the running time.
作者没有为他们的 C++ 实现提供 link，但您可以尝试通过电子邮件发送给他们。他们论文中更重要的方面是他们对基于 Arora 的方法与 Concorde 求解器中提供的 4 种其他竞争算法进行了定量比较。他们的论文得出结论：
Experimental results show that Arora´s PTAS is practically feasible.
Table I and Table II show that in spite of its good performance, it
seems that our approach must be improved to generate more approximate
solutions. In most cases the significant theoretical results are lost
due to implementation decisions. We think the quality of the solutions
had to do with implementation aspects linked to data structures and
the need to give more hints about which portals must be used by the
tour.
如果您详细阅读他们的论文，您会看到他们做出了各种实施决策和优化，其中许多可能是次优的 and/or 没有严格的理由。自己阅读结果，但在我看来，他们的 PTAS 算法平均完成时间是其他算法的 0.25 倍到 1.0 倍，但有时结果要差得多。在我看来，这里最大的风险是 "implementation decisions" 和您可能需要反复试验的启发式方法，以期真正实现那些难以捉摸的性能优势。
我猜它不再相关，但实际上提到的 Special Sauce 论文的作者在 GitHub 上发布了他们的代码：https://github.com/barbaramartina/C---TSP-Arora-Implementation/tree/master/TSP_Implementation
但是，我也在寻找一个确切的实现，所以如果你实现了一些东西，如果你能 post 一个 link 到你的实现，我将非常感激 :)
我愿意在 2004 年实施一种算法来解决 2-dimensional Euclidian version of the Traveling Salesman Problem in the most efficient way (i.e. most accurate result + least time). While doing my research I found plenty of algorithms but Arora's 1998 paper and its presentation struck me as maybe the best ones for that purpose. There are other versions of the solution using the same idea such as the one by Schultes。问题是实施它似乎非常困难（如果不是不可能的话），而且我没有发现任何人这样做的记录以一种易于访问的方式，即使自该论文首次发表以来已经将近 20 年了。
是否有任何现有的实施或至少有相关指南？如果不是，现有且可实施的算法是什么来尽可能地替代它？
当你说你是 "ready" 来实现这个时，我会相信你的话，但是你有充分的理由找不到源代码.
除了复杂性之外，"practical problem with PTAS is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O(n(1/ε)!)." 这会导致更严格的要求，例如 EPTAS 和 FPTAS，尽管我认为 TSP 目前没有满足这些更严格要求的解决方案。因此请记住，当您改变近似参数时，PTAS 解决方案不一定会消除广泛的可变性。
我发现最适合您 post 的论文是 An Empirical Analysis of Approximation Algorithms for Euclidean TSP 。
An innovative Polynomial-Time Approximation Scheme (PTAS) for the Euclidean TSP was given by Sanjeev Arora. To date, there is no evidence that it can be implemented to be practically useful. In light of this, we propose an implementation of the Euclidean TSP that is based on the essential steps of the Arora’s PTAS and adds some heuristics to improve the running time.
作者没有为他们的 C++ 实现提供 link，但您可以尝试通过电子邮件发送给他们。他们论文中更重要的方面是他们对基于 Arora 的方法与 Concorde 求解器中提供的 4 种其他竞争算法进行了定量比较。他们的论文得出结论：
Experimental results show that Arora´s PTAS is practically feasible. Table I and Table II show that in spite of its good performance, it seems that our approach must be improved to generate more approximate solutions. In most cases the significant theoretical results are lost due to implementation decisions. We think the quality of the solutions had to do with implementation aspects linked to data structures and the need to give more hints about which portals must be used by the tour.
如果您详细阅读他们的论文，您会看到他们做出了各种实施决策和优化，其中许多可能是次优的 and/or 没有严格的理由。自己阅读结果，但在我看来，他们的 PTAS 算法平均完成时间是其他算法的 0.25 倍到 1.0 倍，但有时结果要差得多。在我看来，这里最大的风险是 "implementation decisions" 和您可能需要反复试验的启发式方法，以期真正实现那些难以捉摸的性能优势。
我猜它不再相关，但实际上提到的 Special Sauce 论文的作者在 GitHub 上发布了他们的代码：https://github.com/barbaramartina/C---TSP-Arora-Implementation/tree/master/TSP_Implementation
但是，我也在寻找一个确切的实现，所以如果你实现了一些东西，如果你能 post 一个 link 到你的实现，我将非常感激 :)