Exact

Bellman–Held–Karp
Aliasbhk, bellman_karp
TypeExact
ComplexityO(2ⁿ · n²) time, O(2ⁿ · n) space

Description

Dynamic programming algorithm that solves TSP exactly. It builds up solutions for subsets of cities, combining the optimal sub-tour results to find the globally optimal tour. Returns the provably shortest Hamiltonian circuit.

Do not use on more than ~20 cities — memory and runtime grow exponentially with city count.

procedure BellmanHeldKarp(cities):
    n ← |cities|
    dp[S][i] ← min cost to visit exactly the cities in S, ending at i
    dp[{0}][0] ← 0;  all other dp entries ← ∞
    for each subset S of size 2..n (in increasing order):
        for each i in S, i ≠ 0:
            for each j in S \ {i}:
                dp[S][i] ← min(dp[S][i], dp[S\{i}][j] + dist(j, i))
    return min over i≠0 of dp[{0..n-1}][i] + dist(i, 0)

Usage

teeline solve bhk -i ./data/discopt/tsp_5_1.tsp
teeline solve bellman_karp -i ./data/discopt/tsp_5_1.tsp --verbose

References