最短 Hamilton 路径

状态压缩 + 动态规划 典型例题

https://www.acwing.com/problem/content/93/

给定一张 $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≤n≤20$
$0≤a[i,j]≤10^7$

输入样例

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

输出样例

18

题解

状态表示

$dp(i,j):=$ 从节点 $0$ 走到节点 $j$，经过的节点状态为 $i$ 的所有路径的距离的最小值。

$dis(i,j):=$ 从节点 $i$ 走到节点 $j$ 的距离。

对于经过的节点状态为 $i$，我们采用状态压缩的方式来表示它：$i$ 为一个 $20$ 位二进制数，其第 $n$ 位的状态代表是否走过第 $n$ 个点。

举例来说，若 $i=0100,0000,0000,0000,0011_b$，则代表经过了第 $0,1,18$ 个点，其他点没有经过。

状态转移

令节点 $j$ 的前一个节点为 $k$，即路径为：$0\rightarrow k\rightarrow j$

那么可知：$dp(i,j)=dp(i-\{j\},k)+dis(k,j)$

由于 $dp(i,j)$ 储存的是最小值，因此对于 $k=0,1,\dots,n-1$，取所有答案的最小值即可。

初值

$dp(1,0)=0$：从 $0$ 走到 $0$，距离为 $0$，经过了第 $0$ 个点，因此 $i=1,j=0,dp(i,j)=0$

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 16;
int n;
int a[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

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

重点解析

从上面的第 $18$ 行开始

代码解析
for (int i = 0; i < 1 << n; i++)枚举所有的 $i$ 情况
for (int j = 0; j < n; j++)枚举所有的 $j$ 情况
if (i >> j & 1)筛去不合法情况（从 $0$ 走到 $j$，$i$ 中一定包含 $j$）
for (int k = 0; k < n; k++)枚举所有的 $k$ 情况
if ((i - (1 << j)) >> k & 1)筛去不合法情况（从 $0$ 走到 $k$，$i-\{j\}$ 中一定包含 $k$）
dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + a[k][j]);状态转移，取最小值