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倍，但结果有时会大大恶化。在我看来，这里最大的风险就是“实施决策”和启发式方法，你可能需要试验和错误，希望能够真正实现这些难以捉摸的性能优势。