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

1、TSP问题算法实验报告指导教师：季晓慧姓 名：辛瑞乾学 号：提交日期：2015年11月目录总述动态规划法算法问题分析算法设计实现代码输入输出截图OJ提交截图算法优化分析回溯法算法问题分析算法设计实现代码输入输出截图OJ提交截图算法优化分析分支限界法算法问题分析算法设计实现代码输入输出截图OJ提交截图算法优化分析总结总述TSP问题乂称为旅行商问题，是指一个旅行商要历经所有城市一次最后乂回到 原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法， 动态规划法具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回 溯法以及分支限界法。动态规划法算法问题分析假设n个顶点分别用0n

2、-1的数字编号，顶点之间的代价存放在数组mpnn 中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、 n-1的顺序生成1n-1个元素的子集存放在数组x2-1中，例如当n=4时， x1 = 1,x2 = 2,x3 = 3,x4 = 1,2,x5 = 1,3,x6 = 2,3,x7 = 1,2, 3。设数组dpn2%-1存放迭代结果，其中dpij表示从顶点i经过子集xj 中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP 问题的算法如下。算法设计输入：图的代价矩阵mpnn输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度初始化第0列(动

3、态规划的边界问题)for(i=1;in;i+)dpi0=mpi0依次处理每个子集数组x2%-1for(i=1;in;i+)if (子集xj中不包含i)对 xj中的每个元素 k，计算 dij=minmpik+dpkj-1;输出最短路径长度。实现代码#include #include #include #include #include #include #include algorithm#include #include #include #include #include #include #include #include #include #include #include #inclu

4、de #include #include #define debug output for debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0 x3f3f3f3f#define ll long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;const int Max = 100005;int n,mp2020,dp2040000;int main() (while(scanf(%d,&n)(int an

5、s二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&(1(i-1)=0)(int x,y=inf;for(int k=1; kn; k+)(if(j&(10)x=

6、dpk(j-(1(k-1)+mpik;y=min(y,x);dpij=y;dp0mx-1=inf;for(int i=1;in;i+)dp0mxT=min(dp0mxT,mp0i+dpi(mxT)-(1=1)3.1、xk=xk+1，搜索下一个顶点。3.2、若n个顶点没有被穷举完，则执行下列操作EE，转步骤3.3；3.3、若数组xn已经形成哈密顿路径，则输出数组xn，算法结束；3.4、若数组xn构成哈密顿路径的部分解，则k=k+1，转步骤3；3.5、否则，取消顶点xk的访问标志，重置xk,k=k-1，转步骤3。实现代码#include #include #include #include #in

7、clude #include algorithm#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug output for debugn#define pi (acos(T.O)#define eps (1e-8)#define inf 0 x3f3f3f3f #define ll long long int#define lson l , m , rt 1#define

8、 rson m + 1 , r , rt 1 | 1 using 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(mpxnTxn!=T&(mpxn1!=T)&(cur+mpxnTxn+mpxn1ans|ans=-1)(for(int i=1;i=n;i+)visi=xi;ans=cur+mpxn

9、-1xn+mpxn1;else(for(int i=t;i=n;i+)(if(mpxtTxi!=T&(cur+mpxtTxians|ans=T)(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;scanf(%d,&mpij);/puts(YES)；dfs(2);coutansendl;return 0;输入输出截图OJ提交截图算法

10、优化分析在哈密顿回路的可能解中，考虑到约束条件xi!二xj(1=I,j=n,i!=j),则可能 解应该是(1,2,n)的一个排列，对应的解空间树种至少有n!个叶子结点，每 个叶子结点代表一种可能解。当找到可行的最优解时，算法停止。分支限界法算法问题分析分支限界法解决TSP问题首先确定目标函数的界down,up，可以采用贪心法 确定TSP问题的一个上界。如何求得TSP问题的一个合理的下界呢？对于无向图 的代价矩阵，吧矩阵中每一行最小的元素想家，可以得到一个简单的下界，但是 还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个 城市都有两条邻接边，一条是进入这个城市的，另一条是

11、离开这个城市的，那么， 如果把矩阵中每一行最小的两个元素相加在除以2,假设图中所有的代价都是整数， 再对这个结果向上取整，就得到一个合理的下界。需要强调的是，这个解可能不 是一个可行解(可能没有构成哈密顿回路)，但给出了一个参考下界。一般情况下，假设当前已确定的路径为U=(r1,r2,rk),即路径上已确定了 k个 顶点，此时，该部分解的目标函数值的计算方法(限界函数)如下： Lb=(2Ecrir(i+1) + Eri行不在路径上的最小元素+Eri行最小的两个元素)/2算法设计输入：图G=(V,E)输出：最短哈密顿回路1、根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2、计算

12、根节点的目标函数值并加入待处理结点表PT；3、循环知道某个叶子结点的目标函数值在表PT中取得极小值3.1、i二表PT中具有最小值的结点；3.2、对结点i的每个孩子几点x执行下列操作：4、将叶子结点对应的最优解输出，回溯求得最优解的各个分量。实现代码#include #include #include #include #include #include #include algorithm#include #include #include #include #include #include #include #include #include #include #include #incl

13、ude #include #include #define debug output for debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0 x3f3f3f3f#define ll long long int#define lson l , m , rt 1#define rson m + 1 , r , rt 1 | 1using namespace std;const int Max = 100005;/*/vectorMp20;vector:iterator it;int mp2020;int vis20;int u

14、p,low,n,ans;struct node(int x20,st,ed,dis,val,num;bool operator(const node &p)const(return valp.val;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.be

15、gin();sum+=*it;it+;sum+=*it;return sum/2;int gao(node s)(int res二s.dis*2;int tl=inf, t2=inf:for(int i=l: i=n; i+)if (! s. x i)tl=min (tl, mp i s. st);t2=min (t2, mp s. ed i);res+=tl:res+=t2;int tmp:for(int i=l: i=n; i+)tmp二inf;if (! s. x i)it=Mpi. begin();res+=*it;for(int j=l: j=n; j+)tmp=min(tmp, m

16、p j i);res+=tmp;return !(res%2)(res/2):(res/2+1);void bfs(node s)(q.push(s);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,cn

17、t);ans=min(ans,cnt);continue;node tmp;for(int i=1; i=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(

18、int i=1; i=n; i+)(for(int j=1; j=n; j+)(if(i!=j)scanf(d，&mpij);Mpi.push_back(mpij);elsempij=inf;sort(Mpi.begin(),Mpi.end();memset(vis,0,sizeof vis);vis1=1;up=0;up+=getup(1,1,up);low=getlow();node fir;fir.st=1;fir.ed=1;fir.num=1;for(int i=1; i=n; i+) fir.xi=0;fir.x1=1;fir.dis=0;fir.val=low;ans二inf;bfs(fir);printf(dn,ans);return 0;输入输出截图OJ提交截图算法优化分析分支限界法的复杂度是根据数据的不同而不同，搜索的节点越少，复杂度越低， 跟目标函数的选择有很大关系。目标函数值的计算也会需要一定时间，比如此文 章中的目标函数值求解的复杂度是O(2 )。当然此算法仍然有可以优化的地方， 比如在记录该