在图中查找哈密顿循环的动态规划算法是什么？
在无向图中查找哈密顿循环的动态规划算法是什么？ 我在某处看到存在一种时间复杂度为 O(n.2^n) 的算法。
What is dynamic programming algorithm for finding a Hamiltonian cycle in an undirected graph?
I have seen somewhere that there exists an algorithm with O(n.2^n) time complexity.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
确实存在一种用于查找哈密顿循环的 O(n2n) 动态规划算法。这个想法是一个通用的想法，可以将许多 O(n!) 回溯方法减少到 O(n22n) 或 O(n2n< /sup>）（以使用更多内存为代价），是考虑具有指定“端点”的子问题。
在这里，由于您想要一个循环，因此可以从任何顶点开始。因此修复一个，将其命名为
x。子问题是：“对于给定的集合S和S中的顶点v，是否存在从x< 开始的路径/code> 并遍历S的所有顶点，以v结束？”称之为poss[S][v]。与大多数动态规划问题一样，一旦定义了子问题，剩下的事情就很明显了：以任何“递增”顺序循环遍历所有 2n 组 S 的顶点，并且对于每个这样的 S 中的每个 v，您可以将 poss[S][v] 计算为：
最后，存在一个哈密顿环 iff 存在一个顶点
v使得边v->x存在且poss[S][ v]为 True，其中S是所有顶点的集合（x除外，具体取决于您的定义方式）。如果您想要实际的哈密顿循环而不是仅仅决定是否存在，请使 poss[S][v] 存储使其成为可能的实际
u而不仅仅是真或假；这样你就可以在最后追溯一条路径。There is indeed an O(n2n) dynamic-programming algorithm for finding Hamiltonian cycles. The idea, which is a general one that can reduce many O(n!) backtracking approaches to O(n22n) or O(n2n) (at the cost of using more memory), is to consider subproblems that are sets with specified "endpoints".
Here, since you want a cycle, you can start at any vertex. So fix one, call it
x. The subproblems would be: “For a given setSand a vertexvinS, is there a path starting atxand going through all the vertices ofS, ending atv?” Call this, say,poss[S][v].As with most dynamic programming problems, once you define the subproblems the rest is obvious: Loop over all the 2n sets S of vertices in any "increasing" order, and for each v in each such S, you can compute
poss[S][v]as:Finally, there is a Hamiltonian cycle iff there is a vertex
vsuch that an edgev->xexists andposs[S][v]is True, whereSis the set of all vertices (other thanx, depending on how you defined it).If you want the actual Hamiltonian cycle instead of just deciding whether one exists or not, make
poss[S][v]store the actualuthat made it possible instead of just True or False; that way you can trace back a path at the end.我无法找出该特定算法，但是 汉密尔顿页面比您可能需要的更多。 :)
(原始网址，当前为 404), (互联网档案)
I can't pluck out that particular algorithm, but there is more about Hamiltonian Cycles on The Hamiltonian Page than you will likely ever need. :)
(original URL, currently 404), (Internet Archive)