你得到一个完整的无向图，有N个节点和K个“禁止”边。N <= 300, K <= 15。找出图中不使用任何K个“禁止”边的哈密顿循环数。
的直接 DP 方法O(2^N*N^2)不适用于这样的N。看起来获胜的解决方案是O(2^K). 有谁知道如何解决这个问题？
问问题
2269 次
2 回答
4
让我们找出每个禁止边的子集 S，存在多少个哈密顿循环，使用 S 的所有边。如果我们解决了这个子任务，那么我们将通过包含 - 排除公式来解决问题。
现在我们如何解决子任务？让我们画出S的所有边。如果存在度数大于2的顶点，那么显然我们不能完成循环，答案是0。否则图被划分为连通分量。每个组件都是一个唯一的顶点、一个环或一条简单的路径。
如果存在一个圈，那么它必须经过所有顶点，否则我们将无法完成哈密顿圈。如果是这种情况，则答案为 2。（循环可以在 2 个方向上遍历。）否则答案为 0。
剩下的情况是当有c个路径和k个唯一顶点时。为了完成哈密顿循环，我们必须选择每条路径的方向（2^c路），然后选择组件的顺序。我们有c+k 个分量，所以它们可以在(c+k) 中重新排列！方法。但是我们对循环感兴趣，所以我们不区分通过循环移位相互转换的顺序。（所以 (1,2,3), (2,3,1) 和 (3,1,2) 是相同的。）这意味着我们必须将答案除以移位次数c+k。所以答案（对子任务）是2^c (c+k-1)！.
这个想法在 bmerry 的解决方案中实现（非常干净的代码，顺便说一句）。
于 2011-01-21T15:39:37.040 回答
1
哈密顿循环问题是旅行商问题的一个特例（如果两个城市相邻，则将它们之间的距离设置为有限常数，否则为无穷大。）
这些是 NP 完全问题，简单来说意味着没有已知的快速解决方案。
用于定位哈密顿路径的简单启发式算法是构建路径 abc... 并将其扩展直到不再可能；当路径 abc...xyz 因为 z 的所有邻居都已经位于路径中而无法再扩展时，则返回一步，移除边缘 yz 并用 y 的不同邻居扩展路径；如果没有选择会产生哈密顿路径，则后退一步，移除边缘 xy 并用 x 的不同邻居扩展路径，依此类推。这个算法肯定会找到一条哈密顿路径（如果有的话），但它在指数时间内运行。
有关更多信息，请查看 Cormen 的“Algos 简介”的 NP Complete 问题章节
于 2012-04-01T22:08:59.407 回答