欧几里德TSP的PTAS实现？

Question

我愿意实现一个算法来解决二维欧几里得旅行商问题，并以最有效的方式完成（即最准确的结果+最少的时间）。在研究过程中，我发现了许多算法，但Arora 1998年的论文及其演示可能是为此目的设计的最佳算法之一。还有其他使用相同思路的解决方案版本，例如Schultes在2004年的版本。问题是，尽管自从该论文首次发表以来已经将近20年，但似乎实现它非常困难（如果不是不可能的），我没有找到任何人以可访问的方式实现它的记录。

是否有现有的实现或至少有相关指南？如果没有，那么最好的替代算法是什么，可以实现并取得最佳效果？

- Gabriel Rebello

Answer 1

我会相信你说你已经“准备好”实现这个，但是你没有找到源代码的原因是有很好的理由。

除了复杂性之外，“PTAS的一个实际问题是随着ε的缩小，多项式的指数可能会急剧增加，例如如果运行时间为O(n(1/ε)! )”。这导致了更严格的要求，如EPTAS和FPTAS，尽管我不认为TSP目前在这些更严格的要求下有解决方案。因此，请记住，PTAS解决方案并不能消除您在变化逼近参数时所面临的广泛变异性。

我在您的帖子中发现最相关的论文是欧几里得TSP的近似算法的实证分析。

Sanjeev Arora提出了一种创新的多项式时间近似方案（PTAS）用于欧几里得TSP问题。迄今为止，没有证据表明它可以实际应用。因此，我们提出了一种基于Arora PTAS基本步骤并添加一些启发式算法以改进运行时间的欧几里得TSP实现。作者没有提供C++实现的链接，但您可以尝试给他们发送电子邮件。他们论文的更重要的方面是他们对基于Arora方法和Concorde求解器中提供的其他4个竞争算法进行的定量比较。他们的论文总结道：“实验结果表明，Arora的PTAS在实践中是可行的。表I和表II显示，尽管其性能良好，但我们的方法似乎必须改进以生成更多近似解。在大多数情况下，由于实现决策而失去了显著的理论结果。我们认为解决方案的质量与数据结构和需要提供有关哪些门户必须由旅游使用的提示等实现方面有关。”

如果你仔细阅读他们的论文，你会发现他们做出了许多实现决策和优化，其中许多可能是次优的和/或没有得到严格的证明。请自行阅读结果，但在我看来，他们的PTAS算法平均完成时间为其他算法的0.25倍至1.0倍，但有时结果会大幅度变差。在我看来，这里最大的风险是“实现决策”和启发式算法，你可能需要进行试错，以实现那些难以捉摸的性能优势。

- Special Sauce

---

我认为，他们没有实现PTAS版本。从论文的第2.2节中可以看出：“由于这个实际原因，我们决定将门户放置在这样的位置，以便最多只有一个门户与相邻的方块进行通信。” - Felix S

Answer 2

我猜这已经不再相关了，但是在论文“特殊酱料”中提到的作者实际上已经在GitHub上发布了他们的代码：https://github.com/barbaramartina/C---TSP-Arora-Implementation/tree/master/TSP_Implementation

然而，我也在寻找一个精确的实现，所以如果你实现了什么东西，我会非常感激如果你能在这里发布你的实现链接 :)

- Layla

---

欢迎来到Stack Overflow！虽然链接是分享知识的好方法，但如果它们在未来失效了，它们就不会真正回答问题。在您的答案中添加回答问题的链接的基本内容。如果内容过于复杂或太大而无法适应此处，请描述所提出解决方案的一般思路。请记住始终保留对原始解决方案网站的链接引用。请参见：如何撰写良好的答案？ - sɐunıɔןɐqɐp