本文主要是介绍《算法竞赛进阶指南》 91. 最短Hamilton路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
《算法竞赛进阶指南》 91. 最短Hamilton路径
- 1.问题分析
- 2.具体代码
- 3.总结
题目链接(经典问题,无原题链接)
- 是否看了题解找思路
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路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!