The Traveling Salesman

Graph Theory · Axiom Academy

Discover one of computer science's most famous and challenging optimization problems. Imagine you're a salesman who needs to visit 4 cities and return home. Click on the cities below in any order you like to create a route. Use the slider below to see how the number of possible routes grows as we add more cities. TSP is actually about finding a special type of cycle in a weighted graph. Click on cities to build a Hamiltonian cycle (a path that visits every vertex exactly once). Compare how solution time grows for different problem types. Drag the slider to see the dramatic difference. TSP is one of the most studied problems in computer science and optimization. Despite being "simple" to state, it's incredibly difficult to solve efficiently. Delivery route optimization, circuit board drilling, DNA sequencing, telescope observation scheduling, and much more. Any problem requiring efficient sequencing can be modeled as TSP. TSP has driven advances in algorithm design, approximation methods, and our understanding of computational complexity. It remains an active area of research today. Dynamic programming (Held-Karp algorithm), branch and bound, genetic algorithms, simulated annealing, and Lin-Kernighan heuristic are all used to tackle TSP.

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