这些算法虽然对些小规模的问题可精确求解，但计算的复杂度与城市的数目成指数增长。

在大规模的问题上，这些精确算法显得无能为力，而且容易产生组合爆炸，因而人们退而寻求非尽善尽美的所谓启发式算法近似算法，来处理各种实际问题。

七十年代和八十年代是启发式算法的全盛时期，但由于绝大多数启发式算法都是按种确定性的搜索规则来运行，想要改进所得解的可能性极小。

因此，从八十年代后期直到九十年代，些来自其它学科的新代求解方法相继出现，在组合优化问题的求解中取得相当的成功和系列成果。

尽管仍未找到最优解，但是求解它的算法逐渐改进。

年，马良总结归纳出年到年国内外近几十年求解的算法，可分为两类类是精确算法如线性规划动态规划分枝定界法等另类是近似算法启发式算法，如插入算法算法神经网络算法模拟退火算法遗传算法蚂蚁算法等。

目前，对于求解问题，国内外都有相当好的进展，年，周培德用点集凸壳的多项式时间算法解决了个顶点的中国货郎担问题。

年，美国加利弗利亚大学根据出度入度均为的的有向图中有条路的这特性，提出了用算法求解出度入度均为的。

几十年来对于求解问题出现了很多传统方法，其中有精确算法如线性规划方法动态规划方法分支定界方法近似优化算法有插入法最近邻算法灯混合算法概率算法等。

近年来，有很多解决该问题的较为有效的智能方法不断被推出，例如禁忌搜索方法遗传算法模拟退火算法等。

时至今日，人们己经发现有许多问题本质上都可归结为个或是将其作为个子问题来处理，但要想真正有效的求解，目前仍然是件很困难的事。

而由引伸出来的些扩展问题，如瓶颈问题多目标问题等，却由于本身的难度而直少人问津。

旅行售货员问题的数学描述旅行售货员问题，也称货郎问题找到更优的旅行路径摘要旅行售货员问题是个古老而典型的组合优化问题。

对该问题合理而有效的解法不但有重要的理论和学术意义，同时对众多工程实际中的应用提供了重要的指导意义。

这篇论文首先对问题进行了大体的陈述，对其进行了数学描述。

在此基础上，本文对问题进行了进步的定义。

论文介绍了五种算法的基本概念原理意义及发展现状。

这五种算法包括动态规划法分支界限法回溯法遗传算法和微粒子算法。

并展示了部分算法的部分数学过程。

关键词旅行售货员问题遗传算法微粒子算法回溯法我们通常认为它是简单的，对于个问题，通常认为它是复杂的。

表示非确定的多项式，意思是这个问题的解可以用非确定性的算法猜出来。

如果我们有个可以猜想的机器，我们就可以在合理的时间内找到个比较好的解。

完全问题学习的简单与否，取决于问题的难易程度。

因为有很多问题，它们的输出极其复杂，比如说人们早就提出的类被称作难题的问题。

这类问题不像完全问题那样时间有限的。

因为问题由上述那些特征，所以很容易想到些简单的算法把全部的可行解算遍。

但是这种算法太慢了通常时间复杂度为指数次在很多情况下是不可行的。

现在，没有知道有没有那种精确的算法存在。

证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了，或许你就是成功者。

本篇论文就是想用几种方法来就个销售商从几个城市中的城市出发，不重复地走完其余个城市，并回到原出发点，在所有可能的路径中求出路径长度最短的条，比较是否是最优化，哪种结果好。

目前求解旅行商问题的方法可以分为两大类类是精确算法，目的是要找到理论最优解另类是近似算法，不强求最优解，只要找到足够好的满意解就可以了。

在本文中，我们将对两类算法分别选取若干种进行分析。

旅行售货员问题的研究现状旅行售货员问题概述旅行售货员问题是十九世纪初爱尔兰的数学家和英国数学家提出的，通常被描述为对给定城市交通网络，如何为个推销商选择条路线，从网络的点驻地出发，经过每个结点后回到出发点，使得总行程最短。

问题是著名的完全难题，也是组合优化计算机科学界经典的问题之。

它在广泛的应用于运输生产国防生物计算机等领域以外，还为离散优化中各类算法提供了思想方法平台，因而对旅行售货员问题求解方法的研究具有重要的实际价值。

标准的在图论的意义就是所谓的最小圈问题。

由于其在许多领域都有着广泛的应用，因而寻找其实际而又有效的算法显得颇为重要，遗憾的是，计算复杂性理论给予我们的结论是这种可能性尚属未知。

在理论上已归结为所谓的完备问目录摘要引言旅行售货员问题的研究现状旅行售货员问题概述旅行售货员问题的数学描述旅行售货员问题的分类前人的工作精确算法启发式算法本章小结精确算法求解策略及优化算法动态规划法解旅行售货员问题动态规划思想简介动态规划求解旅行售货员问题分支限界法解问题回溯法解旅行售货员问题回溯法思想简介回溯法求解履行商问题回溯法的不足回溯算法的改进三种精确算法的比较动态规划法和回溯法的比较分支限界法和回朔法的比较遗传算法解决旅行售货员问题启发式算法简介遗传算法介绍遗传算法发展遗传算法自身特点遗传算法总结基本遗传算法求解旅行售货员问题微粒子算法简介微粒子算法历史微粒子算法结合旅行售货员问题旅行售货员问题的应用结论参考文献附录旅行售货员问题的最小耗费分枝定界算法附录旅行售货员问题的回溯法致谢， 引言旅行售货员问题，是计算机算法中的个经典的难解问题，已归为完备问题类。

