Traveling Salesman Problem

Graph Theory · Axiom Academy

LESSON Traveling Salesman Problem Understanding one of computer science's most famous optimization problems The Traveling Salesman Problem is formally defined as finding a minimum weight Hamiltonian cycle in a complete weighted graph. Complete Graph: Every pair of vertices is connected by an edge Weighted: Each edge has an associated cost (distance, time, etc.) Hamiltonian Cycle: A path that visits each vertex exactly once and returns to the start Objective: Minimize the total weight of the cycle TSP is NP-hard, meaning no known polynomial-time algorithm can solve all instances optimally. The number of possible tours grows factorially with the number of cities. The division by 2 accounts for the fact that a tour and its reverse have the same total distance. The (n-1)! comes from fixing the starting city and permuting the remaining cities. Since exact solutions are often impractical, approximation algorithms provide near-optimal solutions in reasonable time. Different special cases of TSP allow for different quality guarantees. Nearest Neighbor: At each step, visit the closest unvisited city (simple but can be far from optimal) 2-Approximation for Metric TSP: Uses minimum spanning tree; guarantees solution within 2x optimal Christofides Algorithm: For metric TSP, guarantees solution within 1.5x optimal Lin-Kernighan Heuristic: Iterative improvement that often finds excellent solutions

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