是否存在一种多项式时间的算法来找到图中的哈密顿路径？
我的算法的时间复杂度是阶乘级别的，非常慢。
在图中寻找哈密顿路径的多项式时间算法
5
- Nat
1
我知道寻找哈密顿路径是一个NP完全问题。那么寻找哈密顿回路是一样的问题吗？或者已经被解决了吗？ - wizlog
7个回答
21
通常情况下，由于（汉密尔顿路径问题的决策版本）是NP完全的，你不能指望得到一个多项式时间复杂度的算法来找出汉密尔顿路径。你可以通过通常的N! → N22N动态规划技巧略微加速它（使用DP计算hp[v][w][S] =“是否存在一条以S为子集且端点为v和w的路径”对于每个子集S和其中的任意两个点v和w），但这仍然是指数级别的。
然而，有许多特殊类型的图形，汉密尔顿路径将始终存在，并且它们可以轻松找到（参见Posa、Dirac、Ore等人的工作）。
例如，以下语句为真：如果图的每个顶点的度数至少为n/2，则该图具有汉密尔顿路径。 事实上，您可以在O(n2)时间内甚至更聪明地做到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次迭代才能获得真正的汉密尔顿循环。 更多细节请参见这里。]
然而，有许多特殊类型的图形，汉密尔顿路径将始终存在，并且它们可以轻松找到（参见Posa、Dirac、Ore等人的工作）。
例如，以下语句为真：如果图的每个顶点的度数至少为n/2，则该图具有汉密尔顿路径。 事实上，您可以在O(n2)时间内甚至更聪明地做到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次迭代才能获得真正的汉密尔顿循环。 更多细节请参见这里。]
顺便说一下，如果你想要的只是一条走过每个边仅一次的路径，那么这就叫做Eulerian walk。对于满足条件的图（奇数度顶点的数量为0或2），可以很容易地在多项式时间内（快速地）找到一条。
- ShreevatsaR
17
你刚刚提出了百万美元的问题。找到一个哈密顿路径是一个NP完全问题。有些NP难题可以使用动态规划在多项式时间内解决，但据我所知，这不是其中之一。
- Daniel Spiewak
6
NP-hard问题尚未在多项式时间内得到解决，这仍然是一个百万美元的问题。它们已经在伪多项式时间内得到了解决（有关背包问题的维基百科页面上有更多详细信息）。 - hazzen
6目前没有已知的多项式时间算法可以解决任何NP完全问题； 如果有一种算法可以解决其中一个问题，所有其他NP完全问题都可以在多项式时间内归约到它。我认为hazzen所指的是，某些问题（例如背包问题）可以在多项式时间内得到相当不错的近似解。然而，你得到的近似解越接近完美解，就越远离多项式时间。 - Jay Conrod
你能否命名问题并描述算法呢？我们当然很有兴趣。 - piccolbo
许多NP完全问题可以使用动态规划来解决。以字符串对齐（编辑距离）问题为例，使用朴素实现的时间复杂度为O(k^n)，但使用动态规划则为O(n^2)。通常，任何具有最优子结构和重叠子问题的问题都可以通过记忆化来降低复杂度，这也是动态规划所做的。维基百科上有一个不错的解释和一些示例。 - Daniel Spiewak
需要注意的是，动态规划并没有真正提供一个在多项式时间内解决NP完全问题的算法，它只是利用了一类非常特定的问题结构来消除冗余工作。该技术不适用于 NP完全问题的一般类别。如果可以这样做，那将是一个了不起的结果。 :-) - Daniel Spiewak
然而，你的回答部分是不正确的 - 没有已知的 NP-hard 问题可以在多项式时间内解决。编辑距离不是 NP-hard（除非 P = NP）；它在 P 中。（一些 NP 问题可以在多项式时间内解决，然后它们属于称为 P 的子集。） - sdcvvc
3
这是NP完全问题。但是如果您确实找到了一个好的方法，请告诉我，我将向您展示如何致富。
- 1800 INFORMATION
2
嗯...这要取决于你的定义。哈密顿路径肯定是NP完全问题。然而，一个可以访问边和顶点多次的哈密顿行走（只要在末尾加上步行），可以在O(p^2logp)或O(max(c^2plogp, |E|))内计算，只要你的图满足Dirac最初猜想并由Takamizawa证明的某些条件。请参见Takamizawa（1980）的“在图中查找短闭合跨步行的算法”。
保罗
- Paul
1
令人惊讶的是，对于OP问题的唯一正确答案竟然没有得到任何赞同... - m.raynal
2
寻找更好的最短路径算法是不太可能的，因为它是NP难问题。但是有一些启发式方法可以尝试，也许你可以参考一下课堂笔记 ;)。
为了减少复杂性，您可以使用贪婪算法来找到一个相对较短的路径。
- David L Morris
1
我的问题：证明在图G中寻找哈密顿回路的搜索问题RHAM是自可归约的。当一个搜索问题R可以被Cook约简为一个决策问题时，它就是自可归约的。即：SR={ x : R(x) ≠ ∅ }
- user477959
1
根据你所处理的图形是如何生成的，你可能能够通过贪婪路径扩展和在卡住时进行随机边交换来获得预期的多项式时间对抗随机实例。
这种方法在针对随机生成的相对稀疏的图形，并保证具有哈密顿路径的情况下效果很好。
这种方法在针对随机生成的相对稀疏的图形，并保证具有哈密顿路径的情况下效果很好。
- Captain Segfault
1
1为什么要踩这个回答？这是一个很好的回答，比起那些“哈哈 NP完全”不作为的回答要好得多，因为它告诉了你可以做什么。 - ShreevatsaR
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接