如何找出不使用“禁止”边的哈密顿回路数量？

Question

这个问题实际上是重新表述这个。 Code jam问题如下：

给定具有N节点和K“禁止”的边的完整无向图。 N <= 300，K <= 15。查找在不使用任何K“禁止”边的情况下图中哈密顿循环的数量。

简单的DP方法O(2^N*N^2)对于这样的N不起作用。 看起来获胜的解决方案是O(2^K)。 有人知道如何解决这个问题吗？

- Michael

---

为什么在bmerry的解决方案中，代码最后要乘以9901/2？"(x*w/2) mod w"是什么意思？ - user749486

Answer 1

让我们找出所有被禁止的边的子集S中，有多少个哈密顿回路，这些回路使用了S中所有的边。如果解决了这个子任务，那么我们就可以通过包容排斥公式来解决问题。

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

如果存在一个循环，那么它必须通过所有顶点，否则我们将无法完成哈密顿回路。如果是这种情况，答案为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的解决方案中得到实现（代码非常简洁，顺便说一句）。

- adamax

Answer 2

哈密顿回路问题是旅行商问题的一个特例 （当两个城市相邻时，将它们之间的距离设置为一个有限常数，否则为无穷大）。

这些都是NP完全问题，简单来说就是没有已知的快速解决方法。

用于寻找哈密顿路径的一个微不足道的启发式算法是构建一个路径abc...并将其扩展直到不再可能为止；当路径abc ... xyz不能再扩展因为z的所有邻居都已经在路径中时，向后退一步，删除边yz并使用y的另一个邻居来扩展路径；如果没有选择产生哈密顿路径，则再向后走一步，删除边xy并使用x的另一个邻居来扩展路径，依此类推。 此算法肯定会找到哈密顿路径（如果存在），但是它运行的时间是指数级别的。

有关更多信息，请参见Cormen的“算法导论”中的NP完全问题章节。

- codersofthedark

---

在某种意义上，TSP问题不同于哈密顿回路问题。TSP是一个优化问题，大部分情况下，您会假设它是一个完全图。也就是说，您可以从任何一个顶点到达任何其他顶点。哈密顿回路问题是一个决策问题，并且通常用于非完全图。 - starflyer