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

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个顶点分别用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问题的算法如下。算法设计输入：图的代价矩阵mpnn输出：从顶点0出发经过所有顶点一次且仅

3、一次再回到顶点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 #include #include #include #incl

4、ude #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 Max = 100005;int n,mp2020,dp

5、2040000;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+) for(int i=1; in; i+) if(j

6、&(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,搜索下一个顶点。3.3、若数组xn已经形成哈密顿路径，则输出数

7、组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 #define debug output for debug

8、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 | 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

9、=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; ans=cur+mpxn-1xn+mpxn1; else for(int i=t;i=n;i+) if(mpxt-1xi!=-1&(cur+mpxt-1xians|ans=-1) swap(xt,xi); cur+=mpxt-1xt; dfs(t+1); cur-=mpxt-1xt; swap(xt,xi); int main() while(scanf(%d,&n)

10、 init(); for(int i=1; i=n; i+) for(int j=1; j=n; j+) if(i=j) continue; scanf(%d,&mpij); /puts(YES); dfs(2); coutansendl; return 0;输入输出截图OJ提交截图算法优化分析在哈密顿回路的可能解中，考虑到约束条件xi!=xj(1=I,j=n,i!=j),则可能解应该是（1,2,n）的一个排列，对应的解空间树种至少有n!个叶子结点，每个叶子结点代表一种可能解。当找到可行的最优解时，算法停止。分支限界法算法问题分析分支限界法解决TSP问题首先确定目标函数的界down,up，可以

11、采用贪心法确定TSP问题的一个上界。如何求得TSP问题的一个合理的下界呢？对于无向图的代价矩阵，吧矩阵中每一行最小的元素想家，可以得到一个简单的下界，但是还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加在除以2，假设图中所有的代价都是整数，再对这个结果向上取整，就得到一个合理的下界。需要强调的是，这个解可能不是一个可行解（可能没有构成哈密顿回路），但给出了一个参考下界。一般情况下，假设当前已确定的路径为U=(r1,r2,rk),即路径上已确定了k个顶点，此时，该部

12、分解的目标函数值的计算方法（限界函数）如下：Lb=（2crir(i+1)+ri行不在路径上的最小元素+ri行最小的两个元素）/2算法设计输入：图G=(V,E)输出：最短哈密顿回路1、 根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2、 计算根节点的目标函数值并加入待处理结点表PT；3、 循环知道某个叶子结点的目标函数值在表PT中取得极小值3.1、i=表PT中具有最小值的结点；3.2、对结点i的每个孩子几点x执行下列操作：3.2.1估算结点x的目标函数值lb；3.2.2若（lb=up），则将结点x加入表PT中；否则丢弃该结点；4、将叶子结点对应的最优解输出，回溯求得最优解的各个

13、分量。实现代码#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 debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f3f#define ll

14、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 Max = 100005;/*/vectorMp20;vector:iterator it;int mp2020;int vis20;int up,low,n,ans;struct node int x20,st,ed,dis,val,num; bool operator(const node &p)const return valp.val

15、; ;priority_queueq;int getup(int u,int v,int w) if(v=n) return w+mpu1; int sum=inf,p; for(int i=1; impui) sum=mpui; p=i; visp=1; return getup(p,v+1,w+sum);int getlow() int sum=0; for(int i=1; i=n; i+) it=Mpi.begin(); sum+=*it; it+; sum+=*it; return sum/2;int gao(node s) int res=s.dis*2; int t1=inf,t

16、2=inf; for(int i=1; i=n; i+) if(!s.xi) t1=min(t1,mpis.st); t2=min(t2,mps.edi); res+=t1; res+=t2; int tmp; for(int i=1; i=n; i+) tmp=inf; if(!s.xi) it=Mpi.begin(); res+=*it; for(int j=1; j=n; j+) tmp=min(tmp,mpji); res+=tmp; return !(res%2) ? (res/2):(res/2+1);void bfs(node s) q.push(s); while(!q.emp

17、ty() node head=q.top(); q.pop(); if(head.num=n-1) int p; for(int i=1; i=n; i+) if(!head.xi) p=i; break; int cnt=head.dis+mpphead.st+mphead.edp; node tmp=q.top(); if(cnt=tmp.val) ans=min(ans,cnt); return; else up=min(up,cnt); ans=min(ans,cnt); continue; node tmp; for(int i=1; i=n; i+) if(!head.xi) tm

18、p.st=head.st; tmp.dis=head.dis+mphead.edi; tmp.ed=i; tmp.num=head.num+1; for(int j=1; j=n; j+) tmp.xj=head.xj; tmp.xi=1; tmp.val=gao(tmp); if(tmp.val=up) q.push(tmp); int main() while(scanf(%d,&n) for(int i=0; i=n; i+) Mpi.clear(); for(int i=1; i=n; i+) for(int j=1; j=n; j+) if(i!=j) scanf(%d,&mpij); Mpi.push_back(mpij); else mpij=inf; sort(Mpi.begin(),Mpi.end(); memset(vis,0,sizeof vis); vis1=1;