摘要
TSP问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义。根据TSP问题的特点,借鉴无向完全图上最小生成树的生成过程,设计了一种启发式算法对TSP问题进行求解。该算法的基本思想是以无向完全图上不同最小生成树为基础,采用启发式的方法构造不同闭合回路,最后取最短闭合回路作为最优解。文中采用C语言编程,同时分析了算法的性能和时间复杂度,并进行了大量仿真计算。结果表明设计的算法能够有效求得TSP问题的优化解。
TSP modelis widely used,its solution strategy research is significant in theory and practice.Based on the characteristics of TSP and the minimum spanning tree generation process on undirected complete graph,a heuristic algorithm is designed to solve TSP.The basic idea of the heuristic algorithms is to construct closed loop base on the different minimum spanning tree on undirected complete graph with heuristic methods,the last to take the shortest closed loop as the optimal solution.Use C language to design the algorithm,and analyze the performance,time complexity,at the same time,a great deal case is tested.The simulation results show that the algorithm designed can effectively obtain the optimal solution of TSP.
出处
《计算机技术与发展》
2010年第10期70-73,77,共5页
Computer Technology and Development
基金
辽宁省自然科学基金(20082135)
关键词
旅行商问题
启发式算法
最小生成树
travelling salesman problem
heuristic algorithm
minimal spanning tree
