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

摘要：

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

关键词：旅行商问题、NPC、closest-point、最近点前后插入法、近似算法

所属期刊栏目：42

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2006-12-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：71-73