一种改进的求解TSP问题的近似算法

• 作者: 刘艳娟 谢晓钢 陈胜达
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 旅行商问题 NPC closest-point 最近点前后插入法 近似算法
• 年，卷（期）: 2006,（33）
• 所属期刊栏目: 学术探讨
• 页码范围: 71-73
• 页数: 3页
• 分类号: TP301.6
• 字数: 1996字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.33.023

摘要

旅行商问题(TSP)是典型的具有NPC复杂性的组合优化问题.在现有求解TSP问题的2-近似算法closest-point算法基础上,通过对插入点的插入位置进行改进,提出了一种有效的近似算法最近点前后插入法(CPBOA),并采用TSPLIB中的一些典型实例对该算法进行了测试,同时与典型的常数近似比算法MST-PRIM算法和closest-point算法进行了比较.实验结果表明,该算法在求解质量上与closest-point和MST-PRIM算法相比都有很大的改进,而且速度也很快.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈胜达	厦门大学计算机科学系	2	15	2.0	2.0
2	刘艳娟	厦门大学计算机科学系	2	15	2.0	2.0
3	谢晓钢	厦门大学计算机科学系	2	47	2.0	2.0