《算法竞赛进阶指南》 91. 最短Hamilton路径

本文主要是介绍《算法竞赛进阶指南》 91. 最短Hamilton路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接（经典问题，无原题链接）

• 是否看了题解找思路

1.问题分析

0.原题：
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

1.暴力做法（dfs爆搜）
用dfs搜索卡在了n=15上，但是好像有人dfs可以AC，应该是我剪枝没剪好。
2.状态压缩dp的复习
分析题目可知，每种情况可用二进制的状态表示。
动态规划的分析：（1）.dp[state][j]表示状态为state，最终落在j点上的最小值。例如：经过0（必须经过0点），1，4三点，最终停在2点上的状态表示为dp[10011][2]——错误！该状态不合法；dp[10111][2]——正确！
（2）.集合的划分：暴力枚举所有点，不断更新。

2.具体代码

//暴力dfs
#include <iostream>using namespace std;
const int N = 21;
int data[N][N];
int n,sum,ans,path[N];
bool vis[N];
void dfs(int u,int d)
{if(d==n&&path[d-1]==n-1){ans=min(ans,sum);}else if(path[d-1]!=n-1){vis[u]=true;for(int i=0;i!=n;i++){if(!vis[i]){sum+=data[u][i];path[d]=i;dfs(i,d+1);sum-=data[u][i];}}vis[u]=false;}
}
int main()
{cin>>n;ans=0x3f3f3f3f;for(int i=0;i!=n;i++)for(int j=0;j!=n;j++)cin>>data[i][j];dfs(0,1);cout<<ans;return 0;
}

//状态压缩dp
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 20,M= 1<<20;
int w[N][N],n;
int dp[M][N];
int main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>w[i][j];memset(dp,0x3f,sizeof dp);dp[1<<0][0]=0;for(int i=1;i<(1<<n);i++)//枚举所有状态for(int j=0;j<n;j++)//遍历所有点{if((i>>j & 1))//判断当前状态是否经过了j点for(int k=0;k<n;k++)//如果当前状态经过了j点，则以j为基础，遍历所有点{if((i^(1<<j)) >> k & 1)//难点！ 单独总结dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);}}cout<<dp[(1<<n)-1][n-1]<<endl;return 0;
}

3.总结

(i^(1<<j)) >> k & 1
判断i^(1<<j)状态含k点，
确保dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);操作合法
当前i状态是从i^(1<<j)转移来的

这篇关于《算法竞赛进阶指南》 91. 最短Hamilton路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---