Traveling Salesman Problem
Nearest-neighbor heuristic + 2-opt improvement — click canvas to add cities
Click canvas to add cities, or use Random Cities button
About: The Traveling Salesman Problem (TSP) asks for the shortest tour visiting all cities exactly once. It is NP-hard: no polynomial-time algorithm is known, and the best exact algorithms run in O(n² 2ⁿ) (Held-Karp). Nearest Neighbor greedily visits the closest unvisited city — fast but can yield tours 20-25% above optimal. 2-opt improves the tour by repeatedly reversing segments that reduce total length: if swapping edges (i,i+1) and (j,j+1) shortens the tour, do it. Iterated 2-opt typically reaches within 5% of optimal. For real-world logistics, modern solvers combine LKH (Lin-Kernighan-Helsgott), branch-and-cut, and machine learning to solve instances with millions of cities.