哈密顿路径查找器

伪代码

目前没有已知的多项式算法，因此诚实的写法是带剪枝的回溯。正是剪枝让它勉强可用。

哈密顿路径(图):
    对每个起点 s:
        若 回溯([s], {s}): 返回该路径
    返回 无解

回溯(路径, 已访问):
    若 已访问 包含全部结点: 返回 真

    u = 路径.末端
    对 u 的每个未访问邻居 v:
        // 值回票价的剪枝：
        //  - 某个未访问结点此刻已不可达 -> 失败
        //  - 剩余图中有两个或更多度为 1 的
        //    未访问结点 -> 失败
        已访问.加入(v)
        若 回溯(路径 + [v], 已访问): 返回 真
        已访问.移除(v)      // 撤销并尝试下一个

    返回 假

可达性剪枝是其中最要紧的一条。选定一条部分路径之后，对未访问的结点跑一次快速遍历；只要其中任何一个此刻已与当前末端断开，这条分支就已死亡，可以立刻放弃，而不必等到整棵子树都搜完。在稀疏图上，这能把一次不可行的搜索变成一次很快的搜索，尽管最坏情况仍是指数级。

分步示例演算

在一个五结点图上从 A 出发寻找哈密顿路径，并看清同一个图为何不存在哈密顿回路。

示例图: 无向边 A-B、B-C、C-D、D-E，外加两条弦 A-C 与 B-D。

1. 先看度数. A 的度为 2（B 与 C），B 为 3（A、C、D），C 为 3（A、B、D），D 为 3（B、C、E），而 E 的度为 1，唯一的邻居是 D。度为 1 的结点必然是任何哈密顿路径的端点，这就已经告诉我们 E 是其中一端。
2. 先尝试 A 到 B. 从 A 走到 B，再从 B 走到 C，从 C 出发唯一未访问的邻居是 D，从 D 出发唯一未访问的是 E。于是得到 A-B-C-D-E，覆盖了全部五个结点。
3. 还存在第二个解. 从 A 沿另一条分支回溯可得 A-C-B-D-E，同样合法。哈密顿路径常常并不唯一，而一个返回首个找到的解的算法回答的是存在性问题，而不是计数问题。
4. 现在改问回路. 哈密顿回路必须从最后一个结点回到 A。两条路径都终止于 E，而 E 的度为 1，它唯一的边通向 D。并不存在 E-A 这条边，因此不存在哈密顿回路。

存在两条哈密顿路径 A-B-C-D-E 与 A-C-B-D-E，但不存在哈密顿回路。度为 1 的结点 E 几乎独力解决了这两个问题：它把自己钉成路径端点，同时排除了任何回路，因为回路要求每个结点的度至少为 2。在开始搜索之前先检查度数既便宜又往往具有决定性。

复杂度及其来源

时间: 朴素 O(V!)，动态规划 O(V^2·2^V) · 空间: 动态规划 O(V·2^V)

朴素回溯实际在枚举排列，最坏情况为 O(V 的阶乘)，超过大约 12 个结点就毫无希望。基于子集的 Held-Karp 动态规划要好得多：状态是「已访问结点的子集」加上「当前末端」，共有 2 的 V 次方乘以 V 个状态，每次转移花费 O(V)，因此总计为 O(V 的平方乘以 2 的 V 次方) 时间和 O(V 乘以 2 的 V 次方) 内存。这在大约 20 个结点以内是可行的，此时 2 的 20 次方乘以 20 约为两千万个状态。该问题是 NP 完全的，因此不预期存在多项式算法；不过带剪枝的回溯在真实的稀疏图上常常很快就能结束。

何时使用哈密顿路径，何时不宜

在动用指数级手段之前，先确认你面对的究竟是哪个问题，因为其中有两个其实很容易。

常见陷阱

• 把它与欧拉问题混为一谈. 两者名字相近，难度却天差地别。欧拉覆盖的是边且是线性的；哈密顿覆盖的是结点且是 NP 完全的。解错问题是这里代价最高的一种失误。
• 不做剪枝就开始搜索. 不带可达性检查的纯回溯会去搜索大量已经死掉的子树。检查所有未访问结点是否仍能从当前末端抵达，以及剩余图中度为 1 的未访问结点是否至多两个，通常能把搜索规模压缩几个数量级。
• 以为有路径就一定有回路. 哈密顿路径可以存在，而哈密顿回路却不存在，上面的例子正是如此。回路还额外要求从最后一个结点回到第一个结点有边，而任何度为 1 的结点都会彻底排除这种可能。
• 把 Dirac 条件反过来用. Dirac 定理说的是：若每个结点的度都至少为 V/2，则哈密顿回路存在。其逆命题并不成立：许多度数很低的图照样含有哈密顿回路，因此不满足该条件什么也证明不了。
• 指望它能扩展到大规模. 超过大约 20 到 25 个结点，精确答案可能根本就够不着。如果真正的目标是一条好路线而不是一个证明，请把它建模为 TSP 并使用启发式方法。

常见问题

什么是哈密顿路径？

哈密顿路径是一条恰好访问图中每个结点一次的路径。如果它还回到出发结点，就是哈密顿回路。与欧拉路径不同，它不必用上所有边，而且不能重复访问任何结点。

为什么寻找哈密顿路径很困难？

因为这个性质无法在局部检验。欧拉路径之所以容易，是因为在每个结点上做一次简单的度数统计就能判定存在性；而对于「每个结点恰好访问一次」，并不存在可与之相比的局部判据。该问题是 NP 完全的，因此没有已知的多项式算法，找到一个就等于解决了 P 与 NP。

哈密顿路径与欧拉路径有什么区别？

哈密顿路径恰好访问每个结点一次，可以不用某些边。欧拉路径恰好使用每条边一次，可以重复访问结点。欧拉存在性可以在 O(V + E) 内通过统计奇度结点判定；哈密顿存在性则是 NP 完全的。

如何寻找哈密顿路径？

对小规模图，从每个可能的起点出发做回溯并配合强力剪枝：一旦某个未访问结点变得不可达，或者剩余图中出现两个及以上度为 1 的未访问结点，就立刻放弃该分支。在大约 20 个结点以内，基于子集的 Held-Karp 动态规划能以 O(V 的平方乘以 2 的 V 次方) 给出确定答案。

哈密顿路径与 TSP 有什么关系？

旅行商问题是它的带权优化版本：不是问「是否存在一条走遍所有结点的回路」，而是在带权完全图中求最便宜的那一条。判定哈密顿回路是否存在可以归约到 TSP，这也是 TSP 同样属于 NP 困难的原因。