AlgoScope

Bitmask DP

algorithmadvancedTime O(2^n x n^2)Space O(2^n x n)

Some problems have a state that is a subset of a small set: which cities have been visited, which tasks are done, which people are seated. A subset of n things is an n-bit integer, one bit per thing, and that turns a set into an array index. The travelling salesman is the classic case: dp[mask][last] is the cheapest path from the start through exactly the cities in mask, ending at last. Filling the masks in increasing numeric order works because removing a bit always makes a smaller number, so every subset is finished before any set that contains it. The table has 2^n rows, which is why the technique lives and dies by n being small, around twenty at most.

ABCD000100110101011110011011110111110✓

Visit all 4 cities once, starting and ending at A, as cheaply as possible. The state is the set of cities visited so far, and a set of 4 cities is an 4-bit number: bit 0 is A, bit 1 is B, and so on, written here with A on the right. Each row is one set, each column the city the path ends at, and the cell is the cheapest path from A through exactly that set ending there. Only sets containing A matter, so 8 rows instead of 16.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.

  1. Cheapest path over {A, B, C, D} ending at B: which previous end wins?

    • via C: 50 + 35 = 85
    • via D: 45 + 25 = 70

    Answer: via D: 45 + 25 = 70. Take the row for the set without B, add the last hop from each of its ends, and keep the minimum.

  2. Cheapest path over {A, B, C, D} ending at C: which previous end wins?

    • via B: 45 + 35 = 80
    • via D: 35 + 30 = 65

    Answer: via D: 35 + 30 = 65. Take the row for the set without C, add the last hop from each of its ends, and keep the minimum.

  3. Cheapest path over {A, B, C, D} ending at D: which previous end wins?

    • via B: 50 + 25 = 75
    • via C: 45 + 30 = 75

    Answer: via B: 50 + 25 = 75. Take the row for the set without D, add the last hop from each of its ends, and keep the minimum.

  4. Which end of the full row gives the cheapest tour once the trip home is added?

    • B: 70 + 10 = 80
    • C: 65 + 15 = 80
    • D: 75 + 20 = 95

    Answer: B: 70 + 10 = 80. Add the distance back to A to each entry of the full row and take the minimum.

How it runs, step by step

  1. Visit all 4 cities once, starting and ending at A, as cheaply as possible. The state is the set of cities visited so far, and a set of 4 cities is an 4-bit number: bit 0 is A, bit 1 is B, and so on, written here with A on the right. Each row is one set, each column the city the path ends at, and the cell is the cheapest path from A through exactly that set ending there. Only sets containing A matter, so 8 rows instead of 16.

    Bitmask dynamic programming for the travelling salesman over 4 cities.

  2. Set 0011 = {A, B}, ending at B. The path arrived from the set without B, 0001 = {A}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is A: 0 + 10 = 10.

    dp of 0011 ending at B is 10.

  3. Set 0101 = {A, C}, ending at C. The path arrived from the set without C, 0001 = {A}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is A: 0 + 15 = 15.

    dp of 0101 ending at C is 15.

  4. Set 0111 = {A, B, C}, ending at B. The path arrived from the set without B, 0101 = {A, C}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is C: 15 + 35 = 50.

    dp of 0111 ending at B is 50.

  5. Set 0111 = {A, B, C}, ending at C. The path arrived from the set without C, 0011 = {A, B}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is B: 10 + 35 = 45.

    dp of 0111 ending at C is 45.

  6. Set 1001 = {A, D}, ending at D. The path arrived from the set without D, 0001 = {A}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is A: 0 + 20 = 20.

    dp of 1001 ending at D is 20.

  7. Set 1011 = {A, B, D}, ending at B. The path arrived from the set without B, 1001 = {A, D}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is D: 20 + 25 = 45.

    dp of 1011 ending at B is 45.

  8. Set 1011 = {A, B, D}, ending at D. The path arrived from the set without D, 0011 = {A, B}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is B: 10 + 25 = 35.

    dp of 1011 ending at D is 35.

  9. Set 1101 = {A, C, D}, ending at C. The path arrived from the set without C, 1001 = {A, D}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is D: 20 + 30 = 50.

    dp of 1101 ending at C is 50.

  10. Set 1101 = {A, C, D}, ending at D. The path arrived from the set without D, 0101 = {A, C}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is C: 15 + 30 = 45.

    dp of 1101 ending at D is 45.

  11. Set 1111 = {A, B, C, D}, ending at B. The path arrived from the set without B, 1101 = {A, C, D}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via C: 50 + 35 = 85; via D: 45 + 25 = 70. The cheapest is via D, 70.

    dp of 1111 ending at B is 70.

  12. Set 1111 = {A, B, C, D}, ending at C. The path arrived from the set without C, 1011 = {A, B, D}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via B: 45 + 35 = 80; via D: 35 + 30 = 65. The cheapest is via D, 65.

    dp of 1111 ending at C is 65.

  13. Set 1111 = {A, B, C, D}, ending at D. The path arrived from the set without D, 0111 = {A, B, C}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via B: 50 + 25 = 75; via C: 45 + 30 = 75. The cheapest is via B, 75.

    dp of 1111 ending at D is 75.

  14. The last row, 1111, holds every city. Each entry still has to return to A: end at B: 70 + 10 = 80; end at C: 65 + 15 = 80; end at D: 75 + 20 = 95. The cheapest tour costs 80.

    The cheapest tour costs 80.

  15. Cheapest tour: 80. The table has 8 x 4 cells, 13 of them reachable, filled with 15 additions in total, against 6 orderings by brute force. That gap is small for 4 cities and enormous for 20, where 2^20 x 20 states is about twenty million and 19! is beyond counting. Bitmask DP is the answer whenever the state is a subset of a small set: the subset becomes an integer, one bit per element, and increasing numeric order is a valid order of computation because a subset is always a smaller number than a set containing it.

    Cheapest tour 80 with 13 states filled.

