AlgoScope

Bitmask DP

A bitmask encodes which elements are used. Classic for TSP on small n.

Dynamic programming, technique, advanced
dp of 1111 ending at B is 70.ABCD00010011010101111001101111011111010155045204535504570
dp of 1111 ending at B is 70.ABCD00010011010101111001101111011111010155045204535504570

Bitmask DP: Four cities, eight subsets that contain the start

Decision, step 11 of 15

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.

Cost

Best
O(2^n * n)
Average
O(2^n * n)
Worst
O(2^n * n)
Space
O(2^n)