是否有用于在图中找到哈密顿步行的多项式时间算法？
我的算法是 N 阶乘，而且非常慢。
Nat
问问题
8067 次
7 回答
21
通常，由于哈密顿路径问题的（决策版本）是 NP 完全的，因此您不能希望获得一个多项式时间算法来寻找哈密顿路径。您可以使用通常的 N 稍微加快速度！→ N 2 2 N动态规划技巧（计算 hp[v][w][S] = “对于每个子集 S 和每两个顶点 v 和w 在其中使用 DP），但这仍然是指数级的。
然而，有许多特殊类型的图始终存在哈密顿路径，并且很容易找到它们（参见 Posa、Dirac、Ore 等的工作）
例如，以下情况是正确的：如果图的每个顶点的度数至少为 n/2，则图具有哈密顿路径。事实上，如果你做得更聪明，你可以在 O(n 2 ) 或 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），可以很容易地在多项式中找到时间（快）。
于 2008-09-18T02:19:55.270 回答
17
你刚刚问了百万美元的问题。找到一条汉密尔顿路径是一个 NP 完全问题。一些 NP 难题可以使用动态规划在多项式时间内解决，但（据我所知）这不是其中之一。
于 2008-09-18T00:18:30.380 回答
3
NP完全了。但是，如果您确实找到了一个好方法，请告诉我，我会告诉您如何致富。
于 2008-09-18T00:16:46.907 回答
2
为最短找到更好的算法是不可能的，因为它是 NP 困难的。但是你可以尝试一些启发式方法，也许你可能想查阅你的讲义；）。
为了降低复杂性，您可以使用贪心算法找到一个短的（ish）步行。
于 2008-09-18T00:33:04.293 回答
2
嗯..这取决于你的定义是什么。哈密顿路径肯定是 NP 完全的。但是，可以在 O(p^2logp) 或 O(max(c^2plogp , |E|)) 只要你的图满足狄拉克首先猜想和高见泽证明的某个条件。参见 Takamizawa (1980) “在图中寻找短闭合跨步游走的算法”。
保罗
于 2010-04-25T21:01:27.920 回答
1
根据您正在使用的图形的生成方式，您可以通过执行贪婪路径扩展然后在卡住时进行随机边缘交换来获得针对随机实例的预期多项式时间。
这对于保证具有哈密顿游走的随机生成的相对稀疏的图非常有效。
于 2008-09-20T00:45:35.173 回答
1
我的查询：证明在图 G 中寻找哈密顿循环的搜索问题 RHAM 是自约的搜索问题 R 是自约的，如果它是库克可约化为决策问题
SR={ x : R(x) ≠ ∅ }
于 2010-10-16T14:25:39.387 回答