动态规划法回溯法分支限界法求解TSP问题实验报告

TSP问题算法实验报告指导教师：季晓慧姓名：辛瑞乾学号：提交日期：2015年11月目录总述......................................................................动向规划法................................................................算法问题解析............................................................算法设计................................................................实现代码................................................................输入输出截图............................................................OJ提交截图..............................................................算法优化解析............................................................回溯法....................................................................算法问题解析............................................................算法设计................................................................实现代码................................................................输入输出截图............................................................OJ提交截图..............................................................算法优化解析............................................................分支限界法................................................................算法问题解析............................................................算法设计................................................................实现代码................................................................输入输出截图............................................................OJ提交截图..............................................................算法优化解析............................................................总结......................................................................总述TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短行程或最小开销，解决TSP可以用很多算法，比方蛮力法，动向规划法⋯详尽的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。动向规划法算法问题解析假设n个极点分别用0~n-1的数字编号，极点之间的代价存放在数组mp[n][n]中，下面考虑从极点0出发求解TSP问题的填表形式。第一，按个数为1、2、⋯、n-1的序次生成1~n-1个元素的子集存放在数组x[2^n-1]中，比如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}

。设数组

dp[n][2^n-1]

存放迭代结果，其中

dp[i][j]

表示从极点

i经过子集

x[j]

中的极点一次且一次，最后回到出发点

0的最短路径长度，动态规划法求解

