The Travelling Salesman Problem: When Search Explodes

Visit every city once, return home, minimise distance. Why brute force dies at 20 cities, how branch-and-bound and the MST heuristic help, and the approximation algorithms that actually ship.

A salesman must visit each of $n$ cities exactly once and return to the start. Given the distance between every pair, find the shortest possible route.

That’s the entire problem statement, and it is the most-studied optimisation problem in existence. It is also the point on these pages where search stops working. The 8-puzzle has 181,440 states; you can search it exhaustively. TSP with 20 cities has $6 \times 10^{16}$ tours. There is no computer, present or future, that will enumerate them.

Everything interesting about TSP follows from that one fact.

The problem

Input. A distance matrix $D$ where $D[i][j]$ is the cost from city $i$ to city $j$ .

Output. A permutation of the cities — a tour — minimising

$L(\pi) = \sum_{i=0}^{n-1} D[\pi_i][\pi_{(i+1) \bmod n}]$

Two flavours you’ll meet:

Symmetric TSP — $D[i][j] = D[j][i]$ . Roads, straight-line distance.
Asymmetric TSP — one-way streets, wind, uphill. Harder.

And a property that matters for the algorithms below: metric TSP, where the triangle inequality $D[i][k] \le D[i][j] + D[j][k]$ holds. Real geography is metric. The approximation guarantees at the end of this page require it.

The state space, and why it explodes

Fix the starting city (a tour is a cycle, so rotations are the same tour). That leaves $(n-1)!$ orderings. For symmetric TSP, a tour and its reverse are also the same, so:

$\text{distinct tours} = \frac{(n-1)!}{2}$

Put numbers on it. Suppose you can evaluate one billion tours per second — generously fast:

Cities	Tours	Brute-force time
10	181,440	instant
15	4.4 × 10¹⁰	44 seconds
20	6.1 × 10¹⁶	2 years
25	3.1 × 10²³	10 million years
30	4.4 × 10³⁰	10¹⁴ years

Adding one city multiplies the work by roughly $n$ . This is not a problem you optimise your way out of with better hardware — going from 20 to 25 cities costs you a factor of five million, and Moore’s Law never delivered that in a usable timeframe.

TSP is NP-hard. No polynomial-time exact algorithm is known, and finding one would resolve P vs NP. Assume there isn’t one.

Exact method 1: brute force

Worth writing once, so you can verify the clever methods against it on small inputs.

from itertools import permutations

def brute_force(D):
    n = len(D)
    best_tour, best_len = None, float('inf')
    for perm in permutations(range(1, n)):     # city 0 fixed as the start
        tour = (0,) + perm
        length = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
        if length < best_len:
            best_tour, best_len = tour, length
    return best_tour, best_len

Correct up to about $n = 11$ . Past that, go make a coffee and it still won’t be done.

Exact method 2: Held-Karp dynamic programming

The insight: to extend a partial tour, you don’t need to know the order you visited the cities in — only which set you visited and where you are now.

Let $C(S, j)$ = the cheapest path that starts at city 0, visits exactly the cities in set $S$ , and ends at $j$ . Then:

$C(S, j) = \min_{i \in S,\, i \ne j} \big[ C(S \setminus \{j\},\, i) + D[i][j] \big]$

def held_karp(D):
    n = len(D)
    # C[(mask, j)] = (cost, parent) for a path 0 → ... → j covering `mask`
    C = {}
    for j in range(1, n):
        C[(1 << j, j)] = (D[0][j], 0)

    for size in range(2, n):
        for mask in range(1 << n):
            if bin(mask).count('1') != size or mask & 1:
                continue
            for j in range(1, n):
                if not mask & (1 << j):
                    continue
                prev = mask ^ (1 << j)
                best = min(
                    (C[(prev, i)][0] + D[i][j], i)
                    for i in range(1, n) if prev & (1 << i)
                )
                C[(mask, j)] = best

    full = (1 << n) - 2                              # all cities except 0
    cost, last = min((C[(full, j)][0] + D[j][0], j) for j in range(1, n))

    tour, mask = [0], full
    while last:
        tour.append(last)
        last, mask = C[(mask, last)][1], mask ^ (1 << last)
    return tour[::-1], cost

This runs in $O(n^2 2^n)$ time and $O(n 2^n)$ memory — exponential, but a much smaller exponential than $n!$ :

$n$	$(n-1)!/2$	$n^2 2^n$
15	4.4 × 10¹⁰	7.4 × 10⁶
20	6.1 × 10¹⁶	4.2 × 10⁸
25	3.1 × 10²³	2.1 × 10¹⁰

It buys you roughly 10 extra cities. Memory is what kills it — at $n = 25$ you’d need terabytes.

Held-Karp is from 1962 and is still the best known exact algorithm by worst-case complexity. Sixty years of effort has not improved the exponent.

Exact method 3: branch and bound with an MST heuristic

This is where TSP rejoins the search framework of these pages. Treat a partial tour as a state, and search — but prune any branch whose optimistic estimate already exceeds the best complete tour you’ve found.

The bound needs to be admissible — never an overestimate of the remaining cost. The classic choice is the minimum spanning tree.

Why the MST bound is admissible: whatever route completes the tour, it must connect all the remaining cities plus the endpoints. Any connected subgraph over $k$ nodes costs at least as much as the minimum spanning tree over those nodes. So MST cost can never exceed the true remaining cost — exactly the admissibility condition A* requires.

