// sketch

TSP Visualiser

One of computing's hardest unsolved problems — animated.

Controls

› Click — randomise nodes

The Problem

Given n cities, find the shortest round trip that visits each city exactly once. Formally:

min Σ d(c_i, c_i+1) ∀ permutations

The brute-force answer requires checking every possible route — (n−1)! / 2 permutations. For just 20 cities that is 60,822,550,204,416,000 routes. Even the fastest computers cannot search this exhaustively.

NP-Hard

TSP is NP-hard — no known algorithm solves every instance in polynomial time. Whether such an algorithm exists is the famous P vs NP question, one of the Millennium Prize Problems (unsolved, $1M prize).

In practice, we use heuristics — algorithms that find good (not necessarily perfect) solutions quickly.

Reading the Sketch

●Violet dots are the 16 cities. The number above each dot is its index (0 – 15) — a fixed ID, not a visit order.
─Cyan edges form the current tour — the closed loop connecting every city exactly once. Watch them untangle as the algorithm improves the route.
↺Each swap in the panel is one 2-opt improvement: two crossing edges are uncrossed by reversing the segment between them. Each swap makes the tour measurably shorter.

The panel tracks tour (current length), seed (the nearest-neighbour starting length), and saved — the % improvement 2-opt has squeezed out so far.

The Two Phases

1.Nearest-neighbour seed — start at city 0, always jump to the closest unvisited city. O(n²), instant. Typically 20–25% longer than optimal but gives a solid starting point.
2.2-opt improvement — scan every pair of edges. If swapping them shortens the tour, do it and restart the scan. Stops when no improving swap exists (locally optimal).

// swap test:
d(A,B) + d(C,D) > d(A,C) + d(B,D)
→ reverse segment [B…C]

Why It Matters

TSP is not just a puzzle. It underlies logistics routing (delivery networks, airline scheduling), circuit board drilling (minimising drill-head movement), genome sequencing, and telescope scheduling. Shaving even 1% off large-scale tour lengths saves millions in fuel and time.