TSP问题的解决方案

1、算法设计与分析实验报告学号： 姓名：日 期： 20161230得 分： 一、实验内容：TSP问题二、所用算法的基本思想及复杂度分析：1、蛮力法1) 基本思想借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点 到自身节点的距离为无穷大。在第一行找到最小项alj,从而跳转到 第j行，再找到最小值ajk,再到第k行进行查找。然后构造各行允 许数组rown=p,l.l,各列允许数组colablen=0,l,l.l,其中1表示允 许访问，即该节点未被访问；0表示不允许访问，即该节点已经被访问。 如果改行或该列不允许访问，跳过该点访问下一节点。程序再发问最后 一个节点前，所访问的行中至少有1个

2、允许访问的节点，依次访问这些 节点找到最小的即可；在访问最后一个节点后，再次访问，会返回40, 即实现访问源节点，得出一条简单回路。2) 复杂度分析基本语句是访问下一个行列中最小的点，主要操作是求平方，假设有n 个点，则计算的次数为iT2m。T(n)=n*(n4)=0(nA2)o2、动态规划法1)基本思想假设从顶点s出发，令d(i,V)衣示从顶点i出发经过V，(是个点的集合)中各个顶点次且 仅-次，最后回到出发点s的最短路径长度。推导：(分情况来讨论) 当V，为空集，那么d(i,V表示从i不经过任何点就回到s 了，如上图的城市3“城市 0(0为起点城市)。此时d(i, VCis(就是城市i到城

3、市s的距离)、如果不为空，那么就是对/问题的最优求解。你必须在”这个城市集合中，尝试每 个，并求出最优解。d(i,VminCik+ d(k,k)注：Cik衣示你选择的城市和城市i的距离，d(k,V%k)是个J问题。综上所述，TSP问题的动态规划方程就出来了：丰 S qfcW(l?r-(Ar)宀02)复杂度分析和蛮力法相比，动态规划求解tsp问题，把原来时间复杂性O (n!)的 排列转化为组合问题，从而降低了时间复杂度，但仍需要指数时间。3、回溯法1)基本思想确定了解空间的组织结构后，回溯法从开始结点(根结点)出发，以 深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成 为当前的扩展结

4、点处，搜索向纵深方向移至一个新结点。这个新结点 即成为新的活结点，并为当前扩展结点。如果在当前的扩展结点处不 能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回 移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩 展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所 要求的解或解空间中已无活结点时为止。回溯法求解TSP问题，首先把所有的顶点的访问标志初始化为0,然 后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对 应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子 树继续搜索，否则，对当前子树的兄弟结点进行搜索，如果当前结点 的所有子树都已尝试

5、过并且发生冲突，则回溯到当前结点的父节点。 采用邻接矩阵mpn|n存储顶点之间边的情况，为避免在函数间传递 参数，将数组mp设置为全局变量，设数组刘珂表示哈密顿回路经过 的顶点。2）复杂度分析在哈密顿回路的可能解中，考虑到约束条件xi!=Xj（l=Ij=n,i!=j）,KlJ可能 解应该是（12,n）的一个排列，对应的解空间树种至少有n!个叶子 结点，每个叶子结点代表一种可能解。当找到可行的最优解时，算法 停止。根据递归条件不同时间复杂度也会不同，这里为O （n!）。4、分支限界法1）基本思想分支界限法以广度优先或以最小耗费（最大效益）优势的方式搜索问 题的解空间树。问题的解空间树是表示问题解

6、空间的一棵有序树，常 见的有子集树和排列树。在搜索问题的解空间树时，分支界限法与回 溯法的主要区别在于他们对当前扩展结点所采用的扩展方式不同。在 分支界限法中，每一个活结点只有一次机会成为扩展结点。活结点一 旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中， 导致不可行解或导致非最优解得儿子结点被舍弃，其余儿子结点被加 入活结点表中。算法开始时创建一个最小堆，用于表示活结点优先队 列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如 果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即 告结束。如果

7、每个顶点都有出边，则根据计算出的minout作算法初 始化。2）复杂度分析LI标函数邙R界函数），lb分为三部分，第一部分是经过路径的长度5相加的2倍，加上笫二部分离着路径首尾节点最近的距离相加(不在 已知路径上的)，加上第三部分除了路径上节点，矩阵中两个最短的 距离相加，最后这三部分和相加，得到的结果除以2便是每个节点的 限界值。由于限界函数的不同，下界为O (n),上界为O (21)，智 力特定指出。三、源程序及注释：1、蛮力法int mam()int ij,s=O;intprintf(输入节点个数：n);scanf(%d&：n);pnntfC输入筑d维对称矩阵:nn);colable=(

8、int*)malloc(sizeof(mt)*n);colable0=0;对幹列允许矩阵进行赋值for(i=l;in;i*+)colablei=l;)rows(mt *)malloc(sizeof(mt)*n);for(isO;in;i*)rowi=l;Ias(mt *)malloc(sizeof(int*)*n);for(isO;ina*)(ai=(mt *)malloc(sizeof(int*)*n);)for(isO;inu*)for(j=Og+)(scanf(*%d :&a i (j)1=0;vvhile(rowi=l)j=mm(ai);rovi=0;colablej=0;prrntf

9、C访问路径：n)；s=s*aij;巧；)pnntfC最短总距离为：%dns);int mm(mt *a)intj=O,m=aO,ksO;while(colablej=0 rowj=0)严；m=aj;川求最短距离for(:jn;j*)(if(colable)=l&：rowj=l)/ij 点没有被访问(m=a0;/m始终保持最短距离k=j;)return k;)2、动态规划法int init()8int j;int t;if(scanf(%d,&n)=EOF)return 4;for(i=0; in; i*+)for(j=0; jn; j+)Iif(i=j)continue; scanf(%d,&

10、gi|j);)memset(con/l,sizeof(con);for(i=0; in; i+)biti=li;t=l;for(i=l; in; i+)cont(i4)i=g0i;return 1; int getcon(int s,int k)int t,tt：int i;int min=INF;if(consk!=l)return cons k;t=s& (*bitk4);for(i=l; i0)if(getcon(t,i)+gi kn)(if (graph road n 1!=INF&(ans+graph road n l)bestans)bestans=ans+graph road n

11、 1;for(int j=l;j=n;j+) best road j =road j;elsefor(int j=l;j=n;j+)if (graph road i-l|j!=INF&ans+graphroad i-* 1 jbestans& &Ms|j)roadi=j;ans+=graph road Mj;visj=l;backtrack(i+l);/改回辅助的全局变量ans-=graph road il j；xdsj=O;)int main()memset(graph,INF,sizeof(graph);cinnm;12int a,b;cinab;cingrapha b;graphfb a

12、=grapha b;)visl=l;roadl=l;假设是从1开始 backtrack(2);coutbestansendl;for(int i=l：i=n;i+) coutbestroadi* ：coutlendl;斗分支限界法void in()scan(%d ,&n); for(int i=l; i=n; i+) for(int j=l; j=n; j+)mpij=INF;continue;scanf(%d ,&mpij);)struct nodeIint visp22：/7标记哪些点走了int st沖起点int st_p;起点的邻接点int ed;终点int ed_p;/终点的邻接点in

