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

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