第十三章 用最小生成树解决TSP问题.pdfVIP

( ) 第 24 卷 湖北师范学院学报 自然科学版 Vol24 第 4 期 Journal of Hubei Normal University (Natural Science) No 4 ,2004 用最小生成树解决 TSP 问题 姚建华 ,杨成涛 (济南 94534 部队 ,山东 济南 　250002) ( ) 摘要 :旅行商问题 Traveling Salesman Problem , TSP 问题 是组合优化领域中研究最多的问题之一 ,是一个 经典的N P 难题 ,也是 目前优化领域里的研究热点 。目前解决旅行商问题有诸多算法 ,神经网络 、遗传算 法 、免疫算法等 ,在各种解决旅行商问题的算法中 ,还是存在很多问题 。本文用最小化生成树来求解旅行 商问题 。在对题 目要求进行深入分析的基础上 ,对原有算法进行了多方面改进 ,并用 C 语言进行了实现 。 采用选取排除最长路径顶点的方法降低时间复杂度 、采用比较顶点次序的方法提高算法准确性 、通过 自动 产生顶点坐标降低输入复杂性和测试的准确性 ,实验结果表明该算法可以取得较好的效果 。 关键词 : TSP ;最小生成树 ;最短路径 ;组合优化 中图分类号 : TP30 1. 6 , TP3 12 　　文献标识码 :A 　　文章编号 :100927 14 (2004) 04 0052 05 ( ) 　　旅行商问题 Traveling Salesman Problem , TSP 问题 就是一个销售商从 n 个城市中的某一城市 出发, 不重复地走完其余 n - 1 个城市并回到原出发点, 在所有可能的路径中求出路径长度最短的一 条, 是组合优化领域 中研究最多的问题之一 。从 50 年代 中起, 出版 了大量关于本 问题 的文献 。 L awler 编辑的书对到当时为止的所有主要研究成果作了全面深入的综述 。 对于求解旅行商问题, 有许多方法和思路, 目前最流行的是神经网络算法与遗传算法, 在本次设 计中, 应用最小生成树的解题思路, 来解决旅行商问题 。本文中包括了对旅行商问题和最小生成树解 题思路的论述, 给出了解决旅行商问题的算法设计 。 由题 目要求可知, 对于旅行商问题, 城市的数 目是根据用户的需求而改变的, 而对于所确定数 目 的 n 个城市来说, 每两个城市之间都有相互连通的路径, 且路径的长度是不尽相同的。 对于所求的路径, 要求销售商可从 n 个城市中的任意一个城市 V i 出发, 经过其余所有的 n - 1 个城市, 除出发点 V i 外, 其余 n - 1 个城市在路径中不能重复出发, 即除出发点外, 其余所有城市必 须经过且仅经过一次 。由于每两个城市间的路径长度不完全相同, 因此每条符合上述要求的路径其 长度也不同, 在其中选择一条路径长度最短的就为 TSP 问题所求的最短路径 。 1 　算法设计 　　对于 N 个城市的 TSP 问题 ,其城市的数 目应为 N 。若 N 个城市中, 每两个城市之间都有连通 ( ) 的路径, 其连通路径数 目应为 n n - 1 / 2 。而对于含有个顶点无向连接图来说, 其完全图的边数 ( ) 也为 n n - 1 / 2 , 因此可以用含有 n 个顶点的完全连通无向图来形象的描绘 TSP 问题的已知条 件 ,而此完全连通无向图中每条边上的权值 ,可以表示 TSP 问题中每两个顶点之间的路径长度 。因 此在其后的设计中 ,使用带权的完全无向连通图来分析 TSP 问题的求解过程 。