一尘不染

在图中找到哈密顿循环的动态编程算法是什么?

algorithm

在无向图中寻找哈密顿循环的动态编程算法是什么?我在某处看到存在一种具有O(n.2^n)时间复杂性的算法。


阅读 268

收藏
2020-07-28

共1个答案

一尘不染

确实有一种O(n2 n)动态编程算法可以找到哈密顿循环。这个想法可以减少许多O(n!)回溯到O(n 2 2 n)或O(n2
n)(以使用更多内存为代价)的一般想法,它是考虑 设置 子问题 具有指定的“端点”

在这里,由于需要一个循环,因此可以从任何顶点开始。因此,修复一个,称之为x。子问题是:“对于一个给定S和顶点vS,是有一个路径开始x,并通过所有的顶点会S在结束v?”
称此为poss[S][v]

与大多数动态编程问题一样,一旦定义了子问题,其他问题就显而易见了:以任何“递增”顺序循环遍历所有2
n个顶点集S,对于每个这样的S中的每个v,您都可以计算poss[S][v]为:

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

最后,存在哈密顿循环,前提是存在一个顶点v,使得v->x存在边且该边poss[S][v]为True,S所有顶点的集合在哪里(除了x,取决于您如何定义它)。

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

2020-07-28