Traveling Salesman Problem
A classic optimization problem for finding the shortest possible route visiting a set of cities exactly once
The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits a given set of cities exactly once each and returns to the starting city, and it is one of the most famous NP-hard problems in computer science.
Definition
The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits a given set of cities exactly once each and returns to the starting city, and it is one of the most famous NP-hard problems in computer science.
Overview
TSP is deceptively easy to state and famously hard to solve exactly at scale: given n cities and the distances between every pair, find the minimum-length tour that visits each city exactly once before returning home. The number of possible tours grows factorially with the number of cities — (n-1)!/2 for a symmetric distance matrix — so brute-force enumeration becomes computationally infeasible well before n reaches even a few dozen cities, despite the problem's simple phrasing. Exact algorithms exist that do better than brute force. The Held-Karp dynamic programming algorithm solves TSP exactly in O(n²·2ⁿ) time by using bitmasks to represent subsets of visited cities, a substantial improvement over factorial growth but still exponential and impractical beyond roughly 20-25 cities. Because TSP is NP-hard — and its decision-problem variant is NP-complete — no known algorithm solves it exactly in polynomial time, and it's widely believed (though not proven) that none exists, tying TSP directly to the P vs NP question that remains one of the most important open problems in theoretical computer science. Because exact solutions don't scale, practical applications almost always rely on approximation and heuristic algorithms that find a good, though not guaranteed optimal, tour quickly. Nearest-neighbor and greedy-edge constructions build a reasonable tour fast; 2-opt and Lin-Kernighan local search algorithms then iteratively improve an existing tour by swapping edges; and for the metric TSP variant (where distances satisfy the triangle inequality), the Christofides algorithm guarantees a tour within 1.5 times the optimal length. TSP and its variants underpin real-world logistics and routing problems — vehicle routing for delivery fleets, PCB drilling paths in circuit board manufacturing, DNA sequencing assembly, and network design — making it one of the rare purely theoretical hard problems that shows up constantly in industrial optimization software.
Key Concepts
- Finds the shortest tour visiting every city exactly once and returning to start
- Number of possible tours grows factorially, making brute force infeasible at scale
- NP-hard problem; its decision variant is NP-complete
- Held-Karp dynamic programming solves it exactly in O(n²·2ⁿ) time
- No known polynomial-time exact algorithm exists
- Heuristics (nearest neighbor, 2-opt, Lin-Kernighan) find good approximate solutions fast
- Christofides algorithm guarantees a 1.5x-optimal tour for metric TSP
- Directly connected to the unresolved P vs NP question
Use Cases
Frequently Asked Questions
From the Blog
What Is a Problem Statement? A Practical How-To Guide
A problem statement is a concise description of an issue that needs solving, written so a team can align on what to fix before jumping to solutions. This guide explains its structure and how to write one well.
Read More Career GrowthProblem Solving Skills: How to Build and Show Them
Problem solving is the ability to define a problem clearly, generate options, and choose a workable solution under real constraints. This guide breaks down the process into steps you can practice and demonstrate at work.
Read More Data ScienceHow to fix the small files problem in a data lake
Queries slow down when a table is split across a very large number of small files, because per-file overhead — listing, opening, reading metadata, scheduling a task — starts to dominate the actual reading. Fix it in order: partition cardinality first, writer parallelism second, compaction third.
Read More ProgrammingHow to design API error responses with problem details
Give every error in your API one shape that tells a client three things: which class of failure it is, what specifically was wrong, and whether retrying could help. This article covers the problem details fields, stable error types, field-level validation and what must never leak.
Read More