TSP问题的一个新算法

摘要：

本文采用类贪婪算法的多边形增边法经过14次循环搜索到随机20城市的初始优化路线，路长d=4.9779；并以此作为2-opt交换算子深度寻优算法的第一代母体，经过交换配对，搜索到第九代找到最优解，路长d=4.2370；并对大规模城市的情形作出计算仿真，得到比较满意的结果，进一步提出对于时间复杂度问题的讨论，并给出了有效的改进措施。

关键词： 贪婪算法 多边形增边法 交换算子 遗传算法 循环搜索 时间复杂度

作者: 陈华 管乐乐 宗鹏安 黄星星

作者单位: 河海大学常州校区数理部,江苏常州 213022 河海大学常州校区商学院,江苏常州 213022 河海大学常州校区机电学院,江苏常州 213022 河海大学常州校区计信学院,江苏常州 213022

会议类型: 国内会议

会议名称: 全国第20届计算机技术与应用(CACIS)学术会议

会议地点: 南宁

会议语种:中文

页码: 264-267

在线出版日期: 2009-07-17（万方平台首次上网日期，不代表论文的发表时间）