什么是动态的规划算法找到汉密尔顿循环中的一个图？

Question

什么是动态的规划算法找到汉密尔顿循环中的一个无向图?我已经看到的地方，存在的一个算法 O(n.2^n) 时间的复杂性。

Answer 1

有确实是O（N 2 ^名词）动态编程查找哈密顿循环算法。的想法，这是一般的一个，可以减少许多为O（n！）回溯接近为O（n ² 2 ^名词）或O（N 2 ^名词）（在使用多个存储器的成本），是考虑子问题是集与指定的“端点”

在这里，因为你想有一个周期，你可以在任何顶点开始。因此修复一个，把它x。子问题是：“？对于一个给定S和v顶点S，有一个路径开始x并通过S的所有顶点会在v结束”叫这个，比方说，poss[S][v]

与大多数动态规划问题，一旦定义了子问题的其余部分是显而易见的：遍历所有的2 ^名词集S IN任何“增加”命令的顶点，并且在每个每个V这样S，就可以计算poss[S][v]为：

  

POSS [S] [V] =（存在S中一些u使得POSS [S- {V}] [U]为真和边缘u->v存在）

最后，还有一个汉密尔顿的周期当且仅当有一个顶点v使得边缘v->x存在且poss[S][v]为True，其中S是该组的所有顶点的（比x其他，这取决于你如何定义的话）。

如果你想实际汉密尔顿的周期，而不是仅仅决定一个人是否存在与否，化妆poss[S][v]店实际u使得有可能的，而不是只是真或假;这样你可以追溯在末端的路径。

Answer 2

我不能拔出，具体算法，但是有更多关于汉密尔顿循环上 汉密尔顿网页 比你将有可能在任何时候需要。:)

这页的打算是 综合清单的文件， 源代码，预印本，技术 报告等，可在 互联网有关的汉密尔顿循环 和汉密尔顿路的问题 作为一些相关的问题。

(原来的网址，目前404), (互联网上的档案)