求解TSP算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (29): 43-47.

求解TSP算法

周康^1,2,强小利¹,同小军^1,2,许进¹

1.华中科技大学控制科学与工程系,武汉 430074
2.武汉工业学院数理科学系,武汉 430023

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-11 发布日期:2007-10-11
通讯作者: 周康

Algorithm of TSP

ZHOU Kang^1,2,QIANG Xiao-li¹,TONG Xiao-jun^1,2,XU Jin¹

1.Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China
2.Department of Mathematics and Physics,Wuhan Polytechnic University,Wuhan 430023,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-10-11 Published:2007-10-11
Contact: ZHOU Kang

摘要/Abstract

摘要： 首先提出旅行商问题（TSP）,并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。

关键词: TSP, 传统算法, 现代优化算法, DNA计算

Abstract: TSP is brought forward and is transformed into shortest closed Hamilton loop of directed graph problem.Then three kind of algorithms of TSP is indroduced.One is tradition algorithm,which consists branch and bound method,improving loop method,cupidity algorithm,MST algorithm,MM algorithm,insertion method.Another is modern optimization algorithm which consists simulated annealing algorithm,artificial immune algorithm,genetic algorithm,ant colony algorithm,particle swarm optimization,Tabu Search,Hopfield neural network.The third is algorithm of DNA computing which is designed by authors.Complexity and error range of the DNA algorithm are discussed,and the advantage and shortcoming points of algorithms are analyzed.

Key words: traveling salesman problem, tradition algorithm, modern optimization algorithm, DNA computing

周康^1,2,强小利¹,同小军^1,2,许进¹. 求解TSP算法[J]. 计算机工程与应用, 2007, 43(29): 43-47.

ZHOU Kang^1,2,QIANG Xiao-li¹,TONG Xiao-jun^1,2,XU Jin¹. Algorithm of TSP[J]. Computer Engineering and Applications, 2007, 43(29): 43-47.

[1]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[2]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[3]	张子成，韩伟. 求解TSP问题的自适应离散型布谷鸟算法[J]. 计算机工程与应用, 2017, 53(10): 48-54.
[4]	段艳明1，肖辉辉1，2. 求解TSP问题的改进果蝇优化算法[J]. 计算机工程与应用, 2016, 52(6): 144-149.
[5]	万正宜，彭玉旭. 求解旅行商问题的改进型量子蚁群算法[J]. 计算机工程与应用, 2016, 52(22): 59-63.
[6]	李絮，刘争艳. 基于云模型的模糊自适应蚁群算法研究[J]. 计算机工程与应用, 2016, 52(2): 24-27.
[7]	谭莉1，应石2. 多目标优化机制下DNA编码序列模型[J]. 计算机工程与应用, 2016, 52(15): 34-37.
[8]	叶永刚1，徐耀群2. SLF混沌神经网络及其应用[J]. 计算机工程与应用, 2015, 51(21): 74-79.
[9]	马福祥，马秀娟. 一种基于二次变异策略的改进型遗传算法[J]. 计算机工程与应用, 2014, 50(13): 62-65.
[10]	王永国1，胡娇娇1，季学枫2. 实时采集中异常值的自动甄别与纠错方法研究[J]. 计算机工程与应用, 2013, 49(9): 251-254.
[11]	方霞，席金菊. 基于变异和启发式选择的蚁群优化算法[J]. 计算机工程与应用, 2013, 49(24): 24-27.
[12]	姚明海1，2，王娜3，赵连朋1. 改进的模拟退火和遗传算法求解TSP问题[J]. 计算机工程与应用, 2013, 49(14): 60-65.
[13]	孙守霞1，刘伟2，郭迎3，孟大志4. DNA计算机算术运算的自装配模型（III）—减法[J]. 计算机工程与应用, 2012, 48(32): 39-42.
[14]	臧文科1，夏瑞芳2，刘希玉1. MSC问题的一类表面DNA解法[J]. 计算机工程与应用, 2012, 48(22): 14-17.
[15]	程森林，曾伟. 多级规约算法在PCB钻孔路径优化中的应用[J]. 计算机工程与应用, 2012, 48(16): 212-215.