最短Hamilton路径 — dp状态压缩详解
一般思路:
1.0->n-1一共n个数,走的顺序一共有n!种。
2.需要在枚举一下路径长度
时间复杂度极大
状态压缩思路:
1.用整数表示一个状态->f[i,j]表示从0走到j这些所有路径中存在i点的路径
2.如何把路径分成若干类? 用倒数第二个点来分类(0->第一类 1->第二类…n-1->第n类)
所有从0走到i经过了j点并且倒数第二个点是0->第一类
3.闫式dp分析法,思路就是从前往后一截一截的推,得到dp递推公式f(i-{j},k)+a(k,j)
意思就是在0-k的路径中一共i-{j}个点,在其中找最小的,加上最后一个k->j的权值即可
算法1
代码也是实现了上面所说的步骤问题,接来下进行详细解释
首先要明白建立的数组的意义,根据题意也就是20列但是要达到$10^7$长度的行的一个矩阵
for(int i=0;i<1<<n;i++)
for(int j=0;j<n;j++)
if(i>>j&1)
本句的意思就是遍历每一个状态,看i是否能到第j个点
如果可以到那么进入下一个条件
for(int k=0;k<n;k++)
if((i-(1<<j))>>k&1)
先行后列遍历节点,找到i除去j这个点是否还能到k,如果不行也就不构成上面图中的条件
如果可以到那么进入动态规划方程
cout<<f[(1<<n)-1][n-1]<<endl;
走到最后最右下的那个点就是最小路径值
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;
int n;
int w[N][N];//存放两点之间的距离
int f[M][N];//存放的dp的状态
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&w[i][j]);
memset(f,0x3f,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)//i的第j位一定存在
for(int k=0;k<n;k++)//枚举一下从哪个点转移过来
if((i-(1<<j))>>k&1)//i除去j这个点,同时第k为是1才能走到第k位
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
cout<<f[(1<<n)-1][n-1]<<endl;//n个1都走完了最终落在n-1上就是最小值
return 0;
}