问题求解III-HW03 题解

本题数据范围较大，使用 fleury 算法无法通过，需要实现线性的 Hierholzer 算法。Hierholzer 算法的思路如下：

1. 如果存在奇数度数点 $u, v$，则取任意一条 $uv$ 迹，否则取图中任意一条迹。记当前的路径为 $T$。
2. 取 $T$ 中仍有未访问邻边的非孤立节点 $w$，寻找一条 $ww$ 迹，将这条闭迹插入到 $T$ 中。
3. 重复步骤 2 直到所有的边均被访问。

寻找合法的 $uv$ 迹和 $ww$ 迹看似困难，其实在如下几条性质的加持下非常简单：

• 在一个有两个奇数度数节点的图中从一个奇点出发，以任意方法不走重复边地遍历，直到走到死路，最后一定停留在另一个奇点上。且去掉这条迹之后，图中所有点度数均为偶数。
• 在一个所有节点度数均为偶数的图中从任意节点 $w$ 出发，以任意方法不走重复边地遍历，直到走到死路，最后一定回到 $w$。且去掉这条迹之后，图中所有点度数仍然均为偶数。

这两条性质的证明并不困难，形象化地，对于一个偶数度数点来说，有“进”则必有“出”，所以最后一定会停在奇点/出发点上。因此在上述算法中，所有找迹的部分只要“闷头向前搜”即可。

现在的另外一个问题是：如何寻找步骤2中的合法出发点 $w$，以及找到 $ww$ 迹之后如何高效插入。Hierholzer 算法存在经典且精巧的回溯实现可以完成这两件事。我们直接给出伪代码：

def hierholzer(u):
    for (u, v) in G.edges:
        delete (u, v) from G.edges
        hierholzer(v)
    path.append(u)

大家可以仔细阅读这段代码并思考两个问题：

• 该函数是如何通过回溯找到当前路径上仍有出边的节点的？
• 该函数在走完所有 $u$ 的出边后将 $u$ 加入路径，该顺序是如何做到将步骤 2 中的 $ww$ 迹“插入”原路径的？

做法1: 折半搜索

折半搜索的主要思想是将一个大任务拆成两个规模各为一半的子任务，然后尝试在中间将两部分的结果拼接起来。假设我们可以高效地拼接，记原算法复杂度为 $f(n)$，则折半搜索可以将复杂度优化为 $2\cdot f(n/2)$。当 $f$ 是一个指数或更高阶的函数时，折半搜索通常能显著降低复杂度。

直接阶乘枚举所有可能路径的时间复杂度为 $O(n!)$。如果使用折半搜索，我们可以计算图中所有节点数为 $n/2$ 的路径的长度。然后枚举每条“半路径”(此时另一半路径的顶点已知)和另一半路径与当前路径连接的端点，更新最短的哈密尔顿路径。时间复杂度为 $O(C(n, n/2)\cdot n)$。

做法2：状态压缩动态规划

本题更正统的做法是采取状态压缩动态规划。所谓状态压缩，是指用一个 01 串表示当前已经经过的顶点的集合 (1表示已经走过)，这样一个 01 串又可以映射到一个十进制数的二进制表示，因此我们可以用 $[0, 2^n)$ 中的整数来刻画所有可能的经过状态。以下为了表示方便，我们以 $0$ 到 $n-1$ 标号节点。

令 $dp(Mask, u)$ 表示当前已经经过的节点集合为 Mask，当前节点为 $u$ 的情况下，$Mask$ 中经过节点构成的哈密尔顿路径的最短长度。

• 边界条件是容易的：对于所有的 $0\leq x\leq n-1$，有 $dp(2^x, x)=0$ (只有一个点的路径，当前长度为 0)。
• 转移只需枚举路径下一个节点 $v$(需要保证 $v$ 尚未经过)，状态转移方程式为 $$ dp(Mask|2^v, v) = \min\{dp(Mask|2^v, v), dp(Mask, u) + c(u, v)\} $$

最终答案为 $$ ans = \min_{0\leq x<n}dp(2^n-1, x) $$ 状态的数量为 $O(2^n\cdot n)$，每个状态可以向 $O(n)$ 个状态转移，因此总时间复杂度为 $O(2^n\cdot n^2)$。