首页|Generating Cyclic Permutations: Insights to the Traveling Salesman Problem
Generating Cyclic Permutations: Insights to the Traveling Salesman Problem
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Some results for the traveling salesman problem (TSP) are known for a prime number of cities. In this paper we extend these results to an odd number of cities. F or an odd integer n, we show that there is an algorithm that generates n - 1 cyclic permutations, called tours for the traveling salesman problem, which cover the distance matrix. The algorithm allows construction of a two-dimensional array of all tours for the TSP on an odd number of cities. The array has the following properties: (i) A tour on a vertical line in the array moves the salesman uniquely compared to all other tours on the vertical line. (ii) The sum of the lengths of all tours on a vertical line is equal to the sum of all non-diagonal elements in the distance matrix for the TSP.
Cyclic permutationEntangled set of permutationsTraveling salesman problemTour for the salesmanDistance matrixOdd number of cities
NSTL
