Bitmask DP

## The problem shape A courier starts at a depot, must visit each of n client sites exactly once, and returns to the depot. Travel times between every pair of locations are known and may be asymmetric (one-way streets, traffic direction). You want the cheapest closed route. Brute force enumerates n! orderings — at n = 18 that is about 6.4 × 10^15, hopeless. Subset DP replaces "which ordering" with "which set, and where am I now", and that collapse is the whole trick. ## What a bitmask is doing here A *bitmask* is an integer used as a set: bit i is 1 when site i has been visited. With n sites there are exactly 2^n such sets, and each is a single integer you can index a table with. That is the only reason subsets are usable as a DP dimension at all — the set is a number, so the table is a plain lookup rather than a map of sets. ## Why the set alone is not a state The defining property of a DP state is that it must **screen off the past**: everything the remaining decisions cost has to be computable from the state, never from how you got there. Suppose the mask says sites {A, B, C} are done. One partial route ended at A, another ended at C. Those two histories have different futures — the very next leg is priced from a different starting point, and so is every leg after it. Storing one number per mask would force you to compare, and discard, routes that are not comparable: the cheaper prefix may end somewhere expensive to leave. Keeping only the cheaper one silently throws away the optimum, and the DP returns a wrong (too small or unachievable) answer rather than a slow one. Adding the endpoint restores the property. Once you know the visited set *and* the current site, the rest of the trip depends on nothing else — the identity of the remaining sites is `complement(mask)`, and the first leg out is priced from `last`. That is optimal substructure recovered. ## The recurrence Fix the depot as the start so it never occupies a bit (fixing the start also removes the n-fold rotational symmetry of a closed tour for free). - Base: `dp[bit(i)][i] = travel[depot][i]` for every site i. - Transition: for each mask, each `i` set in mask with a finite `dp[mask][i]`, and each `j` not in mask: `dp[mask | bit(j)][j] = min(dp[mask | bit(j)][j], dp[mask][i] + travel[i][j])`. - Answer: `min over i of dp[full][i] + travel[i][depot]`, where `full` is the all-ones mask. Evaluation order is free: iterating masks in increasing numeric order works, because `mask` is numerically smaller than `mask | bit(j)` whenever bit j was clear. Every value is therefore final before it is read. ## What it costs | quantity | formula | n = 18 | |---|---|---| | states | 2^n · n | ≈ 4.7 million | | transitions | 2^n · n^2 | ≈ 85 million | | memory (4-byte entries) | 4 · 2^n · n | ≈ 19 MB | The extra dimension multiplies memory by n — real, but a *factor*, not another exponential. People sometimes fear it turns 2^n into something worse; it does not. ## Recovering the route The table holds costs, not orderings. Either store a parent index alongside each entry, or walk backwards at the end: from `(full, last)`, find the predecessor `i` in `mask` with `dp[mask without last][i] + travel[i][last] == dp[mask][last]`, then repeat. Reconstruction is O(n^2) at worst and costs nothing asymptotically. ## When the endpoint dimension is *not* needed The endpoint matters here only because the cost of a step depends on the previous choice. In problems where each step's cost depends only on *which* element is added and *how many* have been added — assigning workers to shifts, for instance — the extra dimension is redundant and should be dropped. Recognising which of the two shapes you are in is the actual skill; adding `last` reflexively wastes an n-fold factor, and omitting it when steps are coupled produces a confidently wrong answer. ## Common traps Forgetting the closing leg back to the depot; initialising unreached states to something other than infinity so garbage propagates; letting the mask include the depot and then wondering why the count is 2^(n+1); and assuming symmetry — with asymmetric travel times you cannot reverse a partial route and reuse its cost.