An O(NlogN) Planar Travelling Salesman Heuristic Based on Spacefilling Curves.

摘要

N points in a square of area A may be sorted according to their images under a spacefilling mapping to give a tour of length at most 2 square root of (NA). If the points are statistically independent under a smooth distribution, with N large, then the tour will be roughly 25% longer than optimum (and a simple enhancement reduces this to 15%). The algorithm is easily coded: a complete BASIC program is included in the appendix. Since the algorithm consists essentially of sorting, points are easily added or removed. Our method may also be used with simple dynamic programming to solve TSP path problems.