计算机算法设计与分析 旅行售货员问题

量子计算研究：理论上能解决传统计算机无法处理的复杂问题。 #生活知识# #科技生活# #科技改变生活# #科技创新趋势分析#

旅行售货员问题需要用到分支限界法，分支限界法可以理解为广搜加剪枝。

针对这个题，需要用到这样几个变量：Map数组存放整个题目的地图，Node记录广搜过程中的每个状态，这个结构体中，root数组记录从出发点到当前状态经过的路线，dis记录目前状态下的可能最优值，f记录目前遍历了几个城市，tar记录有哪几个城市已经遍历过了。

其中dis记录的可能最优值需要解释一下，这个值是由两部分组成，第一部分是已经确定的路线的距离，这部分是当前状态下已经确定了的，第二部分是剩下城市的可能最优解，这部分并不一定是符合条件的答案，只是当前状态下最小的距离，在求这个值的时候，从目前状态的点开始，当前点的下一个点不能是自己和已经走过的点，之后的点只能走没走过的点或者返回出发点。
拿第一个子节点来说，它当前走到了2这个点，已经确定的第一部分是1-2这段路线，所以14是确定的，之后看不确定部分，从V2离开，不能走自己也不能走已经走过的点，所以从345里面选最小距离，其余点的情况，只能走没走过的点或返回第一个点，所以V3只能选145的最小距离，这样确定dis的值。

确定好dis后，只需要用优先队列，每次取出dis最小的节点，当已经有四个点是确定的时候，整个路线就确定了，可以得到一个符合条件的路线距离值，记录这个值，前面计算的dis在这时可以用来剪枝，当剩下这条路最小值都比这个已经确定的值还大，那就没有继续走下去的必要，直接剪除。最后取所有符合条件的值的最小值即可。

代码如下：

#include<bits/stdc++.h> using namespace std; int N; int Map[1005][1005]; int Min[1005]; int ans=0x3f3f3f; struct Node{int root[1005];int dis;int f;int tar[1005];friend bool operator < (struct Node a,struct Node b){return a.dis>b.dis;} }; void bfs() {priority_queue< Node >q;struct Node n;n.f=1;n.root[1]=1;n.dis=0;n.tar[1]=1;for(int i=1;i<=N;i++)n.dis+=Min[i];q.push(n);while(!q.empty()){struct Node temp=q.top();q.pop();if(temp.dis>ans)continue;for(int i=1;i<=N;i++){if(temp.tar[i]==1)continue;struct Node t;t.f=temp.f+1;for(int j=0;j<=N;j++){t.tar[j]=temp.tar[j];t.root[j]=temp.root[j];}t.tar[i]=1;t.root[t.f]=i;t.dis=0;for(int j=1;j<t.f;j++){t.dis+=Map[t.root[j]][t.root[j+1]];}int tempmin=0x3f3f3f;for(int j=1;j<=N;j++){if(t.tar[j]==1)continue;tempmin=min(tempmin,Map[i][j]);}t.dis+=tempmin;for(int j=1;j<=N;j++){if(t.tar[j]==1)continue;tempmin=Map[j][1];for(int k=2;k<=N;k++){if(t.tar[k]==1||k==j)continue;tempmin=min(tempmin,Map[j][k]);}t.dis+=tempmin;}if(t.f==N-1)ans=min(ans,t.dis);q.push(t);}} } int main() {while(scanf("%d",&N)!=EOF){memset(Min,-1,sizeof(Min));for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){scanf("%d",&Map[i][j]);if(Map[i][j]==0)continue;if(Min[i]==-1)Min[i]=Map[i][j];elseMin[i]=min(Min[i],Map[i][j]);}bfs();printf("%d\n",ans);}return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114

测试用例：
输入
5
0 14 4 10 20
14 0 7 8 7
4 5 0 7 16
11 7 9 0 2
18 7 17 4 0
输出
30

网址：计算机算法设计与分析 旅行售货员问题 https://www.yuejiaxmz.com/news/view/433275

相关内容

算法设计与分析
【算法设计与分析】递推算法
计算机算法设计与分析（第二章上机实践题）
计算机网络安全问题分析与防护措施研究
java计算机毕业设计宠物管理系统（开题+程序+论文）
Matlab数据分析与多项式计算
分布式计算、统计学习与ADMM算法
建筑给水设计秒流量计算方法分析
算法分析之计数与渐进分析
常用计算机维修方法有哪些,计算机常见硬件故障的诊断及其处理分析

随便看看