TSP问题的算法以下。算法设计输入：图的代价矩阵mp[n][n]输出：从极点0出发经过所有极点一次且仅一次再回到极点0的最短路径长度初始化第0列（动向规划的界线问题）for(i=1;i<n;i++)dp[i][0]=mp[i][0]依次办理每个子集数组x[2^n-1]for(i=1;i<n;i++)if（子集x[j]中不包含i）x[j]中的每个元素k，计算d[i][j]=min{mp[i][k]+dp[k][j-1]};输出最短路径长度。实现代码#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<ctime>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<deque>#include<list>#include<set>#include<map>#include<stack>#include<queue>#include<cctype>#include<numeric>#include<iomanip>#include<bitset>#include<sstream>#include<fstream>#definedebug"outputfordebug\n"#definepi(acos)#defineeps(1e-8)#defineinf0x3f3f3f3f#definelllonglongint#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;constintMax=100005;intn,mp[20][20],dp[20][40000];intmain(){while(~scanf("%d",&n)){intans=inf;memset(mp,0,sizeofmp);for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(i==j){mp[i][j]=inf;continue;}inttmp;scanf("%d",&tmp);mp[i][j]=tmp;}}intmx=(1<<(n-1));dp[0][0]=0;for(inti=1;i<n;i++){dp[i][0]=mp[i][0];}dp[0][mx-1]=inf;for(intj=1;j<(mx-1);j++){for(inti=1;i<n;i++){if((j&(1<<(i-1)))==0){intx,y=inf;for(intk=1;k<n;k++){if((j&(1<<(k-1)))>0){x=dp[k][(j-(1<<(k-1)))]+mp[i][k];y=min(y,x);}}dp[i][j]=y;}}}dp[0][mx-1]=inf;for(inti=1;i<n;i++)dp[0][mx-1]=min(dp[0][mx-1],mp[0][i]+dp[i][(mx-1)-(1<<(i-1))]);printf("%d\n",dp[0][mx-1]);}return0;}输入输出截图OJ提交截图算法优化解析该算法需要对极点会集{1，2，⋯，n-1}的每一个子集进行操作，因此时间复杂度为O(2^n)。和蛮力法对照，动向规划法求解TSP问题，把原来的时间复杂度是O(n!)的排列问题，转变成组合问题，从而降低了算法的时间复杂度，但仍需要指数时间。回溯法算法问题解析回溯法求解TSP问题，第一把所有的极点的接见标志初始化为0，尔后在解空间树中从根节点出发开始找寻，若是从根节点到当前结点对应一个部分解，即满足上述拘束条件，则在当前结点处选择第一棵子树连续找寻，否则，对当前子树的兄弟结点进行找寻，若是当前结点的所有子树都已试一试过并且发生矛盾，则回溯到当前结点的父节点。采用毗邻矩阵mp[n][n]储藏极点之间边的情况，为防备在函数间传达参数，将数组mp设置为全局变量，设数组x[n]表示哈密顿回路经过的极点。算法设计输入:无向图G=(V,E)输出：哈密顿回路1、将极点数组x[n]初始化为0，标志数组vis[n]初始化为0；2、从极点0出发构造哈密顿回路：vis[0]=1;x[0]=1;k=1;3、While(k>=1)x[k]=x[k]+1，找寻下一个极点。、若n个极点没有被穷举完，则执行以下操作∈E，转步骤；、若数组x[n]已经形成哈密顿路径，则输出数组x[n]，算法结束；、若数组x[n]构成哈密顿路径的部分解，则k=k+1，转步骤3；、否则，取悲观点x[k]的接见标志，重置x[k],k=k-1，转步骤3。实现代码#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<ctime>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<deque>#include<list>#include<set>#include<map>#include<stack>#include<queue>#include<cctype>#include<numeric>#include<iomanip>#include<bitset>#include<sstream>#include<fstream>#definedebug"outputfordebug\n"#definepi(acos)#defineeps(1e-8)#defineinf0x3f3f3f3f#definelllonglongint#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;intmp[20][20];intx[30],vis[30];intn,k,cur,ans;voidinit(){for(inti=0;i<n;i++)for(intj=0;j<n;j++)mp[i][j]=-1;ans=-1;cur=0;for(inti=1;i<=n;i++)x[i]=i;}voiddfs(intt){if(t==n){if(mp[x[n-1]][x[n]]!=-1&&(mp[x[n]][1]!=-1)&&(cur+mp[x[n-1]][x[n]]+mp[x[n]][1]<ans||ans==-1)){for(inti=1;i<=n;i++)vis[i]=x[i];ans=cur+mp[x[n-1]][x[n]]+mp[x[n]][1];}}else{for(inti=t;i<=n;i++){if(mp[x[t-1]][x[i]]!=-1&&(cur+mp[x[t-1]][x[i]]<ans||ans==-1)){swap(x[t],x[i]);cur+=mp[x[t-1]][x[t]];dfs(t+1);cur-=mp[x[t-1]][x[t]];swap(x[t],x[i]);}}}}intmain(){while(~scanf("%d",&n)){init();for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i==j)continue;scanf("%d",&mp[i][j]);}}egin();sum+=*it;it++;sum+=*it;}returnsum/2;}intgao(nodes){intres=*2;intt1=inf,t2=inf;for(inti=1;i<=n;i++){if(![i]){t1=min(t1,mp[i][]);t2=min(t2,mp[][i]);}}res+=t1;res+=t2;inttmp;for(inti=1;i<=n;i++){tmp=inf;if(![i]){it=Mp[i].begin();res+=*it;for(intj=1;j<=n;j++)tmp=min(tmp,mp[j][i]);res+=tmp;}}return!(res%2)?(res/2):(res/2+1);}voidbfs(nodes){(s);while(!()){nodehead=();();if==n-1){intp;for(inti=1;i<=n;i++){if(![i]){p=i;break;}}intcnt=+mp[p][]+mp[][p];nodetmp=();if(cnt<={ans=min(ans,cnt);return;}else{up=min(up,cnt);ans=min(ans,cnt);continue;}}nodetmp;for(inti=1;i<=n;i++){if(![i]){=;=+mp[][i];=i;=+1;for(intj=1;j<=n;j++)[j]=[j];[i]=1;=gao(tmp);if<=up)(tmp);}}}}intmain(){while(~scanf("%d",&n)){for(inti=0;i<=n;i++)Mp[i].clear();for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i!=j){scanf("%d",&mp[i][j]);Mp[i].push_ba