动态规划法，回溯法，分支限界法求解TSP旅行商问题.docx-资料库

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第1页.png

第1页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第2页.png

第2页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第3页.png

第3页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第4页.png

第4页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第5页.png

第5页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第6页.png

第6页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第7页.png

第7页 / 共16页

2c05c4ef-1c39-4286-ab79-1d45afa16fad.docx.pdf-第8页.png

第8页 / 共16页

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧 TSP 问题算法实验报告指导教师：季晓慧姓学名：号：辛瑞乾 1004131114 提交日期： 2015 年 11 月中国地质大学（北京）

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧目录总述............................................................................................................................................2 动态规划法................................................................................................................................3 算法问题分析........................................................................................................................3 算法设计................................................................................................................................3 实现代码................................................................................................................................3 输入输出截图........................................................................................................................6 OJ 提交截图...........................................................................................................................6 算法优化分析........................................................................................................................6 回溯法........................................................................................................................................6 算法问题分析........................................................................................................................6 算法设计................................................................................................................................7 实现代码................................................................................................................................7 输入输出截图........................................................................................................................9 OJ 提交截图...........................................................................................................................9 算法优化分析......................................................................................................................10 分支限界法..............................................................................................................................10 算法问题分析......................................................................................................................10 算法设计..............................................................................................................................10 实现代码..............................................................................................................................10 输入输出截图......................................................................................................................15 OJ 提交截图.........................................................................................................................15 算法优化分析......................................................................................................................15 总结..........................................................................................................................................16 总述 TSP 问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城中国地质大学（北京）

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧市，求最短路程或最小花费，解决 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 的最短路径长度 1. 初始化第 0 列（动态规划的边界问题） for(i=1;i #include #include #include #include #include #include #include #include #include #include 中国地质大学（北京）

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧 #include #include #include #include #include #include #include #include #include #include #define debug "output for debug\n" #define pi (acos(-1.0)) #define eps (1e-8) #define inf 0x3f3f3f3f #define ll long long int #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 using namespace std; const int mod = 1000000007; const int Max = 100005; int n,mp[20][20],dp[20][40000]; int main() { while(~scanf("%d",&n)) { int ans=inf; memset(mp,0,sizeof mp); for(int i=0; i

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧 { dp[i][0]=mp[i][0]; } dp[0][mx-1]=inf; for(int j=1; j<(mx-1); j++) { for(int i=1; i0){ x=dp[k][(j-(1<<(k-1)))]+mp[i][k]; y=min(y,x); } } dp[i][j]=y; } } } dp[0][mx-1]=inf; for(int i=1;i

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧输入输出截图 OJ 提交截图算法优化分析该算法需要对顶点集合{1，2，…，n-1}的每一个子集进行操作，因此时间复杂度为 O(2^n)。和蛮力法相比，动态规划法求解 TSP 问题，把原来的时间复杂度是 O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂度，但仍需要指数时间。回溯法算法问题分析回溯法求解 TSP 问题，首先把所有的顶点的访问标志初始化为 0，然后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子树继续搜索，否则，对当前子树的兄弟结点进行搜索，如果当前结点的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。采用邻接矩阵 mp[n][n]存储顶点之间边的情况，为避免在函数间传递参数，将数组 mp 设置为全局变量，中国地质大学（北京）

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧设数组 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) 3.1、x[k]=x[k]+1，搜索下一个顶点。 3.2、若 n 个顶点没有被穷举完，则执行下列操作 3.2.1、若顶点 x[k]不在湖密顿回路上并且(x[k-1],x[k])∈E，转步骤 3.3； 3.2.2、否则，x[k]=x[k]+1,搜索下一个顶点。 3.3、若数组 x[n]已经形成哈密顿路径，则输出数组 x[n]，算法结束； 3.4、若数组 x[n]构成哈密顿路径的部分解，则 k=k+1，转步骤 3； 3.5、否则，取消顶点 x[k]的访问标志，重置 x[k],k=k-1，转步骤 3。实现代码 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug "output for debug\n" #define pi (acos(-1.0)) #define eps (1e-8) 中国地质大学（北京）

姓名：辛瑞乾学号：1004131114 指导老师：季晓慧 #define inf 0x3f3f3f3f #define ll long long int #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 using namespace std; int mp[20][20]; int x[30],vis[30]; int n,k,cur,ans; void init() { for(int i=0;i

资料库

动态规划法，回溯法，分支限界法求解TSP旅行商问题.docx

相关推荐

课程资源

热门标签

最新资料