围绕着这个问题有各种不同的求解方法，已有的算法如动态规划法，分支限界法，回溯法等，这些精确式方法都是指数级的，根本无法解决目前的实际问题，贪心法是近似方法，而启发式算法不能保证得到的解是最优解，甚至是较好的解释。

所以我认为很多问题有快速的算法多项式算法，但是，也有很多问题是无法用算法解决的。

事实上，已经证明很多问题不可能在多项式时间内解决出来。

但是，有很多很重要的问题他们的解虽然很难求解出来，但是他们的值却是很容易求可以算出来的。

这种事实导致了完全问题。

凡是在多项式复杂程度内可以求出最优解的问题，称为问题，其它的则是问题。

在算法问题上，假如个问题是问题验，动态的调整自己的速度和飞行的方向，继而促使整个群体向着可能解区域逼近，有效地解决优化问题。

目前，微粒群算法现已被广泛应用于各种优化问题及工程应用领域，包括多目标优化组合优化神经网络训练聚类分析数据挖掘图像处理机器人路径规划以及电力系统的控制等等许多的领域。

在本章中着重对这算法进行研究和应用。

微粒子算法结合旅行售货员问题微粒群算法在问题上的研究，既为大规模复杂问题的求解提供了新的设计方法，又为这样具有实际应用价值的问题的解决提供了新的思路。

然而微粒群算法在算法诞生的最初段时间，其优化方程用于解决连续领域的优化问题，不适用离散领域。

所以，必须在遵守原有算法优化机理的前提下，对算法的优化方程进行重新的定义，因此，需要更加广泛深入地挖掘和利用生物群智能的现象和机理，改进和完善已有的计算方法。

从而有效的将微粒群算法用于解决这样的离散问题，能算法在组合优化和问题等实际应用领域的研究有着深远的意义。

其研究成果必将推动组合优化微粒群算法的研究和发展。

继而扩展算法在组合优化领域的应用。

通过微粒群算法在问题上的研究，对于智能算法在组合优化和问题等实际应用领域的研究有着深远的意义。

其研究成果必将推动组合优化微粒群算法的研究和发展。

旅行售货员问题的应用广泛的应用于运输生产国防生物计算机应用等领域以外，还为离散优化中其他各类算法提供了思想方法平台，例如印刷电路板的钻孔路线方案，连锁店的货物配送路线，数控机床的运作等问题，经过简单处理，均可建模为问题，因而对寻找出有效的启发式算法，就具有重要的理论意义。

同时也具有重要的实际应用价值。

很自然的作为大量的运输和后勤应用的个子问题提出。

例如，在小区内如何安排校车路线接送学生的问题，因为它对二十世纪四十年代初位研究的先驱者的研究提供了源动力，所以这个运输应用对有着重要的历史意义。

从年开始问题的第二个应用包括从地运输农耕设备到另个地方去检测土壤，这吸引了孟加拉的和爱荷华州的数学研究明遗传算法理论西安西安交通大学出版社，席裕庚等遗传算法综述控制论轮与实践，曾建潮，王丽芳种广义微粒算法模型模型识别与人工智能，戚玉涛，焦李成，刘芳解问题的自适应规约免疫算法软件学报，介婧，曾建潮，韩崇昭基于群体多样性反馈控制的自组织微粒群算法计算机研究与发展，附录旅行售货员问题的最小耗费分枝定界算法旅行售货员问题的最小耗费分枝定界算法定义个最多可容纳个活节点的最小堆计算离开顶点的最小耗费边的耗费离开顶点的最小耗费边的数目，此路不通把节点初始化为树根局部旅行路径为其耗费为目前没有找到旅行路径搜索排列树不是叶子叶子的父节点通过添加两条边来完成旅行检查新的旅行路径是不是更好，。

更多的新近的应用包括电报公司中呼叫服务的时序安排，货舱中栈式起重机的路线安排，收邮包的卡车行车路线安排等等。

虽然运输问题是最自然的应用，但由于其模型的简单性，使得在其它领域都有着有趣的应用。

例如如何安排机器在块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从个孔移到下个孔所花的时间。

在减少费用上就扮演了个非常重要的角色。

另外，还应用于如基因工程中序列的计算，以及网络中组播路由问题等其他方面的问题。

问题具有广泛的应用背景，因此有效的解决这个被归入世纪的科学难题，在可计算理论上具有重要的理论意义，同时也具有重要的实际应用价值。

这就是本文写作的意义所在结论旅行售货员问题是著名的完全难题，也是组合优化计算机科学界最经典的问题之。

它在广泛的应用于运输生产国防生物计算机等领域以外，还为离散优化中各类算法提供了思想方法平台。

因而对寻找出实际而又有效算法，就具有重要的理论意义，同时也具有重要的实际应用价值。

这也说明了，首先