The Travelling Salesman

A unique DP problem

A very tired salesman comes to you today in his dire need for help.

The travelling salesman has 20 cities to visit. He has to visit all of them within a single day. The cities are labelled from 0 to 19. The salesman carries with him a map, and it contains the distance from every city to every other city. He can visit the cities in any order he likes, as long as

1. He starts and ends his travel in the same city

2. He never visits the same city more than once, except of course the starting city, which he visits exactly twice

He wants to minimise the distance he needs to travel. Care to assist him?

Dear reader,

Thank you for supporting Elucidate: for the curious coder. These next few weeks are going to be busy, so expect the length of articles to reduce for a short while.

It’s hard work writing alone. I appreciate all support for my writing. Please consider pledging your financial support- I ask for less than 2 cups of coffee a month, and in return you get a new brain-boosting problem solving adventure every week.

Subscribe or pledge your support here

At the end of these few weeks, I’ll release a much longer article that will be an enjoyable read. Till then, all help is much appreciated.

Understanding the problem

First appearances can be deceiving. Even though it looks like it, this problem is not a graph problem.

This problem is a Dynamic Programming problem.

You can read more about Dynamic Programming below, but I’ll summarise the details here.

Dynamic Programming (DP)

Dynamic programming is a technique in which we keep track of certain values to avoid repetitive re-computation in order to save time and make algorithms faster.

In this case, we’re going to use Dynamic programming to speed up the solution for this problem.

Problem states

Let’s start by asking, how many possible answers to the problem exist?

There are 20 cities. Every potential answer takes the forms of a sequence of cities that the salesman should visit, in order. One of these sequences is correct, our job is to find that sequence. So, how many sequences are there?

Well, the first city in the sequence can be any one of the 20 cities. There are 19 possibilities after that for what the second city could be, and 18 possibilities for the third city, and so on. This gives us a total of 20! possibilities (a 19 digit number). If we look at every possible answer, the salesman and his kids, grandkids, great-grandkids, and the entire human race would have perished by the time the program finds the answer. We need a better solution.

Making observations

Since the salesman starts and ends at the same city, you can say that the path taken by the salesman is a loop. That means you can let any city on the loop be the starting city, it doesn’t matter. Think of it as the same reason a circle looks the same no matter where you look at it from. Hence, it is safe to assume that you start and end at city 0.

Now let’s say you’re solving the problem and are currently at some city, let’s call it city x. Suppose also you have an array, a, that tracks the cities you have already visited. Now from city x, you can choose to visit any city that is not already visited. Let’s say you decide to visit city u. City u is added to the array a, and so you continue the process from city u.

Notice something? Instead of looking at every single solution, you can start from city 0 and begin constructing a solution from there. Let’s consider how you would do this.

Using bitmasks

Another cool data structure to help us. You must know what a bitmask is before reading further.

Bitmasks

We can represent the problem state using just a number and a bitmask. Using this, we write a more efficient simulation that the behaviour of the salesman can follow.

Problem-solving philosophy

When solving such a problem, a good method is to write a simulation. So here we’re going to slowly unpack the step-by-step process of solving the travelling salesman problem. Ready? Let’s go.

First, we want to simulate the movement of the salesman, so let’s create a function called dp. When called, dp takes some parameters and gives us the smallest distance it will take to complete the tour given those parameters. What parameters does the function need?

• A city, x

• A list of cities that have not yet been traversed. This takes the form of a bitmask called b.

So dp(x, b) gives us the smallest distance that the salesman must cover to finish his tour given that he is at city x and has not yet visited the cities in b. Since b is a bitmask, every bit that is 1 represents a city yet to be visited, and every bit that is 0 represents a city that has already been visited.

Now imagine how we’d go about answering this question. For every bit in b, we check if it is one. Suppose the u-th bit is 1. That means we have yet to visit city u. So we

1. Move to city u

2. Update the bitmask to show that u is visited

3. Update the distance travelled

4. Repeat the process from city u with our new bitmask

Since the salesman’s map shows the distance from every city to every city, let dist be a matrix such that dist[x][u] stores the distance from city x to city u.

We want to find, of all the cities we can visit from city x with bitmask b, which city allows us to complete the tour in the shortest time?

Our function so far looks like this.

int dist(int x, int b) {
  // if all cities visited, return to 0 and finish the tour
  if (b == 0) return dist[x][0]; 
  int answer = 10000000; 
  for (int u = 0; u < 20; u++) {
    if (b & (1<<u) == 0) continue; // already visited this city 
    int new_mask = b ^ (1<<u);  // try visiting city u
    ans = min(ans, dist[x][u] + dp(u, new_mask)); // update answer 
  }
  return answer; // return best answer among all u
}

There’s a minor problem though. This function will be too slow because we keep calling the same function again and again. Here’s an example.

Suppose one run of the function starts of at x = 0 and moves to city 1, then moves to city 2,and from there calls the function dp(3, 111…10000) to try moving to city 3. Then another run of the function starts of at x = 0 and moves to city 2 instead, then to city 1, and then calls dp(3, 111…10000). The same function is called twice. We need a way to remember when we’ve called this function before, so we use a matrix memo. memo[x][b] stores the answer to dp(x,b). All values in memo start off at -1 to signify that we don’t know the answer yet.

Now, when we call a function, we check if we’ve computed it before by checking if memo[x][b] is -1. And when we get the answer for a function call, we update memo[x][b]. Let’s add that to the code.

int dist(int x, int b) {
  if (b == 0) return dist[x][0];
  if (memo[x][b] != -1) return memo[x][b]; // already computed 
  int ans = 10000000; 
  for (int u = 0; u < 20; u++) {
    if (b & (1<<u) == 0) continue; // already visited this city 
    int new_mask = b ^ (1<<u);  // try visiting city u
    ans = min(ans, dist[x][u] + dp(u, new_mask)); // update answer 
  }
  memo[x][b] = ans; 
  return answer; // return best answer among all u
}

Finally, we solve the problem by calling dp(0, (1«20)-2), as this is our starting state.

And that’s how you solve the problem!

---

Reflection questions

• What did you learn from this problem?

• Why is the bitmask an efficient representation?

• What is the time complexity of this solution?

• How do we know there is no faster way to solve it?

Thanks for reading, and I’ll see you in the next one.

If you enjoyed this article, click here to pledge your support. I ask less than 2 cups of coffee a month, and all help is much appreciated.