《动态规划法-回溯法-分支限界法求解TSP问题实验报告16页》由会员分享，可在线阅读，更多相关《动态规划法-回溯法-分支限界法求解TSP问题实验报告16页（16页珍藏版）》请在金锄头文库上搜索。
1、姓名：辛瑞乾学号：1004131114指导老师：季晓慧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个顶点分别用0n-1的数字编号，顶点之间的代价存放在数组mpnn中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、n-1的顺序生成1n-1个元素的子集存放在数组x2n-1中，例如当n=4时，x1=1,x2=2,x3=3,x4=1,2,x5=1,3,x6=2,3,x7=1,2,3。设数组dpn2n-1存放迭代结果，其中dpij表示从顶点i经过子集xj中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。算法设计输入：图的
3、代价矩阵mpnn输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1. 初始化第0列（动态规划的边界问题）for(i=1;in;i+)dpi0=mpi02. 依次处理每个子集数组x2n-1for(i=1;in;i+)if（子集xj中不包含i）对xj中的每个元素k，计算dij=minmpik+dpkj-1;3. 输出最短路径长度。实现代码#include #include #include #include #include #include #include #include #include #include #include #include #include #incl
4、ude #include #include #include #include #include #include #include #define debug output for debugn#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 | 1using namespace std;const int mod = 1000000007;const int M
5、ax = 100005;int n,mp2020,dp2040000;int main() while(scanf(%d,&n) int ans=inf; memset(mp,0,sizeof mp); for(int i=0; in; i+) for(int j=0; jn; j+) if(i=j) mpij=inf; continue; int tmp; scanf(%d,&tmp); mpij=tmp; int mx=(1(n-1); dp00=0; for(int i=1; in; i+) dpi0=mpi0; dp0mx-1=inf; for(int j=1; j(mx-1); j+
6、) for(int i=1; in; i+) if(j&(1(i-1)=0) int x,y=inf; for(int k=1; kn; k+) if(j&(10) x=dpk(j-(1(k-1)+mpik; y=min(y,x); dpij=y; dp0mx-1=inf; for(int i=1;in;i+) dp0mx-1=min(dp0mx-1,mp0i+dpi(mx-1)-(1=1)3.1、xk=xk+1，搜索下一个顶点。3.2、若n个顶点没有被穷举完，则执行下列操作3.2.1、若顶点xk不在湖密顿回路上并且(xk-1,xk)E，转步骤3.3；3.2.2、否则，xk=xk+1,搜索下一
7、个顶点。3.3、若数组xn已经形成哈密顿路径，则输出数组xn，算法结束；3.4、若数组xn构成哈密顿路径的部分解，则k=k+1，转步骤3；3.5、否则，取消顶点xk的访问标志，重置xk,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 #de
8、fine debug output for debugn#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 | 1using namespace std;int mp2020;int x30,vis30;int n,k,cur,ans;void init() for(int i=0;in;i+) for(int j=0;jn;j+) mpij=-1; ans=-1;cur=0; for(int i=1;i=n;i+)xi=i;void dfs(int t) if(t=n) if(mpxn-1xn!=-1&(mpxn1!=-1)&(cur+mpxn-1xn+mpxn1ans|ans=-1) for(int i=1;i=n;i+) visi=xi;
