Traveling Salesman with Held and Karp Algorithm

Question

I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP.

I have implemented it with bitmask, and it's something like this:

int TSP(int pos, int bitmask) {
  if (bitmask == (1<<(K+1))-1)
      return dist[pos][0];              // Completing the round trip

  if (memo[pos][bitmask] != -1)
      return memo[pos][bitmask];

  int answer = INF;
  for (int i = 0; i <= K; i++) {
      if (i != pos && (bitmask & (1 << i)) == 0)
          answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i)));
  }

  return memo[pos][bitmask] = answer;     // Storing the best dist for the set of traveled cities and untraveled ones.

}

This algorithm is quite fast; computation of 15 cities is relatively fast enough. However, I notice that it could be further improved to accommodate around 20 cities.

1) If the dist matrix is symmetrical, perhaps we can make use of this property to prevent repeated calculations. (e.g a->b->c->d->a == a->d->c->b->a)

2) Using both a upper and lower bound to prune. The above algorithm is able to get its first possible optimal solution in a very short time, might be able to use that.

I have tried to improve the algorithm based on the aforementioned two principles. However, I don't get a better algorithm.

Am I making a futile attempts at improving something impossible? What do you think?

Answer 1

I think you are right. Under your method, the maximum number of cities may be 20,21 or 22, but cannot be even 25. This is because the number of status in your algorithm is n*(2^n), when n=20, it's about 10^7, when n=25, it's about 10^9, which is a very large number. With modern computers, it can process about 10^7 calculation within 1 second. But it will take about 100 seconds to process 10^9 calculation.

So I think if want to handle more cities, some approximation algorithms may be useful, like simulated annealing algorithm, genetic algorithm, etc. Or you can use multiple machines and scale down the problem.