我正在尝试解决哈密顿回路问题。我能够找到包含所有顶点的路径，但无法完成回路。
有人能够为我提供一种寻找回路的算法吗？
4个回答
16
确定一个图是否有哈密顿回路是一个 NP 完全问题。这意味着我们可以在多项式时间内检查给定路径是否为哈密顿回路，但我们不知道任何能够找到它的多项式时间算法。
唯一可以用来找到哈密顿回路的算法是指数时间算法。其中一些算法包括：
唯一可以用来找到哈密顿回路的算法是指数时间算法。其中一些算法包括：
- 暴力搜索
- 动态规划
- 其他指数但仍然更快的算法，你可以在这里找到。
- alestanis
2
这是计算机科学中最基本的问题之一，根据您的需求有很多解决方案：请从这里开始查看http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms。
还有相关的SO答案：这里和这里。
还有相关的SO答案：这里和这里。
- Darek
0
如果可能的话，使用SAT求解器。它们没有维基百科文章中算法的良好理论时间限制，但在实践中，它们通常可以出奇地快速解决问题。
- Graham Laight
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接