是否存在用于在图中找到哈密顿游动的多项式时间算法？

我的算法是N阶乘，而且速度很慢。

解决方案

NP已完成。但是，如果我们确实设法找到一种好的方法，请告诉我，我将向我们展示如何致富。

我们刚刚问了百万美元问题。寻找汉密尔顿路径是一个NP完全问题。可以使用动态编程在多项式时间内解决一些NP难问题，但是(据我所知)这不是其中之一。

很难找到最短的更好算法，因为这很困难。但是，我们可以尝试一些启发式方法，也许我们可​​能想参考这些内容；)。

为了减少复杂性，我们可以使用贪婪算法查找短暂步行。

通常，由于哈密顿路径问题(的决策版本)是NP完全的，因此我们不希望获得用于查找哈密顿路径的多项式时间算法。我们可以使用通常的N稍微加快速度！ N22N动态编程技巧(计算hp [v] [w] [S] ="是否存在具有端点v和w且其顶点为子集S的路径"，对于每个子集S以及其中的每两个顶点v和w使用DP)，但这仍然是指数级的。

但是，有许多特殊类型的图将始终存在哈密顿路径，并且可以轻松找到它们(请参阅Posa，Dirac，Ore等的工作)。

例如，以下内容是正确的：如果图的每个顶点的度数至少为n / 2，则图具有哈密顿路径。实际上，如果我们做得更聪明，则可以在O(n2)中找到一个，甚至可以在IIRC中找到O(n log n)。
[粗略的草图：首先，仅以"哈密顿"循环连接所有顶点，不要忘记边实际上是否在图中。现在，对于周期中实际上不在图中的每个边(v，w)，请考虑周期的其余部分：v ... w。当deg(v)+ deg(w)> = n时，列表中存在连续的x，y(按此顺序)，使得w是x的邻居，而v是y的邻居。 [证明：考虑{w的所有邻居的集合}和{v的邻居的列表中所有继承者的集合}；他们必须相交。]现在，将周期[v ... xy ... wv]更改为[vy ... wx ... v]，它至少减少了一个无效边，所以我们最多需要n次迭代以获得真正的哈密顿循环。这里有更多详细信息。]

顺便说一句：如果我们要查找的是仅包含一次每个边的遍历，则称为欧拉遍历，对于具有该遍历的图(奇数顶点的个数为0或者2)，可以很容易地在多项式中找到时间(快速)。

根据所使用的图形的生成方式，我们可以通过执行贪婪路径扩展然后在发生阻塞时进行随机边交换来针对随机实例获得预期的多项式时间。

这对于保证具有哈密顿游动的随机生成的相对稀疏图非常有效。

嗯..这取决于定义。哈密​​顿路径当然是NP完全的。但是，可以多次访问边和顶点的哈密尔顿步道(是的，只要在末尾添加步长，它仍称为哈密顿步道)可以用O(p ^ 2logp)或者O(max(c ^ 2plogp ，|| E |))，只要图满足Dirac首先推测并由Takamizawa证明的特定条件即可。参见Takamizawa(1980)"一种用于在图中找到短的封闭式跨步走的算法"。

保罗

我的查询：表明在图G中找到哈密顿环的搜索问题RHAM为
自我还原
如果搜索问题R对于决策问题是Cook可简化的，则它是可自简化的
SR = {x：R(x)？ }`