Bitmask DP
A bitmask encodes which elements are used. Classic for TSP on small n.
Bitmask DP: Four cities, eight subsets that contain the start
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)