Traveling Salesman Dp

Problem

Given a weighted adjacency matrix of n cities, find the minimum cost of visiting every city exactly once and returning to the starting city.

Approach

Bitmask DP (Held-Karp algorithm). State is (visited_set, current_city). Use an integer bitmask to represent the set of visited cities. dp[mask][i] = minimum cost to visit the cities in mask, ending at city i.

When to Use

Visit-all-nodes optimization — "shortest route visiting every city", delivery/pickup routing, inspection tours. Bitmask DP (Held-Karp) for exact solution when n <= 20. Aviation: multi-stop flight routing.

Complexity

Time	O(n^2 * 2^n)
Space	O(n * 2^n)

Implementation

SolutionTestsChallenge

traveling_salesman_dp

Traveling Salesman Problem — bitmask DP solution.

Problem

Given a weighted adjacency matrix of n cities, find the minimum cost of visiting every city exactly once and returning to the starting city.

Approach

Bitmask DP (Held-Karp algorithm). State is (visited_set, current_city). Use an integer bitmask to represent the set of visited cities. dp[mask][i] = minimum cost to visit the cities in mask, ending at city i.

When to use

Visit-all-nodes optimization — "shortest route visiting every city", delivery/pickup routing, inspection tours. Bitmask DP (Held-Karp) for exact solution when n <= 20. Aviation: multi-stop flight routing.

Complexity

Time: O(n^2 * 2^n) Space: O(n * 2^n)

Note

Only practical for small n (typically n <= 20).

tsp

tsp(dist: Sequence[Sequence[int | float]]) -> int | float

Return the minimum cost tour visiting all cities and returning to start.

dist is an n x n adjacency matrix where dist[i][j] is the cost from city i to city j.

tsp([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]) 80

Source code in src/algo/dp/traveling_salesman_dp.py

def tsp(dist: Sequence[Sequence[int | float]]) -> int | float:
    """Return the minimum cost tour visiting all cities and returning to start.

    *dist* is an n x n adjacency matrix where dist[i][j] is the cost
    from city i to city j.

    >>> tsp([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
    80
    """
    n = len(dist)
    if n <= 1:
        return 0

    full_mask = (1 << n) - 1

    # dp[mask][i] = min cost to reach city i having visited cities in mask
    dp: list[list[int | float]] = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                cost = dp[mask][u] + dist[u][v]
                if cost < dp[new_mask][v]:
                    dp[new_mask][v] = cost

    # Close the tour: return to city 0
    result: int | float = INF
    for u in range(1, n):
        cost = dp[full_mask][u] + dist[u][0]
        if cost < result:
            result = cost

    return result

tests/dp/test_traveling_salesman_dp.py

"""Tests for traveling salesman DP."""

import pytest

from algo.dp.traveling_salesman_dp import tsp


class TestTSP:
    def test_four_cities(self) -> None:
        dist = [
            [0, 10, 15, 20],
            [10, 0, 35, 25],
            [15, 35, 0, 30],
            [20, 25, 30, 0],
        ]
        assert tsp(dist) == 80

    def test_two_cities(self) -> None:
        dist = [[0, 5], [5, 0]]
        assert tsp(dist) == 10

    def test_single_city(self) -> None:
        assert tsp([[0]]) == 0

    def test_three_cities_symmetric(self) -> None:
        dist = [
            [0, 1, 2],
            [1, 0, 3],
            [2, 3, 0],
        ]
        # Optimal: 0->1->2->0 = 1+3+2 = 6 or 0->2->1->0 = 2+3+1 = 6
        assert tsp(dist) == 6

    @pytest.mark.slow
    def test_five_cities(self) -> None:
        dist = [
            [0, 3, 4, 2, 7],
            [3, 0, 4, 6, 3],
            [4, 4, 0, 5, 8],
            [2, 6, 5, 0, 6],
            [7, 3, 8, 6, 0],
        ]
        result = tsp(dist)
        assert isinstance(result, int)
        assert result > 0

Implement it yourself

Run: just challenge dp traveling_salesman_dp

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

traveling_salesman_dp

Traveling Salesman Problem — bitmask DP solution.

Problem

Given a weighted adjacency matrix of n cities, find the minimum cost of visiting every city exactly once and returning to the starting city.

Approach

Bitmask DP (Held-Karp algorithm). State is (visited_set, current_city). Use an integer bitmask to represent the set of visited cities. dp[mask][i] = minimum cost to visit the cities in mask, ending at city i.

When to use

Visit-all-nodes optimization — "shortest route visiting every city", delivery/pickup routing, inspection tours. Bitmask DP (Held-Karp) for exact solution when n <= 20. Aviation: multi-stop flight routing.

Complexity

Time: O(n^2 * 2^n) Space: O(n * 2^n)

Note

Only practical for small n (typically n <= 20).

tsp

tsp(dist: Sequence[Sequence[int | float]]) -> int | float

Return the minimum cost tour visiting all cities and returning to start.

dist is an n x n adjacency matrix where dist[i][j] is the cost from city i to city j.

tsp([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]) 80

Source code in src/algo/dp/traveling_salesman_dp.py

def tsp(dist: Sequence[Sequence[int | float]]) -> int | float:
    """Return the minimum cost tour visiting all cities and returning to start.

    *dist* is an n x n adjacency matrix where dist[i][j] is the cost
    from city i to city j.

    >>> tsp([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
    80
    """
    n = len(dist)
    if n <= 1:
        return 0

    full_mask = (1 << n) - 1

    # dp[mask][i] = min cost to reach city i having visited cities in mask
    dp: list[list[int | float]] = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                cost = dp[mask][u] + dist[u][v]
                if cost < dp[new_mask][v]:
                    dp[new_mask][v] = cost

    # Close the tour: return to city 0
    result: int | float = INF
    for u in range(1, n):
        cost = dp[full_mask][u] + dist[u][0]
        if cost < result:
            result = cost

    return result