用最小生成树解决TSP问题

作者：姚建华; 杨成涛tsp最小生成树最短路径组合优化

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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社