在图中找到哈密顿圈的动态规划算法是什么? [英] What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

问题描述

在无向图中寻找哈密顿圈的动态规划算法是什么?我在某处看到存在一种算法，其时间复杂度为 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.

推荐答案

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

There is indeed an O(n2ⁿ) dynamic-programming algorithm for finding Hamiltonian cycles. The idea, which is a general one that can reduce many O(n!) backtracking approaches to O(n²2ⁿ) or O(n2ⁿ) (at the cost of using more memory), is to consider subproblems that are sets with specified "endpoints".

这里，既然你想要一个循环，你可以从任何顶点开始.所以修复一个，称之为x.子问题将是:对于给定的集合 S 和 S 中的顶点 v，是否存在从 x<开始的路径?/code> 并遍历 S 的所有顶点，以 v 结尾?"称其为 poss[S][v].

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 set S and a vertex v in S, is there a path starting at x and going through all the vertices of S, ending at v?" Call this, say, poss[S][v].

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

As with most dynamic programming problems, once you define the subproblems the rest is obvious: Loop over all the 2ⁿ sets S of vertices in any "increasing" order, and for each v in each such S, you can compute poss[S][v] as:

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

poss[S][v] = (there exists some u in S such that poss[S−{v}][u] is True and an edge u->v exists)

最后，存在一个哈密顿循环，当条件是顶点v使得边v->x存在并且poss[S][v] 为 True，其中 S 是所有顶点的集合(除了 x，取决于你如何定义它).

Finally, there is a Hamiltonian cycle iff there is a vertex v such that an edge v->x exists and poss[S][v] is True, where S is the set of all vertices (other than x, depending on how you defined it).

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

If you want the actual Hamiltonian cycle instead of just deciding whether one exists or not, make poss[S][v] store the actual u that made it possible instead of just True or False; that way you can trace back a path at the end.

这篇关于在图中找到哈密顿圈的动态规划算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！