TSP Generator (Mathfest 2002)   <-  Sean Forman   <-  You Are Here
   /

TSP Topics

• Computational Complexity: Intuitively, easy. Computationally, difficult.

• Search Space: Number of solutions grows rapidly, $\frac{(N - 1)!}{2}$.

• Heuristics: Nearest Neighbor, Cheapest Link Algorithm, Repetitive Nearest Neighbor.

• Classroom Examples and Problems: Typically, four to six cities, usually fictional with no maps. Data can be hard to come by and map making is onerous.

• Largest current problem solved: 24,978 cities in Sweden (Applegate, Bixby, Chvátal, Cook, and Helsgaun.

  http://www.math.princeton.edu/tsp/