用于在图中查找哈密顿游走的多项式时间算法
是否存在用于在图中查找哈密顿游走的多项式时间算法？
我的算法是 N 阶乘并且非常慢。
Is there a polynomial time algorithm for finding a Hamiltonian walk in a graph?
My algorithm is N factorial and is really slow.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
您刚刚提出了价值百万美元的问题。 寻找哈密尔顿路径是一个 NP 完全问题。 一些 NP 难题可以使用动态规划在多项式时间内解决，但是（据我所知）这不是其中之一。
You just asked the million dollar question. Finding a Hamilton path is an NP-complete problem. Some NP-hard problems can be solved in polynomial time using dynamic programming, but (to my knowledge) this is not one of them.
一般来说，由于哈密顿路径问题（的决策版本）是 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），可以很容易地找到一个在多项式时间内（快）。
In general, as the (decision version of the) Hamiltonian Path problem is NP-complete, you cannot hope to get a polynomial-time algorithm for finding Hamiltonian paths. You can slightly speed it up with the usual N! → N22N dynamic programming trick (compute hp[v][w][S] = "is there a path that has endpoints v and w and whose vertices are the subset S" for every subset S and every two vertices v and w in it using DP), but that's still exponential.
However, there are many special kinds of graphs for which Hamiltonian paths will always exist, and they can be found easily (see work of Posa, Dirac, Ore, etc.)
For instance, the following is true: If every vertex of the graph has degree at least n/2, then the graph has a Hamiltonian path. You can in fact find one in O(n2), or IIRC even O(n log n) if you do it more cleverly.
[Rough sketch: First, just connect all vertices in some "Hamiltonian" cycle, nevermind if the edges are actually in the graph. Now for every edge (v,w) of your cycle that is not actually in the graph, consider the rest of the cycle: v...w. As deg(v)+deg(w)>=n, there exist consecutive x,y in your list (in that order) such that w is a neighbour of x and v is a neighbour of y. [Proof: Consider {the set of all neighbours of w} and {the set of all successors in your list of neighbours of v}; they must intersect.] Now change your cycle [v...xy...wv] to [vy...wx...v] instead, it has at least one less invalid edge, so you'll need at most n iterations to get a true Hamiltonian cycle. More details here.]
BTW: if what you are looking for is just a walk that includes every edge once, it's called an Eulerian walk and for graphs that have it (number of vertices of odd degree is 0 or 2), one can quite easily be found in polynomial time (fast).
我的查询：表明在图 G 中查找哈密顿循环的搜索问题 RHAM 是
自还原
如果搜索问题 R 可库克简化为决策问题，则它是可自简化的
SR={ x : R(x) ≠ ∅ }My Query: Show that a search problem RHAM for finding a Hamiltonian cycle in the graph G is
self-reducible
A search problem R is self-reducible if it is Cook-reducible to a decision problem
SR={ x : R(x) ≠ ∅ }根据您正在使用的图形的生成方式，您可能能够通过执行贪婪路径扩展，然后在卡住时进行随机边缘交换，获得针对随机实例的预期多项式时间。
这对于保证具有哈密顿游走的随机生成的相对稀疏的图非常有效。
Depending on just how the graphs you're working with are generated you might be able to get expected polynomial time against a random instance by doing greedy path extension and then a random edge swap when that gets stuck.
This works well against randomly generated relatively sparse graphs guaranteed to have a Hamiltonian walk.
嗯..这取决于你的定义是什么。 哈密尔顿路径当然是 NP 完全的。 然而，可以多次访问边和顶点的哈密顿步行（是的，只要在末尾添加步行位，它仍然称为哈密尔顿步行）可以用 O(p^2logp) 或 O(max(c^2plogp) 计算, |E|)) 只要你的图满足狄拉克首先猜想和高见泽证明的某个条件。 参见 Takamizawa (1980)“一种在图中查找短闭跨越游走的算法”。
保罗
Hmmm.. this depends on what your definitions are. An hamiltonian path is certainly NP-complete. However, an hamiltonian walk which can visit edges and vertices more than once (yes it's still called hamiltonian so long as you add the walk bit at the end) can be calculated in O(p^2logp) or O(max(c^2plogp, |E|)) so long as your graph meets a certain condition which Dirac first conjectured and the Takamizawa proved. See Takamizawa (1980) "An algorithm for finding a short closed spanning walk in a graph".
Paul
找到一个更好的最短算法是不太可能的，因为它是 NP 难的。 但是您可以尝试一些启发式方法，也许您可能需要查阅您的讲义以了解这些方法；）。
为了降低复杂性，您可以使用贪婪算法找到较短的步行。
Finding a better algorithm for the shortest is unlikely, as it is NP hard. But there are some heuristics that you could try, and perhaps you might want to consult your lecture notes for those ;) .
For less complexity you could find a short(ish) walk using the greedy algorithm.
它是 NP 完全的。 但如果你确实找到了一个好方法，请告诉我，我会告诉你如何致富。
It's NP complete. But if you do manage to find a good method, let me know and I'll show you how to get rich.