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

1、精选优质文档-倾情为你奉上TSP问题算法实验报告指导教师： 季晓慧 姓 名： 辛瑞乾 学 号：提交日期： 2015年11月 目录总述TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。动态规划法算法问题分析假设n个顶点分别用0n-1的数字编号，顶点之间的代价存放在数组mpnn中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、n-1的顺序生成1n-1个元素的子集存放在数组x2n-1中，例如当n=4时

2、，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出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1. 初始化第0列（动态规划的边界问题）for(i=1;i<n;i+)dpi0=mpi02. 依次处理每个子集数组x2n-1for(i=1;i<n;i+)if（子集xj中不包含i）对xj中的每个元素k，计算dij=minmpik+dpk

3、j-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>#incl

4、ude <map>#include <stack>#include <queue>#include <cctype>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#define debug "output for debugn"#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f

5、3f3f3f#define ll long long int#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1using namespace std;const int Max = ;int n,mp2020,dp2040000;int main() while(scanf("%d",&n) int ans=inf; memset(mp,0,sizeof mp); for(int i=0; i<n; i+) for(int j=0; j<n; j+) i

6、f(i=j) mpij=inf; continue; int tmp; scanf("%d",&tmp); mpij=tmp; int mx=(1<<(n-1); dp00=0; for(int i=1; i<n; i+) dpi0=mpi0; dp0mx-1=inf; for(int j=1; j<(mx-1); j+) for(int i=1; i<n; i+) if(j&(1<<(i-1)=0) int x,y=inf; for(int k=1; k<n; k+) if(j&(1<<(

7、k-1)>0) x=dpk(j-(1<<(k-1)+mpik; y=min(y,x); dpij=y; dp0mx-1=inf; for(int i=1;i<n;i+) dp0mx-1=min(dp0mx-1,mp0i+dpi(mx-1)-(1<<(i-1); printf("%dn",dp0mx-1); return 0;输入输出截图OJ提交截图算法优化分析该算法需要对顶点集合1，2，n-1的每一个子集进行操作，因此时间复杂度为O(2n)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂度是O(n!)的排列问题，转化为组合问题，

8、从而降低了算法的时间复杂度，但仍需要指数时间。回溯法算法问题分析回溯法求解TSP问题，首先把所有的顶点的访问标志初始化为0，然后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子树继续搜索，否则，对当前子树的兄弟结点进行搜索，如果当前结点的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。采用邻接矩阵mpnn存储顶点之间边的情况，为避免在函数间传递参数，将数组mp设置为全局变量，设数组xn表示哈密顿回路经过的顶点。算法设计输入:无向图G=(V,E)输出：哈密顿回路1、 将顶点数组xn初始化为0，标志数组visn初始化为

9、0；2、 从顶点0出发构造哈密顿回路：vis0=1;x0=1;k=1;3、 While(k>=1)3.1、xk=xk+1，搜索下一个顶点。3.2、若n个顶点没有被穷举完，则执行下列操作E，转步骤3.3；3.3、若数组xn已经形成哈密顿路径，则输出数组xn，算法结束；3.4、若数组xn构成哈密顿路径的部分解，则k=k+1，转步骤3；3.5、否则，取消顶点xk的访问标志，重置xk,k=k-1，转步骤3。实现代码#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>

10、;#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>#inclu

11、de <iomanip>#include <bitset>#include <sstream>#include <fstream>#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

12、namespace std;int mp2020;int x30,vis30;int n,k,cur,ans;void init() for(int i=0;i<n;i+) for(int j=0;j<n;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+mpxn1<ans|ans=-1) for(int i=1;i<=n;i+) visi=xi

13、; ans=cur+mpxn-1xn+mpxn1; else for(int i=t;i<=n;i+) if(mpxt-1xi!=-1&&(cur+mpxt-1xi<ans|ans=-1) swap(xt,xi); cur+=mpxt-1xt; dfs(t+1); cur-=mpxt-1xt; swap(xt,xi); int main() while(scanf("%d",&n) init(); for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) if(i=j) continue; s

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

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

16、下：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执行下列操作：4、将叶子结点对应的最优解输出，回溯求得最优解的各个分量。实现代码#include <cstdio>#include <cstdlib>#include <cstrin

17、g>#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>#inc

18、lude <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#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

19、 , rt << 1 | 1using namespace std;const int Max = ;/*/vector<int>Mp20;vector<int>: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 val<p.val; ;priority_queue<node>q;int getup(int u,int

20、 v,int w) if(v=n) return w+mpu1; int sum=inf,p; for(int i=1; i<=n; i+) if(!visi&&sum>mpui) 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=in

21、f,t2=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

22、); while(!q.empty() 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

23、<=n; i+) if(!head.xi) tmp.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(