用最小生成树解决TSP问题

旅行商问题(Traveling Salesman Problem，TSP问题)是组合优化领域中研究最多的问题之一，是一个经典的NP难题，也是目前优化领域里的研究热点。目前解决旅行商问题有诸多算法，神经网络、遗传算法、免疫算法等，在各种解决旅行商问题的算法中，还是存在很多问题。本用最小化生成树来求解旅行商问题。在对题目要求进行深入分析的基础上，对原有算法进行了多方面改进，并用C语言进行了实现。采用选取排除最长路径顶点的方法降低时间复杂度、采用比较顶点次序的方法提高算法准确性、通过自动产生顶点坐标降低输入复杂性和测试的准确性，实验结果表明该算法可以取得较好的效果。

Research on the TSP problem with minimum spanning tree

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.At present,there are lots of algorithms to solve TSP,such as neural networks,genetic algorithm,immune algorithm.Among all the current algorithms,lots of problems still disturb the researchers.The article tries to resolve the TSP with the minimum spanning tree.Based on the deep analysis of the subject,some improvement is presented in the article,and at last,it is realized by C language.To decrease the time complexity,increase the accuracy and decrease the inputting difference,some skills are adopted.And the research results shows that the algorithm in the article can acquire better results.