状态压缩动态规划：最短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

样例输入 #1

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

样例输出 #1

18

提示

【数据范围】

$1\le n\le 20$，

$0\le a[i,j]\le 10^7$

算法思想

根据题目描述，$Hamilton$路径的定义是从 $0$ 到 $n?1$ 不重不漏地经过每个点恰好一次，求最短$Hamilton$路径的长度。

从数据范围来看，$1\le n\le 20$，点非常少，可以考虑使用状态压缩的方式表示每个点是否经过。例如，有$5$个点，经过了点$0、2、3$，其状态的二进制形式为$(01101{)}_2$

状态表示

$f[state][i]$表示从起点走到$i$点时，并且经过点的状态为$state$的情况下，最短$Hamilton$路径的长度。

最终结果为$f[2^n?1][n?1]$。

状态计算

计算$f[state][i]$可以根据最后一步走到$i$点的情况分成若干类。

不妨设上一点为$j$，那么$f[state][i]$应该为不包含$i$的状态走到$j$点的最短路径长度，再加上$a[j][i]$，即
f [ s t a t e ] [ i ] = m i n { f [ s t a t e ? ( 1 < < i ) ] [ j ] + a [ j ] [ i ] } f[state][i]=min\{f[state-(1<<i)][j]+a[j][i]\} f[state][i]=min{f[state?(1<<i)][j]+a[j][i]}

注意：计算$f[state][i]$前提是状态$state$已经包含了$i$点和$j$点。

初始状态

• 题目中求最短路径长度，状态应初始化为无穷大。
• 从$0$点出发，因此$f[1][0]=0$

时间复杂度

• 状态数为$2^n\times n$
• 状态计算过程中要枚举所有能到达$i$的点$j$，时间复杂度为$O(n)$

总的时间复杂度为$O(n^2\times 2^n)=400\times 1048576=419,430,400$

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << 20, INF = 0x3f3f3f3f;
int a[N][N], f[M][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> a[i][j];
    //初始状态
    memset(f, 0x3f, sizeof f);       
    f[1][0] = 0;
    //状态计算
    for(int state = 0; state < 1 << n; state ++)
    {
        for(int i = 0; i < n; i ++)
        {
            //状态中包含i点
            if(state >> i & 1)
            {
                //枚举i的上一点j
               for(int j = 0; j < n; j ++)
               {
                   //状态中包含j
                   if((state >> j & 1) && i != j)
                        f[state][i] = min(f[state][i], f[state - (1 << i)][j] + a[j][i]);
               }
            }
        }
    }
    
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}