algorithm - 在图中找到哈密顿圈的动态规划算法是什么？

Question

什么是在无向图中找到哈密顿圈的动态规划算法？我在某处看到存在具有O(n.2^n)时间复杂度的算法。

Answer 1

确实有一个 O(n2 ⁿ ) 动态规划算法来寻找哈密顿循环。这个想法是一个通用的想法，可以将许多 O(n!) 回溯方法减少到 O(n ² 2 ⁿ ) 或 O(n2 ⁿ )（以使用更多内存为代价），它是考虑作为集合的子问题具有指定的“端点”。

在这里，既然你想要一个循环，你可以从任何顶点开始。所以修复一个，调用它x。子问题将是：“对于给定的集合S和 中的一个顶点v，S是否有一条路径从 开始x并经过 的所有顶点S，结束于v？” 称这个，说，poss[S][v]。

与大多数动态规划问题一样，一旦定义了子问题，剩下的就很明显了：以任何“递增”顺序循环遍历所有 2 ⁿ个顶点集合 S，并且对于每个这样的 S 中的每个 v，您可以计算poss[S][v]为：

poss[S][v] = (S 中存在一些u使得 poss[S−{v}][u] 为 True 并且u->v存在一条边)

最后，有一个哈密顿循环当且仅当存在v一个边v->x存在且poss[S][v]为真的S顶点时，所有顶点的集合在哪里（除了x，取决于您如何定义它）。

如果您想要实际的哈密顿循环，而不是仅仅决定是否存在，请存储使之成为可能poss[S][v]的实际值，而不仅仅是 True 或 False；u这样你就可以在最后追溯一条路径。

Answer 2

我无法挑选出那个特定的算法，但在哈密尔顿页面上关于哈密顿循环的内容比你可能需要的要多。:)

本页旨在成为 Internet 上有关哈密顿循环和哈密顿路径问题以及一些相关问题的论文、源代码、预印本、技术报告等的综合列表。

（原始网址，目前为 404），（互联网档案馆）