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

《动态规划法,回溯法,分支限界法求解TSP问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、TSP问题算法实验报告指导教师：季晓慧姓名：辛瑞乾学号：1004131114提交日期：2015年11月目录总述2动态规划法2算法问题分析2算法设计2实现代码2输入输出截图5OJ提交截图5算法优化分析5回溯法5算法问题分析5算法设计6实现代码6输入输出截图8OJ提交截图8算法优化分析9分支限界法9算法问题分析9算法设计9实现代码9输入输出截图14OJ提交截图14算法优化分析14总结15总述TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮

2、力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。动态规划法算法问题分析假设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^

3、n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。算法设计输入：图的代价矩阵mp[n][n]输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1.初始化第0列（动态规划的边界问题）for(i=1;i

4、{mp[i][k]+dp[k][j-1]};3.输出最短路径长度。实现代码#include#include#include#include#include#include#include#include#include#include#include#include#include

5、e#include#include#include#include#include#include#definedebug"outputfordebug"#definepi(acos(-1.0))#defineeps(1e-8)#defineinf0x3f3f3f3f#definelllonglongint#definelsonl,m,rt<<1#definersonm+1,r,rt<<1

6、1usin

7、gnamespacestd;constintmod=1000000007;constintMax=100005;intn,mp[20][20],dp[20][40000];intmain(){while(~scanf("%d",&n)){intans=inf;memset(mp,0,sizeofmp);for(inti=0;i

8、intmx=(1<<(n-1));dp[0][0]=0;for(inti=1;i0){x=dp[k][(j-(1<<(k-1)))]+mp[i][k];y=min(y,x);}}dp[i][j]=y;}}}d

9、p[0][mx-1]=inf;for(inti=1;i