13、t k;走过的点数int sumv;/经过路径的距离int lb;/目标函数的值 bool operator p.lb;priority_queue q;int low,up;int inq22;/确定上界int dfs(int u,int k,int 1)if(k=n) return l+mpu1;int minlen=INF , p;for(int i=l; imp u i)/*取与所有点的连边中最小的边*/minlen=mpui;p=i；)inqp=l;15return dfs(pk+l,l+minlen);int getjb(node p)int reup.sumv溪2路径上的点的距离

14、int minl=INF,min2=INF;/起点和终点连出来的边for(int i=l; imp i p.st)minl=mpip.st;ret+=minl;for(int i=l; impp.ed i)min2=mpp.ed i;ret+=min2;for(int i=l; i=n; i+)if(p.rispi=O)minl=min2=INF;for(int j=l; jmpij) minl=mpi j;for(int j=l; jmpj i) min2=mpji;ret+=minl+min2;return ret%2=0?(ret/2): (ret/2+1);13void getupOi

15、nql=l;up=dfs(l 丄 0);void getow()low=0;for(int i=l; imin2=INF;int tmpA22;for(int j=l; j=n; j+)tmpAj=mpi|j;sort(tmpA+1 ,tmp A+1+n);/对临时的数组进行排序low+=tmpA 卩;)int solve()严贪心法确定上界勺get.upO；严取每行最小的边之和作为F界*/ getjow();严设巻初始点，默认从1开始*/node star;star.st=l;star.ed=l;star.k=l;for(int i=l; i=n; i+) star.vispi=O;star

16、Adspl=l;star.sumv=O;star.lb=low;件ret为问题的解*/int ret=INF;q.push(star);while(!q.empty() node tmp=q.top();qpop()；if(tmp.k=n-l)严找最后一个没有走的点吟int p；for(int i=l; i=n; i+)if(tmp.dspi=O)p=i；break;int ans=tmp.sumv+mpp tmp.st+mptmp.edp;node judge = q.top();广如果当前的路径和比所有的目标函数值都小则跳出咛if(ans = judge.lb)ret=min(ans,re

17、t);break;/*否则继续求英他可能的路径和，并更新上界勺elseup = min(up,ans);ret=min(ret,ans);continue;广当前点可以向下扩展的点入优先级队列勺node next;for(int i=l; i=n; i+)if(tmp.xispi=O)next.st=tmp.st;严更新路径和勺next.sumv=tmp.sumv+mptmp.edi;广更新最后一个点勺next.ed=i;广更新顶点数*/next.k=tmp.k+l;广更新经过的顶点吟for(int j=l; jup) continue;q.push(next);) return ret;四. 运行输出结果:（1）蛮力法输入节点个数!器入4维对称矩陆：108 3 ? 23 10 1 -49 1 100 7Z 4 7访问路径,M3访问路径!3一1访何路径:1一2访1可路径*20最短总距离为：筑any key to continue（2）动态规划法畐o3QE- 靜的SS的的的的的E 迈辺边辺辺辺辺辺边辺Q X入入入人入入入入入f T厂工；.；m-i-L 丄：一一巷一E H 且且其苴苴且“ nblTU4aHrtmm的的的的的的的的的 苫盖点点点点点点 需Tr护氏顶顶顶nrAoxited with rotum value A any key C