Remember

  • A subset of n things is an n-bit integer; one bit per element turns a set into an array index.
  • Fill masks in increasing order: a subset is always a smaller number than any set containing it.
  • dp[mask][last] for TSP: min over the previous end of dp[mask without last][prev] + distance.

Topics covered

Related

Where this is used

DatabasesJoin order in a query planner

A planner must decide what order to join relations in, and the cheapest plan for a set of tables is assembled from the cheapest plans for its subsets, which is exactly a DP over subsets of the FROM list. PostgreSQL runs this exhaustive search until a query touches geqo_threshold relations, 12 by default, and then hands the query to a genetic search instead, because 2^n plans stop being affordable right about there. DuckDB uses the same subset DP with a smarter enumeration that only visits connected subsets.

LogisticsExact routing for a driver's stop list

Held and Karp published this dp[mask][last] table in 1962, independently of Bellman, and its O(2^n x n^2) is still the best worst-case bound known for solving the travelling salesman problem exactly. Solvers that reach thousands of cities, such as Concorde, get there with branch and cut rather than a faster table. Where the table does fit is the cluster-first, route-second split used in delivery planning: a fleet has thousands of stops, but one driver's day is a dozen or two, and a group that size can be routed exactly instead of approximately.

HardwareSteiner trees in chip and multicast routing

Connecting a handful of chosen terminals in a large graph as cheaply as possible is the Steiner tree problem, and the Dreyfus-Wagner algorithm solves it with a table indexed by a subset of the terminals and a vertex. What matters is that the number of terminals goes in the exponent and the size of the graph does not, which is the right trade for VLSI routing: a net on a chip has an enormous grid to route through but only a few pins to reach. Multicast routing has the same shape, with the receivers as terminals.

CombinatoricsCounting tilings column by column

To count the domino tilings of an m by n board you sweep one column at a time and let the state be a bitmask of which cells in the boundary already stick out into the next column. The table is 2^m by n, so a board that is narrow and long stays cheap even when the count itself has hundreds of digits. This is the same broken profile idea behind the transfer matrix method in statistical physics, where the bitmask is one row of the lattice rather than a set of items used.

Why it works this way

Why the table needs last as well as the mask

The cost of the next step depends on which city you are standing in, not only on which cities are already done. Two paths covering the same set can end in different places and cost different amounts to extend, so collapsing them into a single dp[mask] would throw away the one fact the transition needs. Carrying last multiplies the table by n and the work by another n, and that is where the n^2 in O(2^n x n^2) comes from.

Why city 0 is pinned as the start

A tour is a cycle, so the same tour can be written n different ways depending on where you start reading it. Setting dp[1][0] = 0 and skipping every mask without bit 0 picks one representative and saves a factor of n for free; the alternative is a third index for the start city. It is also why the answer adds d[last][0] at the end: the path has to be closed back to the city it was forced to begin at.

The bit test that does not mean what it reads like

In C, C++ and Java, << binds tighter than ==, and == binds tighter than &. So if (mask & 1 << i == 0) is parsed as mask & ((1 << i) == 0), which tests something else entirely and compiles without complaint. Write ((mask & (1 << i)) == 0). Kotlin sidesteps it twice over: infix functions bind tighter than equality, so the == 0 sees the whole expression, and and and shr are infix functions of equal precedence evaluated left to right, so mask shr last and 1 above groups the way it reads.

The unreachable sentinel is what overflows

Every cell starts at INF and the transition reads dp[prev][p] + d[p][last]. If INF is Int.MAX_VALUE that addition wraps to a large negative number, min takes it, and a state nothing can reach becomes the cheapest way into the mask. The guard dp[prev][p] != INF in the loop above is there for exactly that reason; the other fix is a sentinel with headroom, something like 1 shl 30, which is still positive after one edge weight is added.

Read more

Next up