Gab*_*llo 4 algorithm pseudocode traveling-salesman polynomial-approximations
我愿意实现一种算法，以最有效的方式（即最准确的结果 + 最少的时间）解决旅行商问题的二维欧几里得版本。在做我的研究时，我发现了很多算法，但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)。迄今为止，没有证据表明它可以被实施为实际有用的。鉴于此，我们提出了一种基于 Arora PTAS 基本步骤的欧几里得 TSP 的实现，并添加了一些启发式方法以提高运行时间。
作者没有提供指向其 C++ 实现的链接，但您可以尝试通过电子邮件发送给他们。他们论文中更重要的方面是他们对基于 Arora 的方法与 Concorde 求解器中提供的其他 4 种竞争算法进行了定量比较。他们的论文得出结论：
实验结果表明，Arora 的 PTAS 是切实可行的。表 I 和表 II 显示，尽管其性能良好，但似乎必须改进我们的方法以生成更多近似解。在大多数情况下，重要的理论结果会因实施决策而丢失。我们认为解决方案的质量与与数据结构相关的实现方面有关，以及需要提供更多关于游览必须使用哪些门户的提示。
如果您详细阅读他们的论文，您会看到他们做出了各种实施决策和优化，其中许多可能是次优的和/或没有严格证明的。自己阅读结果，但在我看来，他们的 PTAS 算法平均完成时间是其他算法的 0.25 倍到 1.0 倍，但结果有时要差得多。在我看来，这里最大的风险是“实施决策”和启发式方法，您可能需要反复试验才能真正实现那些难以捉摸的性能优势。