The Traveling Salesman

A delivery driver has twenty stops and one truck. A circuit board needs a drill to hit a thousand holes. A tourist wants to see ten sights in a day and get back to the hotel. All of them face the same question: what's the shortest route that visits every place once and returns to the start?

That's the Traveling Salesman Problem (TSP) — maybe the most famous hard problem of all. It sounds almost trivial: just try the possible orders and pick the shortest. But the orders multiply factorially. Ten cities have over 180,000 routes; twenty cities have more routes than there are grains of sand on Earth; sixty cities outrun the atoms in the universe.

So you can't just check them all. TSP is NP-hard, and along with its cousins on this site it's a poster child for combinatorial explosion. The twist that keeps the world moving: even though the perfect tour is out of reach for big maps, clever methods get astonishingly close — within a few percent of optimal — fast.

Try it. The dots are cities. Click them in the order you'd visit — the demo draws your tour back to the start and measures its total length. Try to make it as short as you can.

<p class="hint">{{hint}}</p>
<svg id="svg" viewBox="0 0 320 250" class="svg"></svg>
<div class="meter">{{tour_length_label}}: <b id="len" class="len">{{dash}}</b><span id="status" class="status"></span></div>
<div class="btns">
  <button id="nn" type="button">{{btn_nn}}</button>
  <button id="opt" type="button">{{btn_opt}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.svg { width: 100%; max-width: 420px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.tour { fill: none; stroke: #457b9d; stroke-width: 2.5; stroke-linejoin: round; }
.city { fill: #8aa0b3; cursor: pointer; transition: fill .1s; }
.city:hover { fill: #457b9d; }
.city.visited { fill: #2a9d8f; }
.city.home { fill: #c0392b; }
.clbl { font: 700 11px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.ord { font: 700 10px system-ui; fill: #1d3557; text-anchor: middle; }
.meter { margin: .8rem 0 .6rem; font-size: 1.05rem; }
.len { color: #1d3557; font-family: ui-monospace, monospace; }
.status { margin-left: .6rem; font: 700 .9rem system-ui; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Then compare. Nearest neighbor greedily hops to the closest unvisited city — fast, but it often paints itself into a long detour at the end. Optimal finds the true shortest tour (by brute force on this small map). Watch the greedy route fall short of the best — that small gap, multiplied across thousands of stops, is exactly why TSP matters and why it's hard.

TSP is the classic hard problem, and a beautiful case study in coping with hardness:

• Checking a tour is easy. Add up the distances between consecutive stops.
• Brute force is factorial. Trying all (n−1)!/2 tours is hopeless past ~15 cities.
• It's NP-hard. Deciding the shortest tour is NP-hard; even approximating general (non-metric) TSP is hard. Its decision version is NP-complete.
• Exact methods reach surprisingly far. Held–Karp dynamic programming solves it in $O(2^{n} \cdot n^{2})$ — fine for ~20 cities — and branch-and-cut solvers (Concorde) have found provably optimal tours through tens of thousands of cities.
• Heuristics get close, fast. For metric TSP (distances obey the triangle inequality), Christofides' algorithm guarantees a tour at most 1.5× optimal. In practice, nearest neighbor then 2-opt/Or-opt local search, and the celebrated Lin–Kernighan (LKH) heuristic, routinely land within 1–2% of optimal on millions of points.
• It's a hub. Many problems reduce to or from TSP, and the same techniques power vehicle routing and scheduling.

So TSP is hard in the worst case yet solved well enough every day — the recurring lesson of this site, in its most iconic form.

The shortest-tour problem is worth billions in the real world:

• Logistics and delivery: planning routes for trucks, couriers and field technicians — the everyday face of TSP (and its vehicle-routing extensions).
• Manufacturing: ordering the holes a drill or the points a laser must hit on a circuit board, minimizing machine travel.
• Genomics: assembling DNA fragments maps onto TSP-like ordering problems.
• Astronomy: scheduling a telescope's slews between targets to waste the least time.
• Warehousing: routing pickers through aisles to fill an order fastest.

Because a small percentage saved scales across millions of routes, TSP solvers and heuristics are a quiet, valuable industry.

The Traveling Salesman is the face on the poster of hard problems. The question is childishly simple, the brute-force answer is impossibly large, and no one knows a fast method that's always exact — if they did, they'd have cracked P vs NP and a million dollars with it.

And yet your packages arrive, your circuit boards get drilled, and your maps suggest good routes — because we stopped demanding perfection and learned to get within a whisker of it, quickly. TSP is the clearest reminder this site offers: a problem can be provably hard and practically conquered at the same time, and the space between "optimal" and "good enough" is where most of the world actually runs.