Tsp问题的几种算法的讲解

《Tsp问题的几种算法的讲解》由会员分享，可在线阅读，更多相关《Tsp问题的几种算法的讲解（25页珍藏版）》请在金锄头文库上搜索。

1、摘要本文分析比较了 tsp问题的动态规划算法，分支界限法， 近似等算法。分析了旅行商问题的时间度特点，针对启发式 算法求解旅行商问题中存在的一些问题提出了改进算法。此 算法将群体分为若干小子集，并用启发式交叉算子，以较好 利用父代个体的有效信息，达到快速收敛的效果，实验表明 此算法能提高寻优速度，解得质量也有所提高。关键词：旅行商问题TSPAbstractthis paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genet

2、ic algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision.Keywords traveling salesman pro

3、blem; genetic algorithm; subset; henristic crossover operator目录1、摘要12、Abstract13、Tsp问题的提法24、回溯法求Tsp问题35、分支限界法求Tsp问题76、近似算法求解Tsp问题107、动态规划算法解Tsp问题12引言tsp问题刚提出时，不少人都认为很简单。后来，人们实 践中才逐步认识到，这个问题只是叙述简单，易于为人所理 解而其计算复杂性却是问题的输入规模的指数函数，属于 NP完全问题。Tsp问题的实现思想已被应用到交通，管理等 很多领域所以有必要探讨Tsp问题的算法。这里给出Tsp问 题的动态规划算法，回溯算法

4、，分支限界法，近似算法，和 改进的启发式算法，以及它们之间的分析比较。正文：旅行售货员问题的提法是：某售货员要到若干城市去推销商品，已知各城市之间的 路程（或旅费）。他要选定一条从驻地出发，经过每个城市 一遍，最后回到驻地的路线，使总的路程（或旅费）最小。设G=（V,E）是一个带权图。图中各边的费用（权）为正数。 图中的一条周游路线是包括V中的每个顶点在内的一条回 路。周游路线的费用是这条路线上所有边的费用之和。旅行 售货员问题要在图G中找到费用最小的周游路线。图 1-1:回溯法:（1）回溯法的基本思想：确定了解空间的组织结构后， 回溯法从开始结点（根结点）出发，以深度优先方式搜索整 个解空间

5、。这个开始结点成为活结点，同时也成为当前的扩 展结点处，搜索向纵深方向移至一个新结点。这个新结点即 成为新的活结点，并为当前扩展结点。如果在当前的扩展结 点处不能再向纵深方向移动，则当前扩展结点就成为死结 点。此时，应往回移动（回溯）至最近的一个活结点处，并 使这个活结点成为当前的扩展结点。回溯法以这种工作方式 递归地在解空间中搜索，直至找到所要求的解或解空间中已 无活结点时为止。回溯法搜索解空间树时，通常采用两种则略避免无效搜 索，提高回溯法的搜索效率。其一是用约束函数在扩展结点 处减去不满足约束的子数；其二是用界限函数剪去得不到最 优解的子数。这两类函数统称为剪支函数。（2）回溯法解tsp

6、问题：旅行售货员问题的解空间可以 组织成一棵树，从书的根结点到任一叶结点的路径定义了图 G的一条周游路线。图5-3是当n=4时解空间树的示例。其 中从根结点A到叶结点L的路径上边的标号组成一条周游路 线1, 2, 3, 4, 1。而从根结点A到叶结点O的路径则表示 周游路线1, 3, 4, 2, 1.图G的每一条周游路线都恰好对应 于解空间树中一条从根结点到叶结点的路径。因此，解空间 树中叶结点个数为（n-1）!】。图 1-2：对于图1-2的图G,用回溯法找最小费用路线时，从解空间 树的根结点A出发，搜索至B,C,F,L.在叶结点L处记录找到 的周游路线1, 2, 3, 4, 1，该周游路线的

7、费用为59.从叶结 点L返回至最近活结点F处。由于F处已没有可扩展结点。 算法又返回到结点C处。结点C成为新扩展结点，由新扩展 结点，算法再移至结点G后又移至结点M,得到周游路线1,2, 4, 3, 1，其费用为66.这个费用不比已有周游路线1, 2,3, 4, 1的费用更小。因此舍弃该结点。算法又依次返回至 结点G, C, B。从结点B，算法继续搜索至结点D, H, N。 在叶结点N处，相应的周游路线1, 23, 2, 4, 1的费用为 25.它是当前找到的最好的一条周游路线。从结点N算法返 回至结点H，D，然后在从结点D开始D开始继续向纵深搜 索至结点O。以此方法算法继续搜索遍整个解空间，

8、最终得 到最小费用周游路线1，3, 2, 4, 1.在递归算法Backtrack中，当i=n时，当前扩展结点是 排列数的叶结点的父结点。此时算法检测图G是否存在一条 从顶点x【n-1到顶点xn的边和一条从顶点xn到顶点1的 边如果这两条边都存在，则找到一条旅行售货员回路。此时 算法还需要判断这条回路的费用是否优于已找到的当前最 优回路的费用bustc。如果是则必须更新当前最优值bestc和 当前最优解bestx。当in时，当前扩展结点位于排列树的第i-1层。图G 中存在从顶点xi-1到顶点xi的边时，xl,:i构成图G的一条 路径，且当x;:i的费用小于当前最优值时算法进入排列树的 第i层，否

