1
$\begingroup$

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 attempt at improving something impossible? What do you think?

$\endgroup$
  • 2
    $\begingroup$ People have been developing efficient algorithms for TSP for ages. If you want a really fast implementation, use one of these. There is a high chance that whatever simple improvements you've thought of has also crossed these people's minds, and has been implemented if possible. $\endgroup$ – Yuval Filmus Oct 27 '13 at 16:46
  • $\begingroup$ Is this related to the large number of other questions we've had about Euclidean TSP recently? $\endgroup$ – David Richerby Oct 27 '13 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.