求解TSP问题的一种启发式算法

摘要：

TSP问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义.根据TSP问题的特点,借鉴无向完全图上最小生成树的生成过程,设计了一种启发式算法对TSP问题进行求解.该算法的基本思想是以无向完全图上不同最小生成树为基础,采用启发式的方法构造不同闭合回路,最后取最短闭合回路作为最优解.文中采用C语言编程,同时分析了算法的性能和时间复杂度,并进行了大量仿真计算.结果表明设计的算法能够有效求得TSP问题的优化解.

关键词：旅行商问题、启发式算法、最小生成树

所属期刊栏目：20

分类号：TP301.6(计算技术、计算机技术)

资助基金：辽宁省自然科学基金20082135

在线出版日期：2010-11-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：70-73,77