Finds shortest tour visiting all vertices exactly once
Time: O(n² × 2ⁿ)
Space: O(n × 2ⁿ)
Use Case: Route optimization, logistics, circuit board drilling
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Traveling Salesman Problem
The Traveling Salesman Problem (TSP) asks for the shortest tour that visits every city exactly once and returns to the start. It is the most famous NP-hard problem in combinatorial optimization, simple to state yet exponentially hard to solve exactly.
How it works
The Held-Karp dynamic programming solution stores, for every subset of cities and every ending city, the cheapest way to visit that subset. Each state is extended by one unvisited city at a time, giving O(n squared times 2 to the n) time, exact but only feasible for roughly 20 cities. Larger instances rely on heuristics such as nearest neighbor and 2-opt, or metaheuristics and branch-and-bound solvers that reach near-optimal tours for thousands of cities.
Applications
TSP models delivery route planning, warehouse order picking, drilling circuit boards, DNA sequencing assembly, and telescope observation scheduling. It anchors the study of NP-completeness and approximation algorithms, and interviewers use it to probe understanding of complexity classes and dynamic programming over bitmasks.