题目描述

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

思路解析

状态定义

$f(i,j)\;(0≤i≤2^n,0≤j<n)$ 表示 “点被经过的状态” 对应的二进制数为 $i$ ，且目前处于点 $j$ 时的最短路径。

状态计算

对于 $f(i,j)$，即当前时刻 “被经过的点的状态” 对应的二进制数为 $i$ ，处于点 $j$（此时状态 $i$ 的二进制位的第 $j$ 位应该为 $1$ ，即 $(i\gg j)\;\&\;1 = 1$）。

因为 $j$ 只能被恰好经过一次，所以一定是当前时刻经过，故上一次 “被经过的点的状态” 对应的二进制数的第 $j$ 位应该为 $0$，即 $i\oplus(1\ll j)=1$。另外上一次所处的位置可能是 $i\oplus(1\ll j)=1$ 中任意一个是 $1$ 的数位 $k$，从 $k$ 走到 $j$ 需经过 $weight(k,j)$ 的路程，考虑所有这样的 $k$ 取最小值。

总结来说，对于当前点 $j$ ，找一个状态，再找一个中间点 $k$，更新 $k$ 点 到 $j$ 点的最短路，该状态要满足 $j$ 点的状态中 $j$ 点被走过，$k$ 点的状态 $j$ 点没被走过、$k$ 点被走过。

$f(i,j)=\min\{f(i\oplus(1 \ll j),k)+weight(k,j)\},\; 0≤k<n,\;((i \gg j) \;\&\; 1) = 1$

初始条件

在起点时，有 $f(1,0)=0$ ，即只经过点 $0$ （ $i$ 只有第 $0$ 位为 $1$ ），目前处于起点 $0$ ，最短路长度为 $0$ 。方便起见，将 $f$ 其他值初始化为无穷大

最终结果

$f(2^n-1,n-1)$，即经过所有点（ $i$ 的所有位都是 $1$ ），处于终点 $n-1$ 的最短路。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20, M = 1 << N;

int n, weight[N][N];
int f[M][N];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> weight[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    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 ^ 1 << j) >> k & 1) {
                f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + weight[k][j]);
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1];
    return 0;
}

复杂度分析

• 时间复杂度 $O(n^2*2^n)$
• 空间复杂度 $O(n*2^n)$