Bitmask DP — TSP intro: Question bank — Coding deep dive

Worked example Two ways to iterate the

same DP The recurrence pulls predecessors; the code below pushes successors. Both are correct because masks only ever grow, so a smaller mask is always finished before a larger one uses it.

INF = float('inf')          # INF is the code name for the symbol ∞
 
# --- PULL (backward): fill dp[mask][i] from smaller prev ---
def tsp_pull(dist):
    n = len(dist)
    full = (1 << n) - 1
    dp = [[INF]*n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):     # i must be visited to end at i
                continue
            prev = mask & ~(1 << i)       # set before arriving at i
            for j in range(n):
                if prev & (1 << j):       # only real predecessors
                    cand = dp[prev][j] + dist[j][i]
                    if cand < dp[mask][i]:
                        dp[mask][i] = cand
    return min(dp[full][i] + dist[i][0] for i in range(1, n))
 
# --- PUSH (forward): spread dp[mask][i] into bigger masks ---
def tsp_push(dist):
    n = len(dist)
    full = (1 << n) - 1
    dp = [[INF]*n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == INF:        # unreached, nothing to push
                continue
            for k in range(n):
                if mask & (1 << k):       # k already visited -> skip
                    continue
                nm = mask | (1 << k)
                cand = dp[mask][i] + dist[i][k]
                if cand < dp[nm][k]:
                    dp[nm][k] = cand
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

True or false — justify

Two orderings that visit the same set and end at the same city are interchangeable for the future.

True. The remaining cost depends only on the visited set and the current spot (SET + SPOT); the internal order of the already-visited prefix has no effect on any future edge, so we keep only the cheaper prefix.

dp[mask][i] stores the cheapest tour.

False. It stores the cheapest path from city 0 to city

i

visiting exactly mask — no return edge yet. The tour cost only appears when you add dist[i][0] over the full mask.

You may start the tour at any city, so the base case needs a loop over all starting cities.

False. A cycle has no distinguished start; fixing the start at city 0 loses no tours (every cycle passes through 0). One base case dp[1][0]=0 suffices, saving a factor of

n

Bitmask DP works only when the distance matrix is symmetric.

False. The recurrence uses dist[j][i] in a specific direction, so it handles asymmetric costs (dist[i][j] != dist[j][i]) correctly. Symmetry was only a convenience in the worked example.

For a fixed mask, every entry dp[mask][i] with

0 \leq i < n

is a meaningful value.

False. Only entries where bit

i

is set in mask are meaningful; "ending at an unvisited city" is impossible, so those stay

\infty

The number of DP states is

2^{n}

False. It is

n \cdot 2^{n}

— one axis for the

2^{n}

subsets (SET) and one axis for the

n

possible current cities (SPOT).

Bitmask DP finds a Hamiltonian cycle even when the graph is missing some edges.

True, if you model missing edges as

\infty

. Any transition using a missing edge adds

\infty

and can never win the min, so infeasible tours are automatically discarded; if all candidates are

\infty

, no cycle exists.

Pushing forward (mask → mask|(1<<k)) and pulling backward (prev → mask) give different answers.

False. They are the two variants shown above — the same DP traversed in opposite directions. Because masks only ever gain bits, every predecessor prev is a strictly smaller integer than mask, so iterating masks in increasing order is safe either way.

n = 0

n = 1

, the closed-tour formula min over i!=0 is fine.

False. With

n = 1

there is no

i \neq = 0

and with

n = 0

there is no city 0 at all, so the min runs over an empty set (error /

\infty

). Both degenerate sizes must be special-cased.

Spot the error

if mask & 1<<i == 0: correctly tests whether city

i

is absent.

Actually it is correct here — in Python & binds tighter than ==, so this parses as (mask & (1<<i)) == 0, which is the right test. But it is fragile and hard to read; the trap is that swapping in an operator like + would break precedence, so seasoned coders still write (mask & (1<<i)) == 0 explicitly.

Someone loops for i in range(n): dp[mask][i] = ... without checking bit

i

Error. They compute values for endpoints that were never visited, polluting the table. Guard with if mask & (1<<i) (skip) — an unvisited endpoint must remain

\infty

The answer is returned as min(dp[full][i] for i in range(n)) where full = (1<<n)-1.

Error (two bugs). It includes

i = 0

(a "tour" that ends where it started with no travel) and it forgets the return edge. Correct closed-tour answer: min(dp[full][i] + dist[i][0] for i in range(1,n)).

To remove city

i

, code writes mask & (1<<i).

Error. That isolates bit

i

, it doesn't remove it. Removal is mask & ~(1<<i); the ~ (NOT) flips the mask so bit

i

becomes 0 and all others stay.

prev = mask & ~(1<<i) is computed, then the code loops for j in range(n) over all

j

Error. You must only take

j

that are actually in prev (i.e. prev & (1<<j)); otherwise you read

\infty

entries or, worse, an invalid predecessor path. Guard the inner loop.

To detect an unreachable state and skip work, the code checks if dp[mask][i] > 0: continue.

Error. A reachable state can legitimately have positive cost. The correct skip test is if dp[mask][i] == INF: continue (recall INF is

\infty

) — only truly unreachable states carry it.

Initialising dp = [[0]*n for _ in range(1<<n)].

Error. All states start reachable at cost 0, so the min never rules anything out — every garbage transition looks free. Must initialise to INF (

= \infty

) and set only dp[1][0] = 0.

Why questions

Why do we index the table by an integer mask rather than by a Python set?

A DP table needs a cheap, fixed-range index, and an integer is the smallest possible one; the

2^{n}

subsets map exactly onto integers

0 \dots 2^{n} - 1

, so array lookup is

O (1)

Why is peeling off the last edge (not the first) the right way to write the recurrence?

The state fixes where you currently are (city

i

), so the natural unknown is "how did I arrive here?" — the last edge

j \to i

. Peeling it exposes a strictly smaller sub-state (prev, j) we've already solved.

Why is the optimal-substructure argument necessary (not just nice)?

DP is only valid if an optimal whole is built from optimal parts. If a cheaper sub-path to (prev,j) existed, we could splice it in and beat dp[mask][i] — contradiction — which is exactly what licenses the min. See Held-Karp Algorithm for the formal statement.

Why does collapsing orderings turn

n!

into

\sim n^{2} 2^{n}

There are

n!

orderings but only

n \cdot 2^{n}

distinct (SET, SPOT) states; many orderings share a state and we keep only the best, so work scales with states, not orderings.

Why can't we just be greedy and always walk to the nearest unvisited city?

Greed is locally optimal but not globally: a cheap early edge can force expensive later ones. TSP has no greedy-safe choice, which is why we must minimise over all predecessors.

Why is

n \approx 20

the practical ceiling?

Memory is

O (n 2^{n})

and time

O (n^{2} 2^{n})

; at

n = 20

that's

\sim 4 \times 1 0^{8}

operations — feasible — but each further city roughly doubles the work, so

n = 25

is already ~

1 0^{10}

. Branch and Bound is used to push past this heuristically.

Why does modelling a missing edge as

\infty

(rather than deleting it) keep the code simple?

Every transition is a min of sums; an

\infty

summand can never be the minimum, so infeasible moves are filtered automatically without any special-case branching.

Why does fixing the start city not miss any optimal tour?

A tour is a cycle, and every cycle over all cities passes through city 0 exactly once; rotating the cycle to begin at 0 gives the same cost, so no optimum is lost.

Edge cases

What does the algorithm return for

n = 0

(empty city set)?

There is no city 0, so dp[1][0] doesn't even exist and full = 0; the whole formulation is undefined. Treat

n = 0

as a special case (cost 0, or "no tour" by convention) before entering the DP.

What does the algorithm return for

n = 1

(one city)?

A closed tour of one city has cost 0 (stay put), but the formula min over i!=0 is empty and must be special-cased; guard

n = 1

explicitly.

Two cities, only

dist [0] [1]

known and symmetric — what's the tour?

0 \to 1 \to 0

with cost

dist [0] [1] + dist [1] [0]

. The DP produces dp[full][1], then adds the return edge; nothing degenerate as long as both directions exist.

The graph is disconnected (no Hamiltonian cycle exists). What happens?

Every full-mask endpoint or the return edge involves an

\infty

, so the final min is

\infty

— the algorithm correctly reports "no tour" rather than crashing.

There is a self-loop dist[i][i] > 0. Does it ever get used?

No. A transition to city

k

is only taken when

k

is not yet in the mask, so you never travel from

i

i

; self-loop costs are irrelevant to the DP.

You want a Hamiltonian path (visit all, no return). What single change is needed?

Drop the + dist[i][0] return term; the answer becomes min over all i of dp[full][i], and now the start need not equal the end.

Distances can be negative (e.g. rewards). Does the DP still work?

The min recurrence still finds the cheapest visit-all path correctly, since it never assumes non-negativity (unlike Dijkstra). But "cheapest" may now be unbounded only if negatives formed a repeatable loop — impossible here because each city is visited once.

All distances are equal to a constant

c

. What is every tour's cost?

Exactly

n \cdot c

(

n

edges in a cycle over

n

cities), so every ordering ties and the DP returns

n c

— a good sanity check that no edge is double-counted or dropped.

Recall One-line self-test

If you can answer these three without notes you own the trap-space: What are the two indices of the state, and why exactly two? ::: SET (visited mask) and SPOT (current city); those are the only facts that affect remaining cost. Name the single guard that keeps impossible endpoints out. ::: if mask & (1<<i) — city $i$ must be in the mask to end there. Name the single term people forget for a closed tour. ::: The return edge + dist[i][0].

Connections

Travelling Salesman Problem — the problem these traps live inside.
Held-Karp Algorithm — the formal name for this exact DP.
Dynamic Programming — optimal substructure justifies the min.
Bit Manipulation · Subset Enumeration — the mask machinery.
Hamiltonian Path and Cycle — path-vs-cycle edge cases.
Branch and Bound — what to reach for past $n \approx 20$ .