| 一种改进的求解TSP问题的近似算法 |
| |
| 引用本文： | 刘艳娟,谢晓钢,陈胜达.一种改进的求解TSP问题的近似算法[J].计算机工程与应用,2006,42(33):71-73. |
| |
| 作者姓名： | 刘艳娟 谢晓钢 陈胜达 |
| |
| 作者单位： | 厦门大学,计算机科学系,福建,厦门,361005 |
| |
| 摘 要： | 旅行商问题(TSP)是典型的具有NPC复杂性的组合优化问题。在现有求解TSP问题的2-近似算法closest-point算法基础上,通过对插入点的插入位置进行改进,提出了一种有效的近似算法最近点前后插入法(CPBOA),并采用TSPLIB中的一些典型实例对该算法进行了测试,同时与典型的常数近似比算法MST-PRIM算法和closest-point算法进行了比较。实验结果表明,该算法在求解质量上与closest-point和MST-PRIM算法相比都有很大的改进,而且速度也很快。
|
| 关 键 词： | 旅行商问题 NPC closest-point 最近点前后插入法 近似算法 |
| 文章编号： | 1002-8331（2006）33-0071-03 |
| 收稿时间： | 2006-02 |
| 修稿时间： | 2006-02 |
Improved Approximation Algorithm for TSP |
| |
| LIU Yan-juan,XIE Xiao-gang,CHEN Sheng-da.Improved Approximation Algorithm for TSP[J].Computer Engineering and Applications,2006,42(33):71-73. |
| |
| Authors: | LIU Yan-juan XIE Xiao-gang CHEN Sheng-da |
| |
| Affiliation: | Department of Computer Science, Xiamen University, Xiamen, Fujian 361005, China |
| |
| Abstract: | Traveling Salesman Problem(TSP) is a typical combinatorial optimization problem.It has been proved that TSP is of NPC complexity.This paper improves the position of inserted point based on 2-approximation algorithm closest-point for solving TSP,and proposes an efficient approximation algorithm CPBOA.Some typical instances in TSPLIB are used to test this algorithm,which are compared with MST-PRIM and closest-point.The computational results show that this algorithm can get better solution,and the time spending is less than closest-point. |
| |
| Keywords: | NPC closest-point |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
