TSP Examples

Optimization · Axiom Academy

EXAMPLE Traveling Salesman Problem (TSP) Comparing exact enumeration with the nearest neighbor heuristic Find the shortest tour visiting all cities exactly once and returning to the start. Excellent work! You've completed this TSP example. Here's what we learned: Exact Enumeration: For small TSP instances (n cities), there are (n-1)!/2 unique tours. This becomes intractable for n > 20 cities. Nearest Neighbor Heuristic: A greedy approach that runs in O(n²) time. Always visit the nearest unvisited city from your current location. Solution Quality: The nearest neighbor heuristic may not find the optimal solution. In this example, it found a tour with length 80 vs optimal 70, giving an approximation ratio of 80/70 = 1.14 (14% worse than optimal). Trade-offs: Exact methods guarantee optimality but are exponential in time. Heuristics provide fast, good-quality solutions with no optimality guarantee. Real Applications: TSP appears in routing, scheduling, circuit design, and DNA sequencing. For large instances, advanced techniques like branch-and-bound, genetic algorithms, or simulated annealing are used. Understanding the trade-off between solution quality and computational time is fundamental in optimization. Practice with different distance matrices to build intuition!

This is the written version of the interactive lesson above. See the full Optimization course.