最短Hamilton路径

更好的阅读体验: https://www.cnblogs.com/Acapplella/p/13544964.html

题目描述

给定一张 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]≤

输入样例

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

思路

首先想下暴力算法，这里直接给出一个例子。
比如数据有 5 个点，分别是 0,1,2,3,4
那么在爆搜的时候，会枚举一下六种路径情况（只算对答案有贡献的情况的话）：

• case 1: 0→1→2→3→4
• case 2: 0→1→3→2→4
• case 3: 0→2→1→3→4
• case 4: 0→2→3→1→4
• case 5: 0→3→1→2→4
• case 6: 0→3→2→1→4

那么观察一下 case 1 和 case 3，可以发现，我们在计算从点 0 到点 3 的路径时，其实并不关心这两中路径经过的点的顺序，而是只需要这两种路径中的较小值，因为只有较小值可能对答案有贡献。
所以，我们在枚举路径的时候，只需要记录两个属性：当前经过的点集，当前到了哪个点。
而当前经过的点集不是一个数。观察到数据中点数不会超过 20，我们可以用一个二进制数表示当前经过的点集。其中第 i 位为 1/0 表示是/否经过了点 i。
然后用闫式 dp 分析法考虑 dp
状态表示：f[i][j]。其中 i 是一个二进制数，表示点集的方法如上述所示。

• 集合：经过的点集为 i ,且当前到了点 j 上的所有路径。
• 属性：路径总长度的最小值。

状态计算：假设当前要从点 k转移到 j。那么根据 Hamilton 路径的定义，走到点 k 的路径就不能经过点 j，所以就可以推出状态转移方程
f[i][j] = min{f[i-(1 << j)][k] + weight[k][j]}
其中weight[k][j]表示从点 k 到点 j 的距离。
所有状态转移完后，根据 f[i][j] 的定义，要输出 f[111⋯11((n−1)个1)][n−1]。
那么怎么构造 n - 1 个 1 呢，可以直接通过 1 << n 求出 100⋯0((n−1)个0)，然后减一即可。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20,M=1<<20;//一共有2的20次方种情况
int f[M][N],weight[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>weight[i][j];//输入点i与点j之间的距离
        }
    }
    memset(f,0x3f,sizeof(f));//由于要求最小值，所以这里将 f 初始化为正无穷会更好处理一些(注意:memset函数是按照字节进行赋值的)
    f[1][0]=0;//由于题目要求0点为起始点，所以0 -> 0的距离长度为0。对其初始化后方便接下来递推的过程。
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)//枚举当前所在的点
        {
            if(i>>j&1)//判断路径i中是否包括当前点j,如果包括当前点，则可以进行状态转移(注意: >>运算符的优先级高于&运算符的优先级，所以(i>>j)&1可以写成i>>j&1)
            {
                //要完成点k到点j的转移，所以要来枚举k。
                for(int k=0;k<n;k++)
                {
                    if(i-(1<<j)>>k&1)//只有去除掉点j后路线中仍然包含点k才能说明路线是在点k的基础上向点j转移的（注意:算术运算符的优先级大于位运算符的优先级）
                    {
                        f[i][j]=min(f[i-(1<<j)][k]+weight[k][j],f[i][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1]<<endl;//由于题目要求计算从点n到点n-1的路径长度，所以(1<<n)-1的二进制形式为111...111[共有(n-1)个1].
    /*
       f[i][j]中
       i的含义是当前的路径(eg:5的二进制形式为101，表示路径经过点0和点2，不经过点1)
       j的含义是当前路径的终点
    */
    return 0;
}