Bitmask Dynamic Programming
A bitmask can encode a selected subset when n is small. Held–Karp DP solves a traveling-salesperson tour by remembering visited vertices and the current endpoint, instead of enumerating every permutation. The input is a directed cost matrix with optional missing edges. We start and end at vertex 1, visit every other vertex once, and reconstruct one minimum-cost tour.
Prerequisites: Bitwise Operations and Bitmasks; reconstruction. Related existing lessons: Bitwise Operations and Bitmasks.
Build the idea
Recognize the repeated subproblems
A permutation search tries roughly (n−1)! tours. Different visit orders can reach the same visited set and endpoint; their future unvisited choices are identical, so only the cheapest history matters. The O(n2^n) state space is useful for n≤18, but not for hundreds of vertices. The exponential dimension remains real even after eliminating factorial repetition.
Define the state
dp[mask][last] is minimum cost from start vertex 1 to last, visiting exactly the mask’s vertices once. Bit 0 is the start; internally vertices are 0-based for masks, while output names are 1-based. The endpoint is necessary because the next edge cost depends on it. A subset-only dp[mask] would lose that information.
Derive the transition
For every finite state, try an unvisited next vertex other than the start. If the directed edge exists, relax mask|(1<<next), next by adding its cost. Once all bits are set, add an existing return edge last→start and take the minimum. The return is separate so the start is not revisited early. A bit test must precede a transition to prevent duplicate visits.
Base cases and computation order
Only dp[1][0]=0 is initially reachable; all other entries are INF. Increasing masks works because adding an unset bit strictly increases the numeric mask. Parent stores the previous endpoint; the previous mask is obtained by clearing last’s bit during backtracking. A singleton has the conventional zero-cost tour 1 1. Missing full tours print IMPOSSIBLE.
Correctness and invariant
Induct on the number of selected bits. Removing the last visited nonstart vertex from a partial tour exposes exactly a predecessor state; appending a legal unvisited vertex constructs a valid candidate. All full tours appear in this process, and minimizing their final return costs gives the optimum. Finite-state guards prevent sentinel arithmetic from creating false tours.
Work the example
For matrix [[0,2,9],[6,0,3],[4,7,0]], tour 1→2→3→1 costs 2+3+4=9. The other order costs 9+7+6=22. States {1,2}, last=2 and {1,3}, last=3 retain the two initial alternatives until their different completions can be compared.
visited / last cost {1} / 1 0 {1,2} / 2 2 {1,3} / 3 9 {1,2,3} / 3 5 best closed tour 9
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
#include<algorithm>
int main(){
int n;
std::cin>>n;
std::vector<std::vector<long long>>cost(n,std::vector<long long>(n));
for(auto&row:cost){
for(auto&x:row){
std::cin>>x;
}
}
if(n==1){
std::cout<<"0\n1 1\n";
return 0;
}
int masks=1<<n;
const long long INF=4000000000000000000LL;
std::vector<long long>dp((size_t)masks*n,INF);
std::vector<int>parent((size_t)masks*n,-1);
dp[n]=0; // mask=1, last=0: start at vertex 1.
for(int mask=1;mask<masks;mask+=2){
for(int last=0;last<n;++last){
if((mask>>last&1)&&dp[(size_t)mask*n+last]!=INF){
for(int next=1;next<n;++next){
if(!(mask>>next&1)&&cost[last][next]>=0){
int m=mask|(1<<next);
long long candidate=dp[(size_t)mask*n+last]+cost[last][next];
if(candidate<dp[(size_t)m*n+next]){
dp[(size_t)m*n+next]=candidate;
parent[(size_t)m*n+next]=last;
}
}
}
}
}
}
int all=masks-1,last=-1;
long long best=INF;
for(int v=1;v<n;++v){
if(cost[v][0]>=0&&dp[(size_t)all*n+v]!=INF&&dp[(size_t)all*n+v]+cost[v][0]<best){
best=dp[(size_t)all*n+v]+cost[v][0];
last=v;
}
}
if(last==-1){
std::cout<<"IMPOSSIBLE\n";
return 0;
}
std::vector<int>route;
int mask=all;
while(last!=-1){
route.push_back(last+1);
int p=parent[(size_t)mask*n+last];
mask^=1<<last;
last=p;
}
std::reverse(route.begin(),route.end());
route.push_back(1);
std::cout<<best<<'\n';
for(int i=0;i<(int)route.size();++i){
std::cout<<route[i]<<(i+1==(int)route.size()?'\n':' ');
}
}
Complexity analysis
O(n2^n) states and O(n) next vertices each give O(n²2^n) time. Values and parents use O(n2^n) space; the n=18 bound keeps this near tens of megabytes. Backtracking is O(n). Tour cost≤n·10^6 fits long long.
Example input and output
Read n (1..18), then an n×n directed matrix:diagonal 0, other entries −1 for missing or costs in 0..10^6. Print minimum Hamiltonian-tour cost and vertices starting/ending at 1, or IMPOSSIBLE. Singleton convention is 0 and route 1 1.
Input
3 0 2 9 6 0 3 4 7 0
Output
9 1 2 3 1
For matrix [[0,2,9],[6,0,3],[4,7,0]], tour 1→2→3→1 costs 2+3+4=9. The other order costs 9+7+6=22. States {1,2}, last=2 and {1,3}, last=3 retain the two initial alternatives until their different completions can be compared.
Practical applications
Use for small-subset ordering, assignment and routing with sufficient subset/endpoint states. Some problems need only dp[mask]; others need extra resources. Large TSP is not made polynomial by this method, and approximation is a different guarantee.
Check your understanding
Why is last needed in addition to mask?
Put it into practice
Enumerate all tours for n≤7 and verify the reconstructed cost.
Show a hint
Include missing return edges,zero-cost edges and a singleton.