Exact euclidean Travelling Salesman

Question

I am trying to implement the algorithm to solve the Travelling Salesman Problem.

I know that it is NP-Hard but I only need to solve it for 20 cities. I want to have an excat result and want to use the dynamic programming algorithm.

With my current implementation I am getting an java heap space error. This happens because I create an solution matrix with a index of "1 << n".

I can´t find any information related to this problem. Only found some information for max 10 cities.

Can anyone help me?

This is my code for TSP:

 int n = dist.length;
        int[][] dp = new int[n][n];
        for (int[] d : dp)
            Arrays.fill(d, Integer.MAX_VALUE / 2);
        dp[1][0] = 0;
        for (int mask = 1; mask < 1 << n; mask += 2) {
            for (int i = 1; i < n; i++) {
                if ((mask & 1 << i) != 0) {
                    for (int j = 0; j < n; j++) {
                        if ((mask & 1 << j) != 0) {
                            dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
                        }
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            res = Math.min(res, dp[(1 << n) - 1][i] + dist[i][0]);
        }

        // reconstruct path
        int cur = (1 << n) - 1;
        int[] order = new int[n];
        int last = 0;
        for (int i = n - 1; i >= 1; i--) {
            int bj = -1;
            for (int j = 1; j < n; j++) {
                if ((cur & 1 << j) != 0 && (bj == -1 || dp[cur][bj] + dist[bj][last] > dp[cur][j] + dist[j][last])) {
                    bj = j;
                }
            }
            order[i] = bj;
            cur ^= 1 << bj;
            last = bj;
        }
        System.out.println(Arrays.toString(order));
        return res;

`1 << n` is not too big for `n = 20`. It is simply 1 million, which is fine even when multiplied by `n`. However, you must not allocate it dynamically, just do it statically with your maximum possible `n` instead of creating a new matrix that depends on an input `n`. — i Code 4 Food, Jun 18 '13 at 03:40
I have tried it with some greater numbers like 23,24 and there I have the OutOfMemory error. I dont understand what you mean with "maximum possible n". As I don´t know how big it will be. Could you explain that please. — user1058712, Jun 18 '13 at 03:49
"I only need to solve it for 20 cities" -> if it doesn't need to work for 21 cities, max N is 20. — svinja, Jun 18 '13 at 07:39
If `n` is 20, the code segment provided will take up not much more than a few kilobytes (`dp` is the biggest data structure, taking up around 20*20*4 bytes = 1.6 KB), which obviously shouldn't cause an out-of-memory error. However, when I run the code I get an `ArrayIndexOutOfBoundsException`. — Bernhard Barker, Jun 18 '13 at 07:49

score 1 · Answer 1 · edited Jul 02 '13 at 05:22

1

You should use :

int[][] dp = new int [1 << n][n];

Instead of :

int[][] dp = new int [n][n];

edited Jul 02 '13 at 05:22

Aditya

5,509
4
31
51

answered Jun 18 '13 at 07:56

Tigran

11
2

Exact euclidean Travelling Salesman

1 Answers1