[1]孙宪丽 王敏 李颖.求解TSP问题的一种启发式算法[J].计算机技术与发展,2010,(10):70-73.
　SUN Xian-li,WANG Min,LI Ying.A Heuristic Algorithm to Solve Travelling Salesman Problem[J].,2010,(10):70-73.
点击复制

求解TSP问题的一种启发式算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2010年10期
页码:
70-73
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
A Heuristic Algorithm to Solve Travelling Salesman Problem
文章编号:
1673-629X（2010）10-0070-04
作者:
孙宪丽1 王敏2 李颖2
[1]沈阳工程学院信息系[2]沈阳工程学院基础部
Author(s):
SUN Xian-li; WANG Min; LI Ying
[1]Department of Information Science and Engineering,Shenyang Institute of Engineering[2]Department of Basic Courses,Shenyang Institute of Engineering
关键词:
旅行商问题; 启发式算法; 最小生成树
Keywords:
travelling salesman problem;  heuristic algorithm;  minimal spanning tree
分类号:
TP301.6
文献标志码:
A
摘要:
TSP问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义。根据TSP问题的特点,借鉴无向完全图上最小生成树的生成过程,设计了一种启发式算法对TSP问题进行求解。该算法的基本思想是以无向完全图上不同最小生成树为基础,采用启发式的方法构造不同闭合回路,最后取最短闭合回路作为最优解。文中采用C语言编程,同时分析了算法的性能和时间复杂度,并进行了大量仿真计算。结果表明设计的算法能够有效求得TSP问题的优化解
Abstract:
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

相似文献/References:

[1]邓义乔 张代远.蚁群算法在搜索引擎系统中的应用研究[J].计算机技术与发展,2009,(12):21.
　DENG Yi-qiao,ZHANG Dai-yuan.Research and Application of Ant Colony Algorithm in Searching Engine System[J].,2009,(10):21.
[2]段凤玲 李龙澍 曹文婷.具有多态特征和聚类处理的蚁群算法[J].计算机技术与发展,2009,(12):77.
　DUAN Feng-ling,LI Long-shu,CAO Wen-ting.Ant Colony Algorithm with Polymorphism and Clustering Processing[J].,2009,(10):77.
[3]杨益 方潜生 高翠云.求解TSP问题的遗传算法硬件实现[J].计算机技术与发展,2009,(04):54.
　YANG Yi,FANG Qian-sheng,GAO Cui-yun.Implementation of Hardware Based on Genetic Algorithm for Solving TSP Problem[J].,2009,(10):54.
[4]刘艳丽 刘希玉.启发式算法在计划排产中的应用[J].计算机技术与发展,2008,(03):221.
　LIU Yan-li,LIU Xi-yu.Application of Heuristic Algorithm in Task Scheduling[J].,2008,(10):221.
[5]王艳玲 李龙澍 胡哲.群体智能优化算法[J].计算机技术与发展,2008,(08):114.
　WANG Yan-ling,LI Long-shu,HU Zhe.Swarm Intelligence Optimization Algorithm[J].,2008,(10):114.
[6]王娟 王建.一种求解TSP问题的改进蚁群算法[J].计算机技术与发展,2008,(12):50.
　WANG Juan,WANG Jian.An Improved Ant Colony Algorithm for Solving TSP Problem[J].,2008,(10):50.
[7]苏劲松 周昌乐 蒋旻隽.一种基于逆转算子的求解TSP问题的改进演化算法[J].计算机技术与发展,2007,(07):94.
　SU Jin-song,ZHOU Chang-le,JIANG Min-jun.An Improved Evolutionary Algorithm for Traveling Salesman Problem Based on Inver- Over Operator[J].,2007,(10):94.
[8]陈文兰 戴树贵.求解旅行商问题的混合蚂蚁算法[J].计算机技术与发展,2007,(07):110.
　CHEN Wen-lan,DAI Shu-gui.A Hybrid Ant Colony Algorithm for Solving Traveling Salesman Problem[J].,2007,(10):110.
[9]廖芳芳 周俊.棉纺织企业多目标优化计划调度系统开发[J].计算机技术与发展,2006,(06):26.
　LIAO Fang-fang,ZHOU Jun.Development of an Optimal Planning and Scheduling System with Multigoals[J].,2006,(10):26.
[10]赵玉章 郭文强 冯昊[].基于二点组合算法的旅行商问题应用性能分析[J].计算机技术与发展,2011,(10):137.
　ZHAO Yu-zhang,GUO Wen-qiang,FENG Hao.Performance Analysis of Two Vertices Combination Algorithm in TSP[J].,2011,(10):137.

备注/Memo

备注/Memo:
辽宁省自然科学基金（20082135）孙宪丽（1971-）,女,副教授,研究方向为分布式决策理论与应用、建模与优化
更新日期/Last Update: 1900-01-01