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.