题目

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

考点

状态压缩 ， dp问题 ，np问题 ，图论

Hamilton路径

定义：从 0到 n−1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。
接下来 n行每行 n 个整数，其中第 i行第 j个整数表示点 i到 j的距离（记为 a[i,j]）。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

分析思路

  1. 主要思路：已知起点0和终点n-1，中间不管怎么走都会选取权重之和最短的情况。假设还没走到终点，将前一个位置当作终点，假设每一个点为终点的情况。以这个思路遍历所有位置，不断更新,最终得出答案。
  2. dp思路：（1）状态压缩：用二进制来表示要走的所以情况的路径,这里用i来代替
    （2）状态表示：f[i][j]:所有从0走到j,走过的所有点的情况是i的所有路径
    （3）状态计算：表示为利用0到k再到j中 k的所有情况 进行状态转移
    （4）状态方程：f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j])
    （5）对方程进行解释：取min，利用去除j位置权重且能到达k位置的集合加上k点到j点的权重 完成转移。

代码

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

const int N = 20,M = 1 << N;
int n;
//f[i][j]为状态数组：表示所有从0走到j,走过所有点的情况是i的所有路径
//w[i][j]为带权无向图的矩阵
int f[M][N],w[N][N];

int main()
{
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            cin >> w[i][j];
        }
    }
    
    memset(f,0x3f3f3f,sizeof f);
    f[1][0] = 0;
    
    for(int i = 0;i < 1 << n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(i >> j & 1) //判断是否经过了j点
            {
                //经过了j点遍历k，k表示走到j这个点之前,以k为终点的最短距离
                for(int k = 0;k < n;k++)
                {
                    //这个判断是为了得知i这个情况里有没有包含k位置
                    //如果包含k位置 则 进行状态转移
                    if(i >> k & 1)
                    {
                        //i - (1 << j) 表示除去j位置的集合
                        //dp更新最短距离 
                        //f[i - (1 << j)][k] + w[k][j]除去j位置的集合到k的距离加上k位置到j位置的权重
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
                    }
                }
            }
        }
    }
    //因为是从0开始所以要-1
    //输出f[(1 << n) - 1][n - 1]表示遍历完了所有点终点是最后一个点的最短距离
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}