浅议旅行商问题的求解.doc

浅议旅行商问题的求解

本文共计24页，8592字；

摘 要

旅行商问题(TSP问题)就是一销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。它是组合优化中研究最多的问题之一，是一个经典的NP难题。吸引了许多不同领域的研究工作者，包括数学、运筹学、物理、生物和人工智能等领域，它是目前优化领域里的研究热点。
目前解决旅行商问题有诸多算法，神经网络、遗传算法、免疫算法等，在各种解决旅行商问题的算法中，还是存在很多问题。
本次设计尝试使用最小生成树来求解旅行商问题。在对题目要求进行深入分析的基础上，对原有算法进行了多方面改进，并用C语言进行了实现。采用选取排除最长路径顶点的方法降低时间复杂度、采用比较顶点次序的方法提高算法准确性，通过自动产生顶点坐标降低输入复杂性和测试的准确性，实验结果表明该算法可以取得较好的效果。

关键词：TSP,最小生成树,最短路径,组合优化
ABSTRACT
Traveling Sale-man Problem (TSP) means a sale-man starts from a city among n city, and passes by every city and return the origin non-repeatedly. From all the routes the shortest is selected and is adopted as the solve. TSP is the most important problem in the combined optimization area, and a NP-hard problem. It has already attracted many researchers from all areas, including mathematics, operational research, physics, biology, and artificial intelligence, at the same time, it is a hotspot in the current optimization area.
目 录
摘要…………………………………………………………………………………………………………………..3
ABSTRACT……………………………………………………………………………………………………3
一． 引言………………………………………………………………………………………...4
1． 背景介绍…………………………………………………………………………..4
2． 存在主要问题…………………………………………………………………..4
3． 本文主要内容…………………………………………………………………..4
二. 设计分析……………………………………………..………………………….………5
1设计题目……………………………………………..………………………….………5
(1)题目要求……………………………………..…..………………………….……….5
(2)题目分析…………………………………………………………………….……….5
2输入分析………………………………………………………………………………..5
3查找路径……………………………………………………………………………..…5
（1）最小生成树……………………………………………………………………….5
（2）求解最小生成树………………………………………………………………...6
（3） TSP路径查找…………………………………………………………………..7
4输出分析………………………………………………………………………………..7
三. 算法设计………………………………………………………………………………..8
1输入设计…………………………………………………………………………………8
2 TSP路径查找设计…………………………………………………………………9
3输出设计………………………………………………………………….……………..9
四. 算法改进……………………………………………………………………………....11
1降低时间复杂度………………………………………………………....…………11
2提高算法准确性…………………………………………………………….…...…11
3降低输入复杂性…………………………………………………………….……...12
五. 结束语……………………………………………………………….………….…..…..13
致谢………………………….………………………………………………………….……..…13
参考文献…………………………………………………………………………….……...…13
附录1 源程序代码……………………………………………………………………..14
附录2 运行实例……………………………………………………………….………...22
参考文献

1. 谭浩强，C语言程序设计（第二版）， 清华大学出版社,1998.5

2. 张基温, C/C++程序设计教程, 高等教育出版社,1997.4

3. 吴伟民, 数据结构（C语言版）, 清华大学出版社,2000.5

4. 靳蕃, 神经网络与神经计算机（原理与应用） ,西南交通大学出版社,1999.6