9、则将剪去相应的子数。算法中用变量cc记录当前 路径x【l:i的费用。解旅行售货员问题的回溯算法可描述如下：TemplateClass Travelingfriend Type tSP(int * *,int,int,Type);private:void Backtrack(int i);int n,*x,*bestx;Type* *a,cc,bestx;Type * *a,cc,bestc,NoEdge;TemplateVoid Traveling:Backtrack(int i)If(i=n)If(axn-1)xn!=NoEdge&axn1!=N0Edge&(cc+axn-1xn+axn1b

10、est|bestc=NoEdge)for(int j=1;j=n;j+)bestxj=xj;bestc=cc+axn-1xn+axn1;elsefor(int j=i；j=n;j+)if(axi-1xj!=NoEdge&(cc+axi-1xjbestcllbestc =NoEdge)Swap(xi,xj;cc+=axi-1xi;Backtrack(i+10;cc-=axi-1xi;swap(xi,xj);分支界限法：(1) 分支界限法的基本思想：分支界限法以广度优先或 以最小耗费(最大效益)优势的方式搜索问题的解空间树。 问题的解空间树是表示问题解空间的一棵有序树，常见的有 子集树和排列树。在

11、搜索问题的解空间树时，分支界限法与 回溯法的主要区别在于他们对当前扩展结点所采用的扩展 方式不同。在分支界限法中，每一个活结点只有一次机会成 为扩展结点。活结点一旦成为扩展结点，就一次性产生其所 有儿子结点。在这些儿子结点中，导致不可行解或导致非最 优解得儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复 上述结点扩展过程。这个过程一直持续到找到所需的解或活 结点表为空时为止。（2）从活结点表中选择下一个扩展结点的不同方式导致 不同的分支界限法。最常用的有两种方式1. 方式队列式（FIFO）分支界限法队列式分支界限法将活结点组织成一个队列，并按

12、队 列的先进先出原则选择下一个结点为当前扩展结点。2 .优先队列式分支界限法优先队列式的分支界限法将活结点表组织成一个优先队 列，并按优先队列中规定的结点优先级选取优先级最高的下 一个结点成为当前扩展结点。（3）分支法解tsp问题：考察4城市旅行售货员的例子， 如图5-3所示，该问题的解空间树是一棵排列树。解次问题 的队列式分支界限法以排列树中结点B作为初始扩展结点。 此时，活结点队列为空。由于从图G的顶点1到顶点2, 3 和4均有边相连，所以结点B的儿子结点C，D，E均为可 行结点，它们被加入到活结点队列中，并舍去当前扩展结点 B。当前活结点队列中的队首结点C成为下一个扩展结点。 由于图G的

13、顶点2到顶点3和4有边相连，故结点C的2 个儿子结点F和G均为可行结点，从而被加入到活结点队列 中。接下来，结点D和结点E相继成为扩展结点而被扩展。此时活结点队列中的结点依次是F, G, H, I, J, K。算法描述：算法开始时创建一个最小堆，用于表示活结点优先队列。 堆中每个结点的子树费用的下界lcost值是优先队列的优先 级。接着算法计算出图中每个顶点的最小费用出边并用 minout记录。如果所给的有向图中某个顶点没有出边，则该 图不可能有回路，算法即告结束。如果每个顶点都有出边， 则根据计算出的minout作算法初始化。算法的while循环体完成对排列树内部结点的扩展。对 于当前扩展结

14、点，算法分2种情况进行处理：1、首先考虑s=n-2的情形，此时当前扩展结点是排列 树中某个叶结点的父结点。如果该叶结点相应一条可行回路 且费用小于当前最小费用，则将该叶结点插入到优先队列 中，否则舍去该叶结点。2、当sn-2时，算法依次产生当前扩展结点的所有儿 子结点。由于当前扩展结点所相应的路径是x0:s，其可行 儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs， xi)是所给有向图G中的一条边。对于当前扩展结点的每一 个可行儿子结点，计算出其前缀(x0:s, xi)的费用cc和相 应的下界lcosto当lcostbestc时，将这个可行儿子结点插入 到活结点优先队列中。算法中

15、while循环的终止条件是排列树的一个叶结点成 为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1, 它已包含图G的所有n个顶点。因此，当s=n-1时，相应的 扩展结点表示一个叶结点。此时该叶结点所相应的回路的费 用等于cc和lcost的值。剩余的活结点的lcost值不小于已找 到的回路的费用。它们都不可能导致费用更小的回路。因此 已找到的叶结点所相应的回路是一个最小费用旅行售货员 回路，算法可以结束。算法结束时返回找到的最小费用，相应的最优解由数组 v给出。近似算法：近似算法解旅行售货员问题:问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v) EE有一非负整数费用c(u,v)。要找出G的最小费用哈密顿 回路。旅行售货员问题的一些特殊性质：比如，费用函数c往往具有三角不等式性质，即对任意 的 3 个顶点 u,v,wEV，有：c(u,w)Wc(u,v)+c(v,w)。当图 G 中 的顶点就是平面上的点，任意2顶点