DP for the Travelling Salesman

1Shortest tour, not tour at most K

TSP-decision asks: is there a tour of cost at most K? That yes/no language is NP-complete; its certificate is a cyclic order. Optimisation TSP asks: what is the shortest tour? That question is NP-hard and is not a member of NP, because NP is a class of languages.

Held–Karp answers the optimisation question exactly, in exponential time. It does not decide a supplied K, and it is not a polynomial algorithm. The four-city instance whose decision answers are 'no' at K=17 and 'yes' at K=18 has optimisation answer 18.

Same 1-2-4-3-1 tour of cost 18. This concept only names the optimisation question whose answer is that 18.

Name the question

1. DecisionTour \le K? Certificate = the order. NPC. Already taught.
2. OptimisationShortest tour? NP-hard. This topic.
3. Held–KarpExact DP for the second. Exponential, not a P-claim.

2State: the set visited and the city you end on

A permutation of n cities is too large to index a table. Held–Karp keeps only the set of cities already visited and the city the path currently ends at. Formally, g(S, j) is the cheapest path that starts at city 1, visits exactly the cities in S, and ends at j \in S. City 1 itself is left out of S.

Two paths that visited the same set and ended at the same j are interchangeable for every future completion. That is the optimal-substructure claim: you may forget the order inside the visited set except for the endpoint.

Figure. g(S, j) stores one number: cheapest path that started at 1, visited exactly the cities in S, and ended at j. City 1 stays outside S. The order inside S is forgotten.

Read one state

1. SThe set of cities already visited, not including the start city 1.
2. jWhere that path ended. j must sit in S.
3. ValueA number — the cheapest such path — not a list of orders.

3Min over the city you arrived from

The cheapest path that visited S and ended at j arrived along one last edge i \to j with i \in S, i \neq j. The prefix that visited the smaller set and ended at the previous city must itself be cheapest, so g(S, j) = \min_{i \in S \setminus \{j\}} \bigl( g(S\setminus\{j\}, i) + d(i,j) \bigr).

The base is a single other city: g(\{j\}, j) = d(1, j). After every g(\{2,\ldots,n\}, j) is known, close the tour with the edge back to 1 and take the min.

Figure. g(S, j) is the min over previous endpoints i of g(S minus j, i) plus d(i, j). At |S|=2 there is one i: g({2,3},3) = g({2},2) + d(2,3) = 2+6=8. Larger S is the same min over more i.

One state from smaller sets

1. Baseg(\{j\},j)=d(1,j).
2. Grow SFor each j \in S, min over previous endpoints i.
3. CloseOPT = \min_j g(\{2,\ldots,n\},j) + d(j,1).

Held–Karp (bitmask)

def held_karp(d):
    n = len(d)
    N = 1 << (n - 1)
    g = [[float('inf')] * n for _ in range(N)]
    for j in range(1, n):
        g[1 << (j - 1)][j] = d[0][j]
    for S in range(N):
        for j in range(1, n):
            if not (S & (1 << (j - 1))):
                continue
            prev = S ^ (1 << (j - 1))
            if prev == 0:
                continue
            g[S][j] = min(
                g[prev][i] + d[i][j]
                for i in range(1, n)
                if prev & (1 << (i - 1))
            )
    full = N - 1
    return min(g[full][j] + d[j][0] for j in range(1, n))

4Twelve states on the four-city instance close at 18

Distances: 1{-}2=2, 1{-}3=9, 1{-}4=10, 2{-}3=6, 2{-}4=4, 3{-}4=3. Base: g(\{2\},2)=2, g(\{3\},3)=9, g(\{4\},4)=10.

Size 3: g(\{2,3,4\},2)=16, g(\{2,3,4\},3)=9, g(\{2,3,4\},4)=11. Closing: 16+d(2,1)=18, 9+d(3,1)=18, 11+d(4,1)=21. Optimum 18.

Figure. Tour 1-2-4-3-1, edges 2+4+3+9=18. This is g({2,3,4},3)+d(3,1). The sibling 1-3-4-2-1 also costs 18.

Size-3 cells from size-2

1. End at 2\min(g(\{3,4\},3)+6,\, g(\{3,4\},4)+4) = \min(13+6,\,12+4)=16.
2. End at 3\min(g(\{2,4\},2)+6,\, g(\{2,4\},4)+3) = \min(14+6,\,6+3)=9.
3. End at 4\min(g(\{2,3\},2)+4,\, g(\{2,3\},3)+3) = \min(15+4,\,8+3)=11.

Coding lab. Held-Karp on four cities runs in the app, with checks on your output.

5O(n² 2ⁿ) is smaller than n! and still exponential

There are O(n 2^{n}) states and each takes a min over O(n) predecessors, so the fill is O(n^2 2^n). Enumerating tours from a fixed start is (n-1)!. For n \ge 8 the factorial has already pulled away; for n=20 Held–Karp is in the hundreds of millions of states and 19! is not enumerable.

That is still exponential. NP-completeness of the decision problem is not contradicted. Branch and bound on the same instance may expand fewer nodes if the bound is strong; Held–Karp always fills the table. Use Held–Karp when you want a simple exact n \le 15 solver; use B&B when a bound can kill most of the tree.

No bar chart of 19! — that value cannot be drawn on a linear axis next to 2^20. The three-row table is the comparison.