Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (35): 46-49.DOI: 10.3778/j.issn.1002-8331.2008.35.014

• 理论研究 • Previous Articles     Next Articles

Efficient approximation algorithm for TSP

SHEN Qing-tao,ZHANG Zhen-yu   

  1. Department of Computer Science,Xinjiang University,Urumuqi 830046,China
  • Received:2008-06-10 Revised:2008-09-10 Online:2008-12-11 Published:2008-12-11
  • Contact: SHEN Qing-tao

高效的求解TSP问题的近似算法

沈庆涛,张振宇   

  1. 新疆大学 信息科学与工程学院计算机系,乌鲁木齐 830046
  • 通讯作者: 沈庆涛

Abstract: This paper proposes a new approach based on the matrix transformation,which can approximately transform the TSP problem to a lower TSP problem and achieve the final solution by recursive algorithm.The time complexity of this algorithm is O(n3).And then,the algorithm is improved while time complexity is O(n4).It is indicated by experimention that the outcome of this algorithm is very efficient,especially in those problem who fulfil triangle inequation.This paper tests the algorithm with the data in TSPLIB,and the error of the outcome not more than 10%.

Key words: Travelling Salesman Problem(TSP), approximation algorithm, matrix transformation

摘要: 提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解。此算法的时间复杂度为O(n3)。而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O(n4)。经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低。利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%。

关键词: 旅行商问题, 近似算法, 变换矩阵