AcWing 91. 最短Hamilton路径
枚举 $n$ 个点的全排列,计算路径长度取最小值,时间复杂度位 $\mathcal{O}(n * n!)$。
使用二进制状态压缩 DP 可以优化到 $\mathcal{O}(n^2 * 2^n)$。
在任意时刻如何表示哪些点已经被经过,那些点没有被经过?
可以用一个 $n$ 位二进制数,若其第 $i$ 位 $(0 \le1 i < n)$ 为 $1$,则表示第 $i$ 个点已经被经过,反之未被经过。
在任意时刻还需要知道当前所处的位置,因此我们可以使用 $F[i, j] (0 \leq 1 i < 2^n, 0 \leq j < n)$ 表示 “点被经过的状态” 对应的二进制数为 $i$,且目前处于点 $j$ 时的最短路径。
在起点时,有 $F[1, 0] = 0$,即只经过了点 $0$ ($i$ 只有第 $0$ 位为 $1$),目前处于起点 $0$,最短路长度为 $0$。
为了方便起见,我们将 $F$ 数组其他的值设为无穷大。
目标是 $F[(1 « n) - 1, n - 1]$,即经过所有点 ($i$ 的所有位都是 $1$),处于终点 $n - 1$ 的最短路。
在任意时刻,有 $F[i, j] = \min {F[i \oplus (1 « j), k] + weight(k, j) }$,其中 $0\leq k < n$ 并且 $((i » j) \& 1)=1$,即当前时刻 “被经过的点的状态” 对应的二进制数为 $i$,处于点 $j$。
因为 $j$ 只能被恰好经过一次,所以一定是刚刚经过的,故在上一时刻 “被经过的点的状态”对应的二进制数的第 $j$ 位应该赋值为 $0$,也就是 $i \oplus (i « j)$。
另外,上一时刻所处的位置可能是 $i \oplus (1 « j)$中任意一个是 $1$ 的数位 $k$,从 $k$ 走到 $j$ 需经过 $weight(k, j)$ 的路程,可以考虑所有这样的 $k$ 取最小值。
完整代码:最短Hamiltion路径.cpp