algorithm - 哈密​​顿循环算法

Question

我一直在寻找一些哈密顿循环算法，但我找不到任何实现，甚至没有一个伪代码！我什至不需要输出循环，只需检查图形是否有循环。输入是一个具有 V 个顶点和 E 个边的图。另外，我想有一个算法来检查一个图是否有哈密顿路径。我不需要输出路径，只需检查它是否有一个。两者都应该在多项式时间内。

Answer 1

该问题是 NP 完全问题之一。

蛮力算法只是创建所有排列并检查其中一个是否是可行的解决方案。

检查可行性：
让当前排列为v1,v2,...,vn：如果图中每个i都有一条边v_i -> v_(i+1)，并且v_n->v1- 那么解决方案是可行的。

---

另一种方法是创建一个图G'=(V,E',w)，其中新边E' = VxV（所有边）和权重函数为：

w(u,v) = 1 if there is an edge (u,v) in the original graph
         infinity otherwise.

现在你得到了一个旅行商问题，并且可以用动态规划来解决它O(n^2*2^n)

Answer 2

除非 P = NP，否则不能在多项式时间内确定一般图的哈密顿性。

在线 HCP 启发式存在于http://fhcp.edu.au/slhweb/，您可以在其中上传图表并对其进行测试，但如果您想要自己的函数，您需要自己编写，或者拼接到其他人的函数中. Andrew Chalaturnyk 写了一个非常好的算法。