# Dynamic Programming Algorithm

Notice that if we consider the path (in order):

(1,2,3,4,6,0,5,7)

and the path

(1,2,3,5,0,6,7,4)

The cost of going from vertex `1`

to vertex `2`

to vertex `3`

remains the same, so why must it be recalculated? This result can be saved for later use.

Let `dp[bitmask][vertex]`

represent the minimum cost of travelling through all the vertices whose corresponding bit in `bitmask`

is set to `1`

ending at `vertex`

. For example:

dp[12][2] 12 = 1 1 0 0 ^ ^ vertices: 3 2 1 0

Since `12`

represents `1100`

in binary, `dp[12][2]`

represents going through vertices `2`

and `3`

in the graph with the path ending at vertex 2.

Thus we can have the following algorithm (C++ implementation):

int cost[N][N]; //Adjust the value of N if needed int memo[1 << N][N]; //Set everything here to -1 int TSP(int bitmask, int pos){ int cost = INF; if (bitmask == ((1 << N) - 1)){ //All vertices have been explored return cost[pos][0]; //Cost to go back } if (memo[bitmask][pos] != -1){ //If this has already been computed return memo[bitmask][pos]; //Just return the value, no need to recompute } for (int i = 0; i < N; ++i){ //For every vertex if ((bitmask & (1 << i)) == 0){ //If the vertex has not been visited cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]); //Visit the vertex } } memo[bitmask][pos] = cost; //Save the result return cost; } //Call TSP(1,0)

This line may be a little confusing, so lets go through it slowly:

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

Here, `bitmask | (1 << i)`

sets the ith bit of `bitmask`

to 1, which represents that the ith vertex has been visited. The `i`

after the comma represents the new `pos`

in that function call, which represents the new “last” vertex. `cost[pos][i]`

is to add the cost of travelling from vertex `pos`

to vertex `i`

.

Thus, this line is to update the value of `cost`

to the minimum possible value of travelling to every other vertex that has not been visited yet.

**Time Complexity**

The function `TSP(bitmask,pos)`

has `2^N`

values for `bitmask`

and `N`

values for `pos`

. Each function takes `O(N)`

time to run (the `for`

loop). Thus this implementation takes `O(N^2 * 2^N)`

time to output the exact answer.