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

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1982
Accession Number
ADA115357

Entities

People

  • J. J. Bartholdi Iii
  • L. K. Platzman

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Dynamic Programming
  • Engineering
  • Identities
  • Inequalities
  • Mathematics
  • Military Research
  • Operations Research
  • Real Variables
  • Sequences
  • Square Roots
  • Systems Engineering
  • Theoretical Computer Science

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research