TSP最短路径的必要条件初探

Necessary condition for shortest path of TSP

对于被访问城市数为n的不对称旅行商问题,构造了一个n行和n列的方阵,每一行上的n个元素为同一个被访问城市;每一列上的n个元素为n个互不相同的被访问城市.依次从该方阵的第一列到第k列上各取出一个城市,同一行上不存在两个被取出的城市,这样取出的城市序列就构成了一条长度为k的路径.主要讨论最短路径的性质:如果一条长度为(n-1)的最短路径能被产生,则该路径上的任一长度为k的路径都为最短路径,k=1,2,…,n-2.该性质为旅行商问题算法研究的基础.

For the asymmetrical traveling salesman problem （TSP） with n cities to be visited, a square matrix with n rows and n columns was constructed. Different vertex in each row represented the same city, and n vertex in each column represented n different cities. Taking one city from each column of the 1st colunm to the k^th column in this matrix with only one city at most taken from a row, the k cities formed a traveling salesman＇s path with length k. It is deduced that, if the shortest path with length n- 1 was found, any path of length k （ k = 1,2,…, n-2） on this path was definitely the shortest path. The result provides a basis for further study of the algorithm for the traveling salesman problem.