我愿意实现一种算法，以最有效的方式（即最准确的结果+最少的时间）解决二维欧几里得版本的旅行商问题。在进行研究时，我发现了很多算法，但Arora 1998 年的论文及其演讲让我觉得这可能是最好的。还有其他版本的解决方案使用相同的想法，例如Schultes在 2004 年提出的解决方案。问题是实现它似乎非常困难（如果不是不可能的话），我发现没有任何人以可访问的方式这样做的记录尽管这篇论文首次发表已经将近 20 年了。
是否有任何现有的实施或至少有这方面的指导方针？如果不是，什么是现有的和可实施的算法来尽可能地替代它？
当你说你“准备好”实现这个时，我会相信你的话，但是你没有找到源代码是有充分理由的。
除了复杂性之外，“PTAS 的一个实际问题是多项式的指数可能会随着 ε 的缩小而显着增加，例如，如果运行时间为 O(n(1/ε)！)。” 这导致了更严格的要求，例如 EPTAS 和 FPTAS，尽管我认为 TSP 目前没有针对这些更严格要求的解决方案。因此请记住，当您改变近似参数时，PTAS 解决方案不一定能消除广泛的可变性。
我在您的帖子中找到的最适用的论文是An Empirical Analysis of Approximation Algorithms for Euclidean TSP。
Sanjeev Arora 为欧几里得 TSP 提供了一种创新的多项式时间近似方案 (PTAS)。迄今为止，没有证据表明它可以实施为实际有用。有鉴于此，我们提出了一个欧几里得 TSP 的实现，它基于 Arora 的 PTAS 的基本步骤，并添加了一些启发式方法来提高运行时间。
作者没有提供指向他们的 C++ 实现的链接，但您可以尝试通过电子邮件发送给他们。他们论文中更重要的方面是他们对基于 Arora 的方法与 Concorde 求解器中提供的其他 4 种竞争算法进行了定量比较。他们的论文得出结论：
实验结果表明，Arora 的 PTAS 是切实可行的。表 I 和表 II 表明，尽管它的性能很好，但似乎我们的方法必须改进以生成更近似的解决方案。在大多数情况下，重要的理论结果会因实施决策而丢失。我们认为解决方案的质量与与数据结构相关的实施方面有关，并且需要提供更多关于游览必须使用哪些门户的提示。
如果您详细阅读他们的论文，您会看到他们做出了各种实施决策和优化，其中许多可能不是最佳的和/或没有严格合理的。自己阅读结果，但在我看来，他们的 PTAS 算法平均完成时间是其他算法的 0.25 到 1.0 倍，但结果有时会更差。在我看来，这里最大的风险是“实施决策”和启发式方法，您可能需要反复试验才能真正实现那些难以捉摸的性能优势。
我想它不再相关，但实际上提到的论文 Special Sauce 的作者在 GitHub 上发布了他们的代码：https ://github.com/barbaramartina/C---TSP-Arora-Implementation/tree/master/TSP_Implementation
但是，我也在寻找一个确切的实现，所以如果你实现了一些东西，如果你能在这里发布一个你的实现的链接，我将非常感激:)