**Traveling Salesman Problem(TSP)** is one of the most famous problems in algorithm and the basic example is below.

https://www.acmicpc.net/problem/2098

First, this is a problem which should be solved with Dynamic Programming.

But I had difficulty in finding the method of defining `memo`

array.

$N$ can be maximum $16$ but I cannot make $16$-dimensional array.

As it turns out, this can be solved with **Bit Masking**.

For example, if $N=4$, then we can define the array as `int memo[4][1<<4]`

.

Then the second dimension can represent each visited city with bits, so actual numbers are from $0$ to $15$ but in bits the range is from $0000$ to $1111$.

The city which is not visited is $0$ and the visited is $1$, so we can represent the current state of visiting.

The initial state is $0000$ and it becomes $0001$ after visiting $0th$ city.

And if we visited $0th$ and $2nd$ city, then the state would be $0101$.

If we visited all cities, then the state is $1111$.

But there is one more problem.

We should specify what `memo`

stands for eventually and how the recursive relation can be represented.

At first, I tried to define that `memo[i][state]`

becomes the value where with the current `state`

, the last city we visited is `i`

.

But in this approach, making codes is quite tricky.

Assume that if $N=4$, we want to find `memo[1][0110]`

.

Then we should check from `memo[0][0000]`

to `memo[3][1111]`

to find states where the city `i`

is not visited and add the weight to it.

So we need an outer loop for $N$ times and the second loop to iterate all states, which becomes the algorithm inefficient.

So we have to re-define the array `memo`

and reduce the code as clear as possible.

There is a general solution for TSP and we need to check several assumptions.

**1. The answer is the same no matter where we start.**

Given the above graph, let’s say that we start from $0$.

With the path $0$->$1$->$2$->$3$->$0$, the answer is $12$.

But this is a traveling problem.

In other words, we just have to find a path which visits all cities and comes back to the beginning.

If we start from $1$, then the answer is also $12$ whose path is $1$->$2$->$3$->$0$->$1$.

And whatever we choose as the starting point, there is no reason to make a detour or select an edge with a bigger weight, so it leads to the same answer.

Therefore, the main idea is not different no matter what the starting point is, so we can choose an arbitrary point as the beginning.

I assumed that the starting point is $0$.

**2. The array represents the current city and the current state.**

Not defining the array `memo`

as I mentioned above, we should define `memo[cur][state]`

as “the value where I am in city `cur`

now and the current visiting state is `state`

”.

This can reduce the difficulty in making recursive relation, because with recursive function if we return the final value properly, we can get the answer by adding them.

Let’s see the function `main`

first.

```
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<vector<int>> W;
vector<vector<int>> memo;
const int INF = 20000000;
int main() {
scanf("%d", &N);
W.assign(N, vector<int> (N, 0));
memo.assign(N, vector<int> (1 << N, 0));
for (int i=0; i<N; ++i) {
for (int j=0; j<N; ++j) {
scanf("%d", &W[i][j]);
}
}
printf("%d\n", TSP(0, 1));
return 0;
}
```

We can see that the initial spot is $0$ and the state is initialized with $0001$ and `TSP`

is called.

```
int TSP(int cur, int state) {
int ret = INF;
if (memo[cur][state] != 0) {
return memo[cur][state];
} else {
if (state == (1<<N)-1) {
if (W[cur][0] != 0) {
return W[cur][0];
} else {
return INF;
}
}
for (int i=0; i<N; ++i) {
if ((state & (1<<i)) || (W[cur][i] == 0)) {
continue;
}
ret = min(ret, TSP(i, state | (1<<i)) + W[cur][i]);
}
memo[cur][state] = ret;
}
return ret;
}
```

The function `TSP(int cur, int state)`

returns the minimum traveling distance we want, if the current spot is `cur`

and the current state is `state`

.

This is made as a recursive function, and of course this is Dynammic Programming so it returns the value immediately if the value is already calculated.

If not, then it checks whether the state represents the situations that all cities are visited.

If it is the case that we visited all cities, then the function returns the distance from the starting point $0$ to the last spot, which is the current `cur`

.

If there is no distance, then it returns substantially large value so that this cannot be chosen as the answer.

In other cases, now the function runs from $0$ to $N-1$ and calls itself recursively.

First, we exclude the cases that `state`

already visited $i$th city and that there is no way from `cur`

to `i`

.

Then we call `TSP`

with the assumption that now we visited `i`

.

Called function will keep calling itself until it visits all spots adding proper weight value continuously.

That is, recursively called `TSP`

function comes back with the minimum traveling distance from the next spot to the last spot.

Adding it with the distance from `cur`

to `i`

will get the final result.

Then the array `memo`

is updated with the returned result.

This is the entire codes.

```
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<vector<int>> W;
vector<vector<int>> memo;
const int INF = 20000000;
int TSP(int cur, int state) {
int ret = INF;
if (memo[cur][state] != 0) {
return memo[cur][state];
} else {
if (state == (1<<N)-1) {
if (W[cur][0] != 0) {
return W[cur][0];
} else {
return INF;
}
}
for (int i=0; i<N; ++i) {
if ((state & (1<<i)) || (W[cur][i] == 0)) {
continue;
}
ret = min(ret, TSP(i, state | (1<<i)) + W[cur][i]);
}
memo[cur][state] = ret;
}
return ret;
}
int main() {
scanf("%d", &N);
W.assign(N, vector<int> (N, 0));
memo.assign(N, vector<int> (1 << N, 0));
for (int i=0; i<N; ++i) {
for (int j=0; j<N; ++j) {
scanf("%d", &W[i][j]);
}
}
printf("%d\n", TSP(0, 1));
return 0;
}
```

One more question, is it profitable as DP?

It seems that by visiting each city, the case will spread out so there might not be a value in the array we want.

Then can we say that this is an efficient way for TSP problem?

Obviously, YES.

As described in the image, there are repeated calculations even if it was already calculated.

The example is the case that $N=4$, so it might seem to not be enormously efficient but assume that $N$ is much bigger.

The overlapping cases will become much larger.

Reducing the number of calling recursive functions leads to the benefit of the computational time anyway.