avd*_*avd 19 algorithm graph cycle dynamic-programming hamiltonian-cycle
什么是在无向图中找到哈密顿循环的动态规划算法？我在某处看到存在一种具有O(n.2^n)时间复杂度的算法.
Shr*_*saR 33
确实存在用于发现哈密顿循环的O(n2 n)动态编程算法.这个想法是一个普遍的想法,可以减少许多O(n!)回溯方法到O(n 2 2 n)或O(n2 n)(以使用更多内存为代价),是考虑集合的子问题使用指定的"端点".
在这里,既然你想要一个循环,你可以从任何顶点开始.所以修一个,打电话给它x.子问题是:"对于一个给定S和顶点v的S,是有开始的路径x,并通过所有的顶点会S在结束v？"调用该方法,比如,poss[S][v].
与大多数动态规划的问题,一旦你定义的子问题,其余是显而易见的:遍历所有的2个Ñ任何"增加"为了顶点集S,并在每个这样的S中的每个V,可以计算poss[S][v]为:
poss [S] [v] =(
u在S中存在一些,使得[S- {v}] [u]为True并且u->v存在边缘)
最后,如果有一个顶点v使得边v->x存在并且poss[S][v]为True,S则存在哈密顿循环,其中是所有顶点的集合(除了x,取决于您如何定义它).
如果你想要实际的汉密尔顿循环而不仅仅是决定一个是否存在,那么poss[S][v]将实际存储变为u可能而不仅仅是真或假; 这样你就可以追溯到最后的路径了.