def mst_cost(D, nodes):
    """Prim's algorithm — cheapest tree connecting `nodes`."""
    if len(nodes) <= 1:
        return 0
    nodes = list(nodes)
    inside, outside = {nodes[0]}, set(nodes[1:])
    total = 0
    while outside:
        cost, best = min((D[i][j], j) for i in inside for j in outside)
        total += cost
        inside.add(best); outside.remove(best)
    return total


def branch_and_bound(D):
    n = len(D)
    best_tour, best_len = None, float('inf')

    def bound(path, cost):
        """Lower bound on any tour extending `path`."""
        remaining = set(range(n)) - set(path)
        if not remaining:
            return cost + D[path[-1]][0]
        # cheapest exit from the current city, MST over the rest,
        # cheapest return to the start
        out = min(D[path[-1]][j] for j in remaining)
        back = min(D[j][0] for j in remaining)
        return cost + out + mst_cost(D, remaining) + back

    def explore(path, cost):
        nonlocal best_tour, best_len
        if len(path) == n:
            total = cost + D[path[-1]][0]
            if total < best_len:
                best_tour, best_len = path + [0], total
            return
        if bound(path, cost) >= best_len:
            return                                  # PRUNE
        # try nearer cities first — finds a good incumbent sooner,
        # which makes the bound prune harder
        for nxt in sorted(set(range(n)) - set(path), key=lambda j: D[path[-1]][j]):
            explore(path + [nxt], cost + D[path[-1]][nxt])

    explore([0], 0)
    return best_tour, best_len

Two details do all the work:

Sorting the successors by distance. Visiting the nearest city first finds a decent tour quickly, which lowers best_len, which makes every subsequent bound check prune more aggressively. Without the sort, branch and bound is barely better than brute force.
The three-part bound — cheapest exit + MST + cheapest return. Using the MST alone is valid but weak; adding the two connecting edges tightens it considerably at almost no cost.

In practice this handles 20–40 cities. The worst case is still exponential — you just rarely hit it.

Approximation: what actually ships

For real problems (thousands of cities), you give up on optimal and take provably close enough.

Nearest neighbour — the greedy baseline

def nearest_neighbour(D, start=0):
    n = len(D)
    tour, unvisited = [start], set(range(n)) - {start}
    while unvisited:
        nxt = min(unvisited, key=lambda j: D[tour[-1]][j])
        tour.append(nxt); unvisited.remove(nxt)
    return tour, sum(D[tour[i]][tour[(i+1) % n]] for i in range(n))

$O(n^2)$ , instant, and typically 25% worse than optimal. Its failure mode is memorable: it happily visits every nearby city, then has to make one enormous jump back across the map to pick up the one it skipped.

2-opt local search — the workhorse

Take any tour. Find two edges that cross, remove them, and reconnect the other way. Repeat until nothing improves.

def two_opt(D, tour):
    n = len(tour)
    improved = True
    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                a, b = tour[i - 1], tour[i]
                c, d = tour[j], tour[(j + 1) % n]
                if D[a][b] + D[c][d] > D[a][c] + D[b][d]:
                    tour[i:j + 1] = reversed(tour[i:j + 1])
                    improved = True
    return tour

Nearest neighbour followed by 2-opt lands within about 5% of optimal, in a few lines of code. That combination is the right default for almost any practical TSP.

The guaranteed methods

Algorithm	Guarantee	Notes
Nearest neighbour	none (can be arbitrarily bad)	fast baseline
MST doubling	≤ 2 × optimal	metric TSP only
Christofides	≤ 1.5 × optimal	MST + minimum perfect matching on odd-degree nodes
2-opt / 3-opt	none, ~5% in practice	the pragmatic choice
Lin-Kernighan	none, ~2% in practice	the serious choice
Concorde (exact)	optimal	has solved 85,900 cities

Christofides (1976) held the best guarantee for 45 years — it was only beaten in 2021, and by less than a ten-thousandth of a percent. That’s how hard this problem is.

Why TSP matters

TSP is the reference NP-hard problem. If you can reduce your problem to TSP, you know not to look for an exact polynomial algorithm — go straight to heuristics.

Where it shows up, usually in disguise:

Logistics — every delivery route, every day. UPS’s ORION system is TSP with time windows and truck capacities; it reportedly saves ~100 million miles a year.
PCB drilling — the drill head visits thousands of hole positions. Tour length is machine time.
DNA sequencing — fragment assembly is a shortest-common-superstring problem, which reduces to asymmetric TSP.
Telescope scheduling — slewing between targets costs observing time.
Warehouse picking — the walking route through the aisles.
CNC and 3D printing — travel moves between cuts or extrusions.

And the strategic lesson, which is the real reason it’s on this page:

Recognising that a problem is intractable is itself a result. Once you know the space is $(n-1)!/2$ , you stop trying to search it and start asking a different question: how good a tour can I find in the time I have? Nearest neighbour plus 2-opt, in twenty lines, gets you within 5% — and 5% today beats optimal in two years.

Where to go next

Problem Solving with AI: The State-Space Framework — states, operators and search
The 8-Puzzle — heuristics on a space you can search
4-Queens and 8-Queens — the other combinatorial explosion, with a happier ending
Dijkstra’s Algorithm — shortest path, which is polynomial