求解TSP算法

被引：31

作者：

周康

强小利

同小军

许进

机构：

[1] 华中科技大学控制科学与工程系

来源：

计算机工程与应用 | 2007年 / 29期

基金：

浙江省自然科学基金;

关键词：

TSP; 传统算法; 现代优化算法; DNA计算;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

收藏

页码：43 / 47+85 +85

页数：6

相关论文

共 21 条

[1] TSP的DNA计算算法 [J].

周康 ;

刘文斌 ;

许进 .

系统工程与电子技术, 2007, (02) :316-319

[2] 模拟退火自适应大变异遗传算法及其应用 [J].

邢桂华 ;

朱庆保 .

计算机工程, 2005, (03) :170-172

[3] 基于混合行为蚁群算法的研究 [J].

胡小兵 ;

黄席樾 ;

不详 .

控制与决策 , 2005, (01) :69-72

[4] 一种求解旅行商问题的新型单亲遗传算法 [J].

胡纯德 ;

祝延军 ;

高随祥 ;

不详 .

计算机工程与应用 , 2004, (35) :37-40

[5] 改进微粒群优化算法求解旅行商问题 [J].

肖健梅 ;

李军军 ;

王锡淮 .

计算机工程与应用, 2004, (35) :50-52

[6] 基于人工免疫算法和蚁群算法求解旅行商问题 [J].

胡纯德 ;

祝延军 ;

高随祥 .

计算机工程与应用, 2004, (34) :60-63

[7] 求解旅行商问题的混合粒子群优化算法 [J].

高尚 ;

韩斌 ;

吴小俊 ;

杨静宇 .

控制与决策, 2004, (11) :1286-1289

[8] 旅行商问题的基因整合算法 [J].

燕子宗 ;

费浦生 .

数学杂志, 2004, (05) :531-536

[9] 具有自适应杂交特征的蚁群算法 [J].

朱海梅 ;

朱庆保 ;

胡勇 .

计算机工程与应用, 2004, (22) :81-83+96

[10] Grefenstette编码法的MATLAB实现 [J].

叶欢 ;

经亚枝 .

中国测试技术, 2004, (02) :58-60