【算法】【状压DP】最短 Hamilton 路径中被忽视的玄妙之处
本文最后更新于：2024年1月17日 晚上 22:39
【算法】【状压DP】最短 Hamilton 路径中被忽视的玄妙之处
1 题目：最短 Hamilton 路径
最短 Hamilton 路径
给定一个有权无向图，给定起点 \(0\) 和终点 \(n-1\)。
求是否存在一条路径，使得每个点恰好经过一次，且路径权值和最小。
输入格式
第一行输入整数 \(n\)。
接下来 \(n\) 行每行 \(n\) 个整数，其中第 \(i\) 行第 \(j\) 个整数表示点 \(i\) 到 \(j\) 的距离（记为 \(a[i,j]\)）。
对于任意的 \(x,y,z\) ，数据保证 \(a[x,x]=0，a[x,y]=a[y,x]\) 并且 \(a[x,y]+a[y,z]≥a[x,z]\)。
输出格式
输出一个整数，表示最短 \(Hamilton\) 路径的长度。
数据范围
\(1≤n≤20\)
\(0≤a[i,j]≤107\)
2 状压DP模板AC代码
先给出最终的代码，然后我们再分析其中不被重视的玄秘之处。
1 | |
3 常规分析
点的编号从 \(0\) 开始，\(n-1\) 为终点。
用 \(dp[S][j]\) 表示点集 \(S\) 中，以 \(j\) 为终点的最短路径长度。（注意此处并没有指定起点）
我们从最小的点集开始枚举，直到逐步扩大到包含所有点的点集。最后的答案就是 \(dp[S_{final}][n-1]\)。
容易发现，\(dp[S][j]\) 的状态转移方程为：
\[ dp[S][j] = min\{dp[S-j][k] + dist[k][j]\} \quad (k \in S-j) \]
其中 \(S-j\) 表示 \(S\) 中除去 \(j\) 之外的点集。
这个状态转移方程的意思是，我们枚举 \(S-j\) 中的一个点 \(k\)，然后计算 \(dp[S-j][k] + dist[k][j]\)，即 \(S-j\) 中以 \(k\) 为终点的最短路径长度加上 \(k\) 到 \(j\) 的距离，这个值就是 \(S\) 中以 \(j\) 为终点的最短路径长度。
4 细节解读
首先要注意这并不是全局的最短 Hamilton 路径，而是指定了起点和终点情况下的最短 Hamilton 路径。
观察 \(dp[S][j]\) 的状态转移方程，我们发现，\(dp[S][j]\) 的值只与点集和终点有关，而与起点无关。
那么哪里限制了起点呢？实际上在这个地方：
1 | |
这两行代码看似顺其自然，但是却是这个算法的核心！
很多地方讲解时重点放在了状态设置上，而没有讲解边界条件设置上的玄机。
我们需要搞清楚为什么要这样初始化，为什么把只有起点的点集的 Hamilton 距离设为0，把其他设为无穷大？为什么这样就能约束起点？这绝对不是自然而然的事情！
状态的遍历过程
1 | |
我们发现，状态 \(S\) 从1（二进制为00...01）开始遍历，然后每次加1遍历所有以二进制表示的状态：
以 \(n = 3\) 为例：
1 | |
在 \(1 \sim 2^n-1\) 顺序遍历 \(S\) 时如何保证其子集 \(S-j\) 都已经计算好了？
我们可以发现， \(S-j\) 对比 \(S\) 的二进制表示中，每次只有一个位从1变成0。所以根据二进制数的特性，\(S-j\) 对应的二进制数一定比 \(S\) 的二进制数小。因此，我们可以保证，\(S-j\) 肯定是在 \(S\) 之前被遍历过的。
\(dp[S][j]\) 没有包含起点信息，为什么能够保证 \(dp[S][j]\) 所代表的最短路径中，起点一定为点0？
因为我们在
memset时将只有一个点但不是起点0的点集 \(S_{2^n(n>1)}\) 的最短路径 \(dp[S_{2^n(n>0)}][n]\) 设置为了 \(INF\) 。在递推过程中， 不包含起点的点集的 \(dp[S_{(0 \notin S)}][j\in S]\) 由其子集的 \(dp[S-j_{(0 \notin S-j)}][k\in S-j]\) 递推而来。
我们追溯这个过程会发现，它们最终都是由 \(dp[S_{2^n(n>0)}][n]=INF\) 递推而来。所以不包含起点的点集都一定是 \(INF\) 。
同时，在计算包含起点的点集 \(dp[S_{(0 \in S)}][j\in S]\) 的过程中，如果枚举到不包含起点的子集，由于 \(dp[S-j_{(0 \notin S-j)}][k\in S-j]=INF\)，那么这里的路径长度也就成了 \(INF\) ，在取最小值时不会被选中。
点集包含起点但是终点为起点0的 \(dp[S_{(0 \in S)}][0]\) 同理
所以，不是 \(INF\) 的 \(dp[S][j]\) ，都从只包含起点的点集 \(dp[S_0][0] = 0\) 递推得出。
因此，\(dp[S][j]\) 所代表的最短路径中，起点一定为点0。
为什么要把只有起点的点集的 Hamilton 距离设为0，把其他设为无穷大？如果想要有多个起点，该怎么做？
我们从第3点的分析中可以看出，只有起点的点集的 Hamilton 距离设为0，是为了保证 \(dp[S][j]\) 在取最小值的时候，只有起点为点0的路径不是INF，其他都是INF，这样就能保证 \(dp[S][j]\) 所代表的最短路径中，起点一定为点0。
所以如果想要有多个起点，那么就要把所有起点的点集的 Hamilton 距离 \(dp[S][j]\) 初始化为0，其他设为无穷大就可以了。
上面代码中遍历 \(S\) 时为什么要计算不包含起点0的情况？
这个只是为了让代码更加通用，如果不计算不包含起点0的情况，那么代码可以改为为：
1
2
3
4
5
6
7
8
9
10for (int S = 1; S < (1 << n); S+=2) { // 跳过不包含起点0的情况，也就是跳过偶数
for (int j = 1; j < n; j++) { // 跳过将起点0作为终点的情况，也就是跳过j=0
if ((S >> j) & 1) {
for (int k = 0; k < n; k++) { // 注意这里k不能从1开始，因为dp[1][0]=0的终点是0
if ((S ^ (1 << j)) >> k & 1)
dp[S][j] = min(dp[S][j], dp[S ^ (1 << j)][k] + dist[k][j]);
}
}
}
}如果有多个起点，那么代码可以改为为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14// 例子：图总共8个点{0,1,2,3,4,5,6,7}，以{1,2,5}为起点
memset(dp, 0x3f, sizeof(dp));
dp[0b00000010][1] = dp[0b00000100][2] = dp[0b00100000][5] = 0;
for (int S = 1; S < (1 << n); S++) {
if (!(S & 0b00100110)) continue; // 跳过所有点都不在起点集合中的情况
for (int j = 0; j < n; j++) { // 这里就不能跳过j=0了
if ((S >> j) & 1) {
for (int k = 0; k < n; k++) {
if ((S ^ (1 << j)) >> k & 1)
dp[S][j] = min(dp[S][j], dp[S ^ (1 << j)][k] + dist[k][j]);
}
}
}
}
5 总结
看了网上很多的题解，好像都没有提到这个细节，所以还是要自己多思考，多总结。不是能写出AC代码就行了，还要能够清楚地解释为什么这样写。这样在遇到变种题型时才能够快速修改代码。