Spacefilling Curves and the Planer Travelling Salesman Problem. Revision.

摘要

This paper analyzes the performance of a novel heuristic to obtain the minimal-length tour of N given points in the plane: they are sequenced as they appear along a spacefilling curve. The algorithm consists essentially of sorting, so it is easily coded and requires only O(N) memory and O(N log N) operations. Its performance is shown to be competitive with that of other available methods. Key words: Planar travelling salesman problem, heuristic algorithm, spacefilling curve.