[Shortest Hamilton path]

发表于 | 更新于 | 分类于 ， ，
本文字数： 12k

链接

\(\text{最短Hamilton路径}\)

题意

  给定一张\(n\)个点的带权无向图，点从\(0\)到\(n-1\)标号，求起点\(0\)到终点\(n-1\)的最短\(\text{Hamilton}\)路径。 \(\text{Hamilton}\)路径的定义是从\(0\)到\(n-1\)不重不漏地经过每个点恰好一次。

  输入格式：第一行一个整数\(n\)，接下来一个\(n\times n\)的矩阵\(a[i,j]\)，代表图中点与点之间的关系;

  数据范围：\(1\leq n\leq 20,0\leq a[i,j]\leq 10^7\).

  输出格式：输出一个整数，表示最短\(\text{Hamilton}\)路径的长度。

分析

  首先很容易想到一种方法，枚举\(n\)个点的排列，然后计算最小值，那么复杂度是\(O(n\ast n!)\)，然而\(20!\)大约是\(2e18\)，显然不可行；之后不知什么人想出来一种比较巧妙的方法。

  考虑使用二进制表示状态，从一个点转移到另一个点，两个点之间的状态转移的差距，体现在二进制上仅仅是一位不同；

  使用一个\(n\)位二进制数，若第\(i(0\leq i< n)\)位为\(1\)，则表示第\(i\)个点已经被访问过了，反之未被访问过，在任意时刻还需要知道当前所在的位置，所以使用\(f[i,j](0\leq i<2^n,0\leq j<n)\)表示点被经过的状态对应的二进制数为\(i\)，且目前处于点\(j\)时的最短路径。

  在起点\(0\)时，有\(f[1][0]=0\)(\(0\)点的状态是\(1\))，其他设为\(\infty\)，目标是\(f[(1<< n)-1][n-1]\)，即经过所有点(\(i\)的所有位都为\(1\))，并且最终位于\(n-1\)位置，动态转移方程为： \[f[i][j]=\min{f[i\space xor(1 << j)][k]+weight[k][j]}\]   枚举当前的位置和当前位置的前一个位置，复杂度为\(O(n^2 \ast 2^n)\).

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 1000005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

int n, m, f[(1 << 21) - 1][25], e[25][25];
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    while (scanf("%d", &n) != EOF) {
        memset(f, INF, sizeof(f));
        f[1][0] = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                e[i][j] = read();
        for (int i = 1; i < 1 << n; i++)
            for (int j = 0; j < n; j++)
                if (i >> j & 1)
                    for (int k = 0; k < n; k++) 
                        if (i >> k & 1)
                            f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + e[j][k]);
        printf("%d", f[(1 << n) - 1][n - 1]);
    }
}