我有相对较小的（40-80 个节点）三次（3 正则）平面图，我必须确定它们的哈密顿性。我知道这个任务是 NP 完全的，但我希望渐近指数时间算法对于我感兴趣的图形大小来说仍然非常快。
问问题
837 次
2 回答
3
40 个节点似乎可行。您从 60 条边中选择了 40 条要包括在内。
让我们尝试深度优先搜索。
首先，选择一个顶点 V。您需要准确排除它的 3 个入射边之一。一次尝试这 3 种可能性。当您选择要排除的边时，您将强制包含 4 条边。此后，我们将排除边的顶点称为“已使用”。
如果你可以重复这个过程 10 次，你会选择所有 40 条边，只搜索 3^10 (59049) 种可能性。当然，在确定了足够多的边之后，您将用完“孤立”的顶点。
但是，我们现在有了一个算法的想法。在每一步，尝试选择一个“使用”邻居最少的顶点。实际上，选择一个有 2 个使用过的邻居的顶点是最好的，因为使用过的边是强制的。我不确定选择具有 1 个或 0 个已使用邻居的顶点是否是次优的。尝试两种方式！（并且 3 个使用的邻居表示搜索失败）
当我们完成挑选边缘时，检查它们是否形成一个循环。
你有一些示例图吗？我可能会尝试一个简单的实现。
于 2010-07-06T22:51:00.357 回答
2
来自http://mathworld.wolfram.com/HamiltonianCycle.html：“Rubin (1974) 描述了一种有效的搜索过程，它可以使用大大减少回溯和猜测的推论来找到图中的部分或全部 Hamilton 路径和电路。”
这篇论文在这里出售：http: //portal.acm.org/citation.cfm?id= 321850.321854
于 2010-07-06T22:08:04.657 回答