最短Hamilton路径

最短Hamilton路径

给定一张 $n$ 个点的带权无向图,点从 $0∼n−1$ 标号,求起点 $0$ 到终点 $n−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\leqslant n\leqslant 20 $

$0\leqslant a[i,j]\leqslant 10^{7}$

输入样例:

1
2
3
4
5
6
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例:

1
18

解析

考虑简单的做法,将 $n$ 个数塞入 $k_n$ 的数组中,对 $k_n$ 进行全排列,将每次全排列的结果根据输入的 $a_{i,j}$ 得出Hamilton路径的长度,每次的得数取 $min$ 即为最终答案。

时间复杂度为 $O(n\times n!)$

1
2
3
4
5
6
7
ans = 0x3f;
while(next_permutation(k, k+n)) {
res = 0;
for (int i = 2; i <= n; i++) {
res += a[k[i - 1]][k[j]];
} ans = std::min(ans, res);
}

(注意各处未知数的含义!!!相同的 $i$ 和 $i$ 可能表示不同的意思)

考虑简化问题,设 $f_{i,j}$ 为当前所记录的 i->j 的最短距离,此时存在另外一条路线 i->k->j 的距离是小于 $f_{i,j}$ ,那么此时将 $f_{i,j}$ 的距离更新为 i->k->j 的距离即可。

那么就会存在两个问题

1、如何知道 $k$ 是否是没走过的点

2、如何记录 $f_{i,j}$ 是由 i->k->j

我们发现,上面的问题中,$i$ 是一直没有动过的,我们改变的一直是我们当前所在的点,即 $k、j$,那么我们就可以将 $i$ 变成记录当前所有点的状态,而后面的 $j$ 变成记录当前的所处点,那如何用 $i$ 记录当前所有点的状态呢?用二进制数表示。

我们发现 $n$ 很小,只有20,$f_{1<<20,20}$ 的最大值是 20971520,并不会爆空间,我们用 0 和 1 和当前数字所处的位置来表示第几个点是否走过。

这样我们就解决了第一个问题,然后来解决第二个问题。

假设 i->k->j 一定是最优的最短距离,且在状态 $i$ 中,$i,j,k$ 点均走过了(即在 $i,j,k$ 位上的数都是1),那么 $f_{i,j}$ 的距离一定是 i->k->j。

但是注意,以上的解法泛用所有的情况,假设我们有五个点 $i,j,k,x,y$,此时i->k->j->x->y 的距离大于 i->j->x->k->y,那我们就要选第二种为最短距离,此时和第一种解法是一样的,将其看做 $f_{i,y}$ ,而中间的数看成 $k$,而中间又可以…(这里同理),所以我们只需要枚举 $i$ 的所有情况即可。

那么时间复杂度就是 $O((1<<n) \times n\times n)$ 即为 $O(2^n\times n^2)$

其他看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 20;
int f[1 << N][N];
int a[N][N];

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}

memset(f, 0x3f, sizeof(f)); //得到最小值 所以起始值为最大值
f[1][0] = 0; //自己走自己是0 1的二进制就是1
for (int i = 0; i < 1 << n; i++) { //枚举所有的情况
for (int j = 0; j < n; j++) if(i >> j & 1) { //第 j 位是否走过
for (int k = 0; k < n; k++) if((i ^ 1 << j) >> k & 1) { //第 k 位是否走过,(i ^ 1 << j)的意思是 这里排除了 k == j 的情况 (自行理解)
f[i][j] = std::min(f[i][j], f[i ^ 1 << j][k] + a[k][j]); //f[i][j] 的状态是由 f[i][k] -> f[k][j]得来 而 j 是后走的 所以在前面的 i 中的 j 是没走的状态 要先去掉
}
}
}

printf("%d", f[(1 << n) - 1][n - 1]);
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!