旅行售货员问题 大学论文.doc

摘 要 旅行售货员问题是一个古老而典型的组合优化问题。对该问题合理而有效的解法不但有重要的理论和学术意义，同时对众多工程实际中的应用提供了重要的指导意义。 这篇论文首先对问题进行了大体的陈述，对其进行了数学描述。在此基础上,本文对问题进行了进一步的定义。论文介绍了五种算法的基本概念、原理、意义及发展现状。这五种算法包括动态规划法、分支界限法、回溯法、遗传算法和微粒子算法。并展示了部分算法的部分数学过程。 关键词：旅行售货员问题；遗传算法；微粒子算法；回溯法 Several Solutions to Traveling Salesman Problem Abstract Traveling 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 目 录 摘 要 I Abstract II 引 言 1 1 旅行售货员问题的研究现状 2 1.1旅行售货员问题概述 2 1.2 旅行售货员问题的数学描述 3 1.3 旅行售货员问题的分类 4 1.4 前人的工作 5 1.4.1 精确算法 5 1.4.2 启发式算法 5 1.5 本章小结 5 2 精确算法求解策略及优化算法 6 2.1动态规划法解旅行售货员问题 6 2.1.1 动态规划思想简介 6 2.1.2 动态规划求解旅行售货员问题 6 2.2分支限界法解问题 6 2.3回溯法解旅行售货员问题 8 2.3.1 回溯法思想简介 8 2.3.2 回溯法求解履行商问题 8 2.3.3 回溯法的不足 9 2.3.4 回溯算法的改进 9 2.4 三种精确算法的比较 10 2.4.1 动态规划法和回溯法的比较 10 2.4.2分支限界法和回朔法的比较 11 3 遗传算法解决旅行售货员问题 12 3.1启发式算法简介 12 3.2 遗传算法介绍 12 3.2.1遗传算法发展 12 3.2.2遗传算法自身特点 13 3.2.3遗传算法总结 13 3.3 基本遗传算法求解旅行售货员问题 14 4 微粒子算法简介 15 4.1 微粒子算法历史 15 4.3 微粒子算法结合旅行售货员问题 15 5 旅行售货员问题的应用 16 结 论 17 参 考 文 献 18 附录Ａ　旅行售货员问题的最小耗费分枝定界算法 19 附录Ｂ　旅行售货员问题的回溯法 22 致 谢 24 引 言 旅行售货员问题(Traveling Salesman Problem)，是计算机算法中的一个经典的难解问题，已归为完备问题(Non polynomial)类。围绕着这个问题有各种不同的求解方法，已有的算法如动态规划法，分支限界法，回溯法等，这些精确式方法都是指数级的，根本无法解决目前的实际问题，贪心法是近似方法，而启发式算法不能保证得到的解是最优解，甚至是较好的解释。所以我认为很多问题有快速的算法(多项式算法)，但是，也有很多问题是无法用算法解决的。 事实上，已经证明很多问题不可能在多