TSP:给定n个点,m条无向边,每条边有一个权值代表两个点之间的距离,现在要求把每一个点都走一遍并回到原点,求路径的最短值。
对于现在走到的点i,它前面会有k给点,后面有s个点,那么与最短路有关的就是后面s给点应该如何走,而前面的k个点,我们只需记录走过这几个点所需的最短路。
那么就可以用状压dp,比方说现在走到i点,01串用来代表之前走过的状态,比如n=7,i=2,01串(我们叫它st好了)是0011010,就代表2、4、5点是走过的(走过的点标1,一开始的状态就应该全是0),其中现在处在点2。那么dp[st][i]就应该表示此时在i点,状态为st时走过的最短路。
上图的黄色和绿色线分别对应两种不同的路径,我们会发现,对于每一条路,所有点都是要经过的,那么其实起点选哪个都没有关系,因为在一条路径里所有点的地位应该是相同的,从1出发,会首先把剩余四个点都走完,再从最后一个点回到1;从2或3、4、5出发,思路是相同的,而且他们走过的路径是一样的,所以我说从哪个点开始都没有关系。
既然如此,就不妨从点1开始吧!
既然是dp,那么就应该有递推,我们可以从最后的状态开始讨论(很正常的思路)。
最后的状态是:刚好把所有点都踩了一遍,然后来到了点k(k!=1),如果k与1之间存在边的话,就连在一起,路就走完了,那么这个状态就是合法的,将这条路对应的最短路径加上该点到点1的路径长度,与ans进行比较,进行更新就可以了。
如果k与1之间没有边的话,这个状态就是非法的,排除。

接下来,我们可以用记忆化搜索,先定义一个st=111...1(n个1),代表所有点都踩过的情况,
然后用i从1到n循环,与ans进行对比的就是f[st][i]+mas[i][1],最后输出ans即可。
现在唯一的问题就是如何递推来求f[st][i]。
st当中第i位一定是1,代表第i点走过了,我们要求f[st][i]的话,得先还原出到达i点之前的状态,也就是把第i位变成0,得到st1(原状态)。
然后,对于剩下的st当中为1的点(代表来到第i点之前已经走过的点),如果它们与点i有边连接的话,就可以通过求出dp[st1][j]+mas[j][i](j代表之前走过,现在枚举到的点),并通过横向对比,来求出最小值作为f[st][i]即可。
部分细节放在代码里:(代码末有测试样例,答案应为17(可以自己手搓))
#include<bits/stdc++.h> using namespace std; #define ll long long ll f[(1<<20)+10][25];//st状态下停在i点的最短路; ll mas[23][23]; ll n,m,x,y,z; ll deal(ll st,ll x)//记忆化搜索 { if(f[st][x]!=0x3f3f3f3f3f3f3f3f) //代表已经被处理过了; return f[st][x]; ll st1=st-(1<<(x-1));//来到这一点前的状态,也就是第x个点还没有走过 for(int i=1;i<=n;++i){ if(mas[i][x]==0) continue; if((st>>(i-1))&1){ f[st][x]=min(f[st][x],deal(st1,i)+mas[i][x]); } } return f[st][x]; } int main() { cin>>n>>m;//n个点,m条边 for(int i=1;i<=m;++i){ cin>>x>>y>>z; mas[x][y]=z; mas[y][x]=z;//无向边 } memset(f,0x3f,sizeof f);//初始化 f[1][1]=0;//初始化,?????????? ll st=(1<<n)-1;//n位全部变成1,代表此时n个点都踩完了。 ll ans=1e12; for(int i=2;i<=n;++i){ int tmp=deal(st,i); if(mas[i][1]!=0) ans=min(ans,tmp+mas[i][1]); } cout<<ans<<endl; return 0; } /* 样例: 5 9 1 2 2 1 3 7 1 4 2 1 5 4 2 3 10 2 4 6 2 5 3 3 4 4 4 5 1 */
讯享网
这其实用了很经典的状压思路,将所有状态压缩成01串来表示,通常用于状态数不大的情况。
下面给出一道例题(也是状压的思路)
看这里
讯享网#include<bits/stdc++.h> using namespace std; #define ll long long ll n,s; ll mas[20]; ll dp[20][(1<<18)+10];//状态为j且队尾为i的情况下可行的方案数 int main() { cin>>n>>s; for(int i=1;i<=n;++i) cin>>mas[i]; for(int i=1;i<=n;++i) dp[i][1<<(i-1)]=1; //初始化 for(ll i=0;i<(1<<n);++i){ for(int j=1;j<=n;++j){ if(i&(1<<(j-1))){ for(int k=1;k<=n;++k){ if((i&(1<<(k-1)))) continue; if(abs(mas[j]-mas[k])<=s) continue; dp[k][i+(1<<(k-1))]+=dp[j][i]; } } } } ll ans=0; for(int i=1;i<=n;++i){ ans+=dp[i][(1<<n)-1]; } cout<<ans<<endl; return 0; }


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/112315.html