如何找到不使用“禁止”边的哈密尔顿周期数？

Question

这个问题实际上改写为one。该code jam problem如下：

您将得到与ñ节点和ķ一个完整的无向图“禁止入内”的边缘。 N < = 300,K < = 15.找出图中不使用任何K“禁止”边的哈密尔顿周期数。

直接的DP方法O(2^N*N^2)不适用于这样的N。它看起来像获胜的solutions是O(2^K)。有人知道如何解决这个问题吗？

Answer 1

让我们找出禁用边的每个子集S，存在多少个哈密尔顿周期，即使用S的所有边。如果我们解决了这个子任务，那么我们将通过inclusion-exclusion formula解决问题。

现在我们该如何解决子任务？让我们画出S的所有边。如果存在一个度数大于2的顶点，那么显然我们不能完成这个循环，答案是0.否则，图被分解为连通分量。每个组件都是唯一的顶点，循环或简单路径。

如果存在一个循环，那么它必须通过所有的顶点，否则我们将无法完成汉密尔顿循环。如果是这种情况，答案是2（该循环可以在2个方向进行遍历。）否则，答案是0

其余情况是，当有Ç路径和ķ鞋底顶点。要完成哈密尔顿循环，我们必须选择每个路径的方向（2^c方式），然后选择组件的顺序。我们有c + k组件，所以它们可以在（c + k）中重新排列！方式。但是我们对循环感兴趣，所以我们没有区分通过循环移位变成彼此的顺序。 （So（1,2,3），（2,3,1）和（3,1,2）是相同的。）这意味着我们必须按照班次数除以答案，c + k。所以答案（对于子任务）是2^c（c + k-1）！。

这个想法是在bmerry的解决方案（非常干净的代码，顺便说一句）实施。

Answer 2

哈密顿周期的问题是旅行推销员问题的特殊情况（由两个城市之间的距离设定为如果它们是相邻的和无穷大，否则一有限常数而获得。）

这些是NP完全问题，其在简单的话意味着他们没有快速的解决方案。

定位哈密顿路径的一个简单的启发式算法是构建一个路径abc ...并将其扩展到不再可能;当路径abc ... xyz不能再扩展时，因为z的所有邻居已经位于路径中，则返回一步，移除边缘yz并用y的不同邻居延伸路径;如果没有选择产生哈密尔顿路径，那么需要进一步退一步，去除边缘xy并用x的不同邻居延伸路径，以此类推。这个算法肯定会找到哈密尔顿路径（如果有的话），但它运行在指数时间。

详细检查“介绍交易算法”的NP完全问题本章通过Cormen