Tsp问题的几种算法的分析.docxVIP

摘要 本文分析比较了 tsp 问题的动态规划算法，分支界限法， 近似等算法。分析了旅行商问题的时间度特点，针对启发 式算法求解旅行商问题中存在的一些问题提出了改进算法。 此算法将群体分为若干小子集，并用启发式交叉算子，以 较好利用父代个体的有效信息，达到快速收敛的效果，实 验表明此算法能提高寻优速度，解得质量也有所提高。 关键词：  旅行商问题 TSP Abstract this paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genetic 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 problem; genetic algorithm; subset; henristic crossover operator 1 目录 1、 摘要--------------------------------------------------------------1 2、 Abstract---------------------------------------------------------1 3、 Tsp 问题的提法------------------------------------------------2 4、 回溯法求 Tsp 问题--------------------------------------------3 5、 分支限界法求 Tsp 问题--------------------------------------7 6、 近似算法求解 Tsp 问题-------------------------------------10 7、 动态规划算法解 Tsp 问题----------------------------------12 2 引言 tsp 问题刚提出时，不少人都认为很简单。后来，人们 实践中才逐步认识到，这个问题只是叙述简单，易于为人 所理解而其计算复杂性却是问题的输入规模的指数函数， 属于 NP 完全问题。Tsp 问题的实现思想已被应用到交通， 管理等很多领域所以有必要探讨 Tsp 问题的算法。这里给 出 Tsp 问题的动态规划算法，回溯算法，分支限界法，近 似算法，和改进的启发式算法，以及它们之间的分析比较。 正文： 旅行售货员问题的提法是： 某售货员要到若干城市去推销商品，已知各城市之间 的路程（或旅费）。他要选定一条从驻地出发，经过每个城 市一遍，最后回到驻地的路线，使总的路程（或旅费）最 小。 设 G=(V,E) 是一个带权图。图中各边的费用(权)为正数。 图中的一条周游路线是包括 V 中的每个顶点在内的一条回 3 路。周游路线的费用是这条路线上所有边的费用之和。旅 行售货员问题要在图 G 中找到费用最小的周游路线。 1  2 图 1-1： 3 4 回溯法： （1）回溯法的基本思想：确定了解空间的组织结构后， 回溯法从开始结点（根结点）出发，以深度优先方式有哪些信誉好的足球投注网站 整个解空间。这个开始结点成为活结点，同时也成为当前 的扩展结点处，有哪些信誉好的足球投注网站向纵深方向移至一个新结点。这个新 结点即成为新的活结点，并为当前扩展结点。如果在当前 的扩展结点处不能再向纵深方向移动，则当前扩展结点就 成为死结点。此时，应往回移动（回溯）至最近的一个活 结点处，并使这个活结点成为当前的扩展结点。回溯法以 这种工作方式递归地在解空间中有哪些信誉好的足球投注网站，直至找到所要求的 解或解空间中已无活结点时为止。 回溯法有哪些信誉好的足球投注网站解空间树时，通常采用两种则略避免无效 有哪些信誉好的足球投注网站，提高回溯法的有哪些信誉好的足球投注网站效率。其一是用约束函数在扩展 结点处减去不满足约束的子数；其二是用界限函数剪去得 不到最优解的子数。这两类函数统称为剪支函数。 （2）回溯法解 tsp 问题：旅行售货员问题的解空间可以 组织成一棵树，从书的根结点到任一叶结点的路径定义了 4 图 G 的一条周游路线。图 5-3 是当 n=4 时解空间树的示例。 其中从根结点 A 到叶结点 L 的路径上边