1、- I - 摘 要 旅行售货员问题是一个古老而典型的NP组合优化问题。对该问题合理而有效的解 法不但有重要的理论和学术意义，同时对众多工程实际中的应用提供了重要的指导意 义。 这篇论文首先对TSP问题进行了大体的陈述，对其进行了数学描述。在此基础上, 本文对TSP问题进行了进一步的定义。论文介绍了五种算法的基本概念、原理、意义及 发展现状。这五种算法包括动态规划法、分支界限法、回溯法、遗传算法和微粒子算法。 并展示了部分算法的部分数学过程。 关键词：关键词：旅行售货员旅行售货员问题问题；遗传算法；遗传算法；微粒子算法；微粒子算法；回溯法回溯法 旅行售货员问题 - II - Several So
2、lutions to Traveling Salesman Problem Abstract Traveling salesman problem is an old and typical NPhard 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 engineer
3、ing applications. The essay starts with the general account of TSP, explains the mathematical description of TSP. On the original basis, the essay made through classification of TSP; The essay introduced the basic concept, principle, procedure and significance of five types of algorithm, including d
4、ynamic 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 - III - 目 录 摘 要 . I Abstract II 引 言 1 1 旅行售货员问题的
5、研究现状 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 三种精
6、确算法的比较 . 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 旅行售货员问题 - IV - 4.1 微粒子算法历史 . 15 4.3 微粒子算法结合旅行售货员问题 . 15 5 旅行售货员问题的应用 16 结 论 17 参 考 文 献 18 附录 旅行售货员问题的最小耗费分枝定界算法 19 附录 旅行售货员问题的回溯法 22 致 谢 错误错误!未定义书签。未定义书签。 - 1 - 引 言 旅行售货员问题(Traveling Salesman Problem)， 是计算机算法中的一个经典的难解问 题，已归为NP完备问题(Non polynomial)类。围绕着这个问题有各种不同的求解方法， 已有的算法如动态规划法，分支限界法
