我正在尝试解决哈密顿循环问题。我能够找到包含所有顶点的路径，但无法完成循环。
有人可以为我提供一个算法来找到循环吗？
问问题
36691 次
4 回答
16
确定图是否具有哈密顿循环是一个 NP 完全问题。这意味着我们可以检查给定路径是否是多项式时间内的哈密顿循环，但我们不知道任何能够找到它的多项式时间算法。
唯一可以用来找到哈密顿循环的算法是指数时间算法。他们之中有一些是
- 蛮力搜索
- 动态规划
- 您可以在此处找到其他指数但速度更快的算法
于 2012-10-28T09:24:57.437 回答
2
这是计算机科学中最基本的问题之一，有很多解决方案取决于您想要什么：从这里开始http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms
于 2012-10-28T09:04:09.873 回答
2
我希望我找到的这个下面的链接能帮助你清楚地解释...... http://www.geeksforgeeks.org/archives/19092
于 2012-10-28T09:07:09.263 回答
0
如果可能，请使用 SAT 求解器。它们没有 Wikipedia 文章中算法的良好理论时间限制，但在实践中，它们通常可以惊人地快速解决它们。
于 2017-09-21T10:46:59.700 回答