旅行售货员问题毕业设计论文.doc

摘 要旅行售货员问题是一个古老而典型的组合优化问题。对该问题合理而有效的解法不但有重要的理论和学术意义，同时对众多工程实际中的应用提供了重要的指导意义。这篇论文首先对问题进行了大体的陈述，对其进行了数学描述。在此基础上,本文对问题进行了进一步的定义。论文介绍了五种算法的基本概念、原理、意义及发展现状。这五种算法包括动态规划法、分支界限法、回溯法、遗传算法和微粒子算法。并展示了部分算法的部分数学过程。关键词：旅行售货员问题；遗传算法；微粒子算法；回溯法Several Solutions to Traveling Salesman ProblemAbstractTraveling salesman problem is an old and typical hard combinatorial optimization problem, its valid and effective solutions not only has important theoretical and academic values, but also has important guiding significance for many practical engineering applications. The essay starts with the general account of , explains the mathematical description of . On the original basis, the essay made through classification of ; The essay introduced the basic concept, principle, procedure and significance of five types of algorithm, including dynamic programming, branch bounding method, backtracking method, Genetic algorithm, Particle Swarm Optimization. It also displayed some major process in mathematic ways.Key Words：Traveling Salesman Problem; Genetic Algorithm; Backtracking Algorithm目 录摘 要IAbstractII引 言11 旅行售货员问题的研究现状21.1旅行售货员问题概述21.2 旅行售货员问题的数学描述31.3 旅行售货员问题的分类41.4 前人的工作51.4.1 精确算法51.4.2 启发式算法51.5 本章小结52 精确算法求解策略及优化算法62.1动态规划法解旅行售货员问题62.1.1 动态规划思想简介62.1.2 动态规划求解旅行售货员问题62.2分支限界法解问题62.3回溯法解旅行售货员问题82.3.1 回溯法思想简介82.3.2 回溯法求解履行商问题82.3.3 回溯法的不足92.3.4 回溯算法的改进92.4 三种精确算法的比较102.4.1 动态规划法和回溯法的比较102.4.2分支限界法和回朔法的比较113 遗传算法解决旅行售货员问题123.1启发式算法简介123.2 遗传算法介绍123.2.1遗传算法发展123.2.2遗传算法自身特点133.2.3遗传算法总结133.3 基本遗传算法求解旅行售货员问题144 微粒子算法简介154.1 微粒子算法历史154.3 微粒子算法结合旅行售货员问题155 旅行售货员问题的应用16结 论17参 考 文 献18附录旅行售货员问题的最小耗费分枝定界算法19附录旅行售货员问题的回溯法22致 谢24引 言旅行售货员问题(Traveling Salesman Problem)，是计算机算法中的一个经典的难解问题，已归为完备问题(Non polynomial)类。围绕着这个问题有各种不同的求解方法，已有的算法如动态规划法，分支限界法，回溯法等，这些精确式方法都是指数级的，根本无法解决目前的实际问题，贪心法是近似方法，而启发式算法不能保证得到的解是最优解，甚至是较好的解释。所以我认为很多问题有快速的算法(多项式算法)，但是，也有很多问题是无法用算法解决的。事实上，已经证明很多问题不可能在多项式时间内解决出来。但是，有很多很重要的问题他们的解虽然很难求解出来，但是他们的值却是很容易求可以算出来的。这种事实导致了完全问题。凡是在多项式复杂程度内可以求出最优解的问题，称为问题，其它的则是问题。在算法问题上，假如一个问题是问题，我们通常认为它是“简单的”，对于一个问题，通常认为它是“复杂的”。表示非确定的多项式，意思是这个问题的解可以用非确定性的算法猜出来。如果我们有一个可以猜想的机器，我们就可以在合理的时间内找到一个比较好的解。完全问题学习的简单与否，取决于问题的难易程度。因为有很多问题，它们的输出极其复杂，比如说人们早就提出的一类被称作难题的问题。这类问题不像完全问题那样时间有限的。因为问题由上述那些特征，所以很容易想到一些简单的算法把全部的可行解算一遍。但是这种算法太慢了(通常时间复杂度为指数次)在很多情况下是不可行的。现在，没有知道有没有那种精确的算法存在。证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了，或许你就是成功者。本篇论文就是想用几种方法来就一个销售商从几个城市中的某一城市出发，不重复地走完其余个城市，并回到原出发点，在所有可能的路径中求出路径长度最短的一条，比较是否是最优化，哪种结果好。目前求解旅行商问题的方法可以分为两大类：一类是精确算法，目的是要找到理论最优解；另一类是近似算法，不强求最优解，只要找到“足够好”的满意解就可以了。在本文中，我们将对两类算法分别选取若干种进行分析。1 旅行售货员问题的研究现状1.1旅行售货员问题概述旅行售货员问题是十九世纪初爱尔兰的数学家W.Hamilton 和英国数学家T.Kirkman1提出的，通常被描述为：对给定城市交通网络，如何为一个推销商选择一条路线，从网络的某一点(驻地)出发，经过每一个结点后回到出发点，使得总行程最短。问题是著名的完全难题，也是组合优化、计算机科学界经典的问题之一。它在广泛的应用于运输、生产、国防、生物、计算机等领域以外，还为离散优化中各类算法提供了思想方法平台，因而对旅行售货员问题求解方法的研究具有重要的实际价值。标准的在图论的意义就是所谓的最小圈问题。由于其在许多领域都有着广泛的应用，因而寻找其实际而又有效的算法显得颇为重要，遗憾的是，计算复杂性理论给予我们的结论是：这种可能性尚属未知。在理论上已归结为所谓的完备问题类，即非确定性多项式完备问题。关于这类十分困难的问题，现在所知道的仅仅是；任何完备问题都不能用己知的多项式算法来解决;用多项式算法去研究问题起于五十年代，如线性规划算法、动态规划算法、分枝定界法。这些算法虽然对一些小规模的问题可精确求解，但计算的复杂度与城市的数目成指数增长。在大规模的问题上，这些精确算法显得无能为力，而且容易产生组合爆炸，因而人们退而寻求非尽善尽美的所谓启发式算法(近似算法)，来处理各种实际问题。七十年代和八十年代是启发式算法的全盛时期，但由于绝大多数启发式算法都是按某种确定性的搜索规则来运行，想要改进所得解的可能性极小。因此，从八十年代后期一直到九十年代，一些来自其它学科的新一代求解方法相继出现，在组合优化问题的求解中取得相当的成功和一系列成果。尽管仍未找到最优解，但是求解它的算法逐渐改进。2000年，马良总结、归纳出1954年到1996年国内外近几十年求解的算法，可分为两类：一类是精确算法如线性规划、动态规划、分枝定界法等；另一类是近似算法(启发式算法)，如插入算法、算法、神经网络算法、模拟退火算法、遗传算法、蚂蚁算法等。目前，对于求解问题，国内外都有相当好的进展，2000年，周培德用点集凸壳的多项式时间算法解决了31个顶点的中国货郎担问题。1998年，美国加利弗利亚大学Dan Gusfiled根据出度、入度均为的2的有向图中有一条路的这一特性，提出了用Greedy算法求解出度、入度均为2的。几十年来对于求解 问题出现了很多传统方法，其中有精确算法如线性规划方法、动态规划方法、分支定界方法；近似优化算法有插入法、最近邻算法灯、混合算法、概率算法等。近年来，有很多解决该问题的较为有效的智能方法不断被推出，例如禁忌搜索方法、遗传算法、模拟退火算法等。时至今日，人们己经发现有许多问题本质上都可归结为一个或是将其作为一个子问题来处理，但要想真正有效的求解，目前仍然是一件很困难的事。而由引伸出来的一些扩展问题，如瓶颈问题、多目标问题等，却由于本身的难度而一直少人问津。1.2 旅行售货员问题的数学描述旅行售货员问题，也称货郎问题，有两种提法。一种旅行售货员问题的简单描述是：一名商人欲到个城市推销商品，每两个城市和之间的距离为，如何选择一条路径是的商人每个城市走一遍回到起点后，所走的路径最短。其数学模型为在加权图上求一个圈，使得 (1.1)上述经典的定义比实际问题就要狭隘了，因为实际上旅行售货员可以在一段路程上往返，往往反而节省了整个巡回的总费用（大都用距离来表示）。此外，如果有图所示的用上述经典的定义找不到解得，但在实际中的旅行售货员仍可选择一条最优路线，只不过顶点要被访问两次。 12354图2.1 旅行售货员问题举例则另一种提法是商人从某城市出发，遍历各个城市至少一次后返回出发点，设计出一条路线使总路程最短。此时，数学模型是在加权图上求一个生成回路，使。 (1.2)这个叫做理想回路。从算法理论上讲，这两种提法难度是相当的。1.3 旅行售货员问题的分类从问题对应到图的类型，通常有两种基本的分类：任意两个城市之间来往的路径均相等或可以不相等；就可以归结为无向图或有向图问题。任意两个城市之间来回均存在路径或至少有两个城市之间仅存在单行路径；这种类型可以归结为完全图或者非完全图问题。将上述两种情况加以组合，便可得到以下四种的路径关系：完全有向图；完全无向图；非完全有向图；非完全无向图。从问题本身的限制条件的强弱，主要有三类，第一类不作任何限制，只给出距离矩阵，求最小回路；第二类要求距离间要满足三角不等式(对于一个旅行售货员问题中的任意三个城市，假如从经过到达的旅行费用不低于从到的旅行费用，那么称这个旅行售货员问题满足三角不等性)，满足三角不等性的旅行售货员问题，具有许多优良的性质，可以大大方便计算。但另一方面，已经证明，满足三角不等性的对称旅行售货员问题，也是完全问题。对于满足三角不等性的对称旅行售货员问题，可以在多项式的计算时间内求得近似解。第三类就是定义在欧氏平面上的，即Euclid TSP，它以欧氏平面上的坐标和欧氏距离来给出城市间的坐标和城市间的距离。从问 题 的 多项式可解性上，可分为两类。一类是目前己知有多项式的时间算法可解的，比如其距离矩阵满足Demidenk条件、Kalmanson 条件或者Supnick条件等；另一类是目前尚未发现有多项式时间算法可解的，而研究热点就是如何寻找更多的多项式时间可解的情形，使得第一类集合扩大，第二类缩小。除此之外，的研究经过了几十年的发展，还引申出其它扩展形式，比如多旅行售货员问题(Multi Salesman Problem)，它是由多人完成环游的，该问题可转化为等价的单人问题求解。还有多目标旅行售货员问题(Multi objective )，该问题在每条边都有个权值，则使得回路上相应的个目标值都尽可能小的解就称为多目标的有效解，如实际问题中要考虑的路程最短、时间最小、费用最省、风险最小等多方面的因素。1.4 前人的工作1.4.1 精确算法精确算法能保证完全搜索问题的整个解空间，从而找到最优解，但需要消耗指数级的运算时间；有些精确算法虽然运用一些精巧的技术来减少搜索空间，但其本质上还是进行全局搜索，并没有降低运算时间复杂度。本文讨论的前四种动态规划法，分支界限法，回溯法，改进的回溯法均属于这一分类。1.4.2 启发式算法启发式算法不能保证搜索问题的全部解空间，所以也不能保证能够搜到最优解，甚至在某些实例上连解都得不到，但它们与精确算法相比却具有运算时间上的优势，即它们的运算时间复杂度都只是多项式2，并不会随着输入规模的扩大而产生“组合爆炸”。这类算法采用的是启发式策略来指导搜索，普遍比精确算法要快。但这类算法对学科交叉能力要求较高，在此我们仅讨论其中的一种，遗传算法。1.5 本章小结本章从的概述出发，介绍了旅行售货员问题的数学描述与分类，在原有的基础上，对作了更细致的分类:如将旅行售货员问题对应图上的分类，最后综述了旅行售货员问题在近几十年的研究分支以及算法进展与分类，着重介绍了一些主要算法的求解思想、适用特点及性能。2 精确算法求解策略及优化算法2.1动态规划法解旅行售货员问题2.1.1 动态规划思想简介我们将具有明显的阶段划分和状态转移方程的规划称为动态规划，这种动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理)，则可以考虑用动态规划解决。所以动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的，相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。2.1.2 动态规划求解旅行售货员问题旅行售货员问题其实就是一个最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。关于旅行售货员问题，状态变量，表示从出发经过个城市到达的最短距离，为包含个城市的可能集合，动态规划的递推关系为：，(2.1)其中，表示到的距离。 或者，我们可以用：， in ，即为所求 (2.2)其中表示从出发，经过中每个城市一次且一次，最短路径。2.2分支限界法解问题旅行售货员问题的解空间是一个排列树，与在子集树中进行最大收益和最小耗费分枝定界搜索类似，使用一个优先队列，队列中的每个元素中都包含到达根的路径。 假设我们要寻找的是最小耗费的旅行路径，使用最小耗费分枝定界法。实现过程中，用一个最小优先队列来记录活节点，队列中每个节点的类型为3。每个节点包括如下区域：x ，从到的整数排列，其中x 0 = 1 ；s，一个整数，使从排列树根节点到当前节点的路径定义了旅行路径的前缀x0: s；而剩余待访问的节点是x s + 1 : n - 1 ；cc，旅行路径前缀，即解空间树中从根 节点到当前节点的耗费；lcost，该节点子树中任意叶节点中的最小耗费；rcost，从顶点x s : n - 1 出发的所有边的最小耗费之和。当类型为的数据被转换成为类型时，其结果即为lcost的值。分枝定界算法的代码见附录A。程序首先生成一个容量为1000的最小堆，用来表示活节点的最小优先队列。活节点按其lcost值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中 耗费最小的边所具有的耗费。如果某些顶点没有出边，则有向图中没有旅行 路径，搜索终止。如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。根的孩子作为第一个-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0， x0=1， x1: n-1是剩余的顶点(即顶点 )。旅行路径前缀1的开销为0，即cc=0，并且rcost=n，i=1。在程序中，bestc 给出了当前能找到的最少的耗费值。初始时，由于没有找到任何旅行路径，因此bestc的值被设为NoEdge。while 循环不断地展开-节点，直到找到一个叶节点。当s = n - 1时即可说明找到了 一个叶节点。旅行路径前缀是x 0 : n - 1 ，这个前缀中包含了有向图中所有的个顶点。因此s = n - 1的活节点即为一个叶节点。由于算法本身的性质，在叶节点上lcost 和cc恰好等于叶节点对应的旅行路径的耗费。由于所有剩余的活节点的lcost值都大于等于从最小堆中取出的第一个叶节点的lcost值，所以它们并不能帮助我们找到更好的叶节点，因此，当某个叶节点成为-节点后，搜索过程即终止。while 循环体被分别按两种情况处理，一种是处理s = n - 2的-节点，这时，-节点是某个单独叶节点的父节点。如果这个叶节点对应的是一个可行的旅行路径，并且此旅行路径的耗费小于当前所能找到的最小耗费，则此叶节点被插入最小堆中，否则叶节点被删除，并开始处理下一个-节点。 其余的-节点都放在while 循环的第二种情况中处理。首先，为每个-节点生成它的两个子节点，由于每个-节点代表着一条可行的路径x 0 : s ，因此当且仅当 是有向图的边且x i 是路径x s + 1 : n - 1 上的顶点时，它的子节点可行。对于每个可行的孩子节点，将边 的耗费加上。cc 即可得到此孩子节点的路径前缀( x 0 : s ，x) 的耗费cc。由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边，因此任何叶节点对应的耗费都不可能小于cc加上离开各剩余顶点的出边耗费的最小值之和，因而可以把这个下限值作为-节点所生成孩子的lcost值。如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费bestc，则把新生成的孩子加入活节点队列(即最小堆)中。如果有向图没有旅行路径，程序返回NoEdge，否则，返回最优旅行路径的耗费，而最优旅行路径的顶点序列存储在数组v 中。2.3回溯法解旅行售货员问题2.3.1 回溯法思想简介 回朔法有“通用解题法”之称，它采用深度优先方式系统地搜索问题的所有解，基本思路是:确定解空间的组织结构之后，从根结点出发，即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点，这个结点成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向转移，则当前扩展结点成为死结点。此时，回溯到最近的活结点处，并使其成为当前扩展结点，回溯到以这种工作方式递归地在解空间中搜索，直到找到所求解空间中已经无活结点为止。2.3.2 回溯法求解旅行售货员问题旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成的所有排列的递归算法类似。设开始时x= 1，2， n ，则相应的排列树由x 1: n 的所有排列构成。找旅行售货员回路的回溯算法Backtrac是类Traveling的私有成员函数，TSP是Traveling的友员。TSP(v)返回旅行售货员回路最小费用。整型数组v返回相应的回路。如果所给的图不含旅行售货员回路，则返回NoEdge。函数TSP所作的工作主要是为调用Backtrack所需要变量初始化。由TSP调用Backtrack(2)搜索整个解空间。在递归函数Backtrack中，当i = n时，当前扩展结点是排列树的叶结点的父结点。此时，算法检测图是否存在一条从顶点x n-1 到顶点x n 的边和一条从顶点x n 到顶点1的边。如果这两条边都存在，则找一条旅行售货员回路。此时，算法还需判断这条回路的费用是否优于已找到的当前最优回路的费用best。如果是，则必须更新当前最优值bestc和当前最优解bestx。当时，当前扩展结点位于排列树的第层。图中存在从顶点x i-1 到顶点x i 的边时，x 1: i 构成图的一条路径，且当x 1: i 的费用小于当前最优值时，算法进入排列树的第层。否则将剪去相应的子树。算法中用变量cc记录当前路径x 1:i 的费用。具体算法程序见附录B。2.3.3 回溯法的不足在没有特殊条件约束的情况下,构成问题的是无向带权图，而周游路线是环形封闭路线；因此，可以明显看出，回溯法构成的解空间树中存在着大量的重复解。个连通城市的问题构成的解空间树中，其叶子结点的数目为，而经过分析，重复的解路径数目达到整个解空间路径数目的一半。在不考虑约束函数时，整个搜索有一半是无效搜索，这大大降低了搜索的效率。2.3.4 回溯算法的改进对算法改进的基本思想：在建立解空间树后，使用新方法将已建立的解路径反转，找出其重复解，然后从解空间树中将其删除，直到删除所有的重复解4。改进算法的描述如下：建立解空间树后，从第一条解路径开始，记录当前路径,按照相反顺序将其存入数组recorder中，然后参照数组内容,直接查找要删除的枝,进行子树删除；在删除的过程中，先判断其父节点有无其它子树，如果有则删除现有枝，如果没有，继续向上查找父节点,直找到有其它子树的父节点，删除此枝。for ( i = 1; i = leanfnum; i+) void recordpath i ( ) int recordarr M = new array dep three( );for ( m=0; m = pathedgedep three()-m;search recorder ;void deletesub( edge s)doif super j(s)delete s;Leafnum- - ;break;else j+;while (j H(1000); / 定义一个最多可容纳1000个活节点的最小堆T *MinOut = new T n+1; / 计算MinOut = 离开顶点i的最小耗费边的耗费 T MinSum = 0; / 离开顶点i的最小耗费边的数目 for (int i = 1; i = n; i+) T Min = NoEdge; for (int j = 1; j = n; j+) if (aj != NoEdge & (aj Min | Min = NoEdge) Min = aj; if (Min = NoEdge) return NoEdge; / 此路不通 MinOut = Min; MinSum += Min; MinHeapNode E; / 把E-节点初始化为树根 E.x = new int n; for (i = 0; i n; i+) E.x = i + 1; E.s = 0; / 局部旅行路径为x 1 : 0 E.cc = 0; / 其耗费为0 E.rcost = MinSum; T bestc = NoEdge; / 目前没有找到旅行路径 / 搜索排列树 while (E.s n - 1) if (E.s = n - 2) / 不是叶子/ 叶子的父节点 / 通过添加两条边来完成旅行 / 检查新的旅行路径是不是更好 if (aE.xn-2E.xn-1 != NoEdge & aE.xn-11 != NoEdge & (E.cc + aE.xn-2E.xn-1 + aE.xn-11 bestc | bestc = NoEdge) / 找到更优的旅行路径 bestc = E.cc + aE.xn-2E.xn-1 + aE。xn-11; E.cc = bestc; E.lcost = bestc; E.s + + ; H.I n s e r t ( E ) ; else delete E.x; else / 产生孩子 for (int i = E.s + 1; i n; i+) if (aE.xE.sE,x != NoEdge) / 可行的孩子， 限定了路径的耗费 T cc = E.cc + aE.xE.sE.x; T rcost = E.rcost - MinOutE.xE.s; T b = cc + rcost; /下限 if (b bestc | bestc = NoEdge) / 子树可能有更好的叶子 / 把根保存到最大堆中 MinHeapNode N; N。x = new int n; for (int j = 0; j n; j+) N.xj = E.xj; N.xE.s+1 = E.x; N.x = E.xE.s+1; N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; H.I n s e r t ( N ) ; / 结束可行的孩子 delete E。x; / 对本节点的处理结束 try H。DeleteMin(E); / 取