哈密顿路径算法

Question

我有一个项目，需要使用两种不同的算法在无向无权图中查找哈密顿路径。我已经实现了一种基于回溯的启发式算法，但是我一直在寻找另一种算法，但是找不到。

所以我的问题是，除了使用回溯之外，你知道哪种算法可以找到哈密顿路径？

编辑：在查看了几篇其他帖子后，我发现我们可以使用最长路径算法找到哈密顿路径，并检查路径长度是否等于顶点数-1。我想知道这是否正确。

提前感谢。

- qbisson

Answer 1

由于哈密顿路径是NP完全问题，你可能最终会使用某种形式的回溯。无论你使用堆栈还是穷举枚举来实现指数级爆炸，都取决于你自己。

如果你在寻找公式，可以看看各种TSP算法（我不太了解哈密顿路径技术）。请注意，任何利用三角不等式的算法都不适用，因为你的权重实际上都是1和无穷大（边不存在）。

寻找不需要三角不等式的分支定界TSP公式。分支定界似乎是TSP可证明最优解的技术的最新进展。

使用最小生成树的分支限界可能很好（易于实现），并且您可以通过迭代方式（在分支之间）用节点权重增强最小生成树，以将度数>2的节点分解为度数为2的节点而不改变结果的正确性。我记不得这个技术的名字了（我正在工作，所以不能查阅）。但是，您的MST的新距离度量应该是：

cost[i,j] = (exists(i,j) ? 1 : infinity) + node_augmentation[i] + node_augmentation[j].

更好的收敛规则有点复杂（如果degree[i]>2，则增加；如果degree[i]<2，则减少），但是我再也想不起来那篇论文了（我认为它可能是Held-Karp，但我可能完全错了）。

对于糟糕的答案我很抱歉，但我希望这可以帮助你寻找方法。由于我不太了解TSP技术如何适用于哈密顿路径技术，所以我可能没有什么帮助。

- ccoakley