Travelling Salesman Problem

The problem, simply

There are N places, numbered 0 to N - 1. Place 0 is home. You get a table dist[i][j]: how far it is from place i to place j. Start at home, visit every other place exactly once, and come back home.

Give back the smallest total distance. The table may be one-sided: going from i to j can cost something different from going back.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of visiting the friends.

1. Start at home with nothing visited.
2. Pick any unvisited friend, ride there, and add the distance.
3. When everyone is visited, add the ride home and keep the smallest total.
4. Undo the last choice and try the next friend (backtracking).

class TSPBrute {
    static int best;

    public static int tsp(int[][] dist) {
        int n = dist.length;
        best = Integer.MAX_VALUE;
        boolean[] seen = new boolean[n];
        seen[0] = true;
        go(dist, 0, 1, 0, seen);
        return best;
    }

    // at: where we stand, count: places visited, cost: distance so far
    static void go(int[][] dist, int at, int count, int cost, boolean[] seen) {
        int n = dist.length;
        if (count == n) { best = Math.min(best, cost + dist[at][0]); return; }  // ride home
        for (int next = 1; next < n; next++) {
            if (seen[next]) continue;
            seen[next] = true;
            go(dist, next, count + 1, cost + dist[at][next], seen);
            seen[next] = false;
        }
    }
}

How long it takes: there are (N - 1)! orders, and building each one costs about N steps, so O(N!) in total. For N = 15 that is already over a trillion. Extra room: the seen marks and the recursion, O(N).

Way 2: the clever way

Use the notebook. A page is named by two things: the set of places already visited and the place you stand at now. Write the set as a row of on and off switches, one per place (a bitmask). For example {0, 1, 3} is the number 1011 in binary.

1. dp[set][end] is the shortest ride that starts at home, visits exactly set, and ends at end. Start with dp[{0}][0] = 0.
2. Fill pages from small sets to big sets. From a page dp[set][u], try riding to any place v not in set: dp[set + v][v] = min(itself, dp[set][u] + dist[u][v]).
3. When the set holds every place, add the ride home: the answer is the smallest dp[all][u] + dist[u][0].

The pages are a table with one row per set and one column per end place. Each cell only looks at cells from rows with one fewer place.

class TSPBitmask {
    public static int tsp(int[][] dist) {
        int n = dist.length;
        if (n == 1) return 0;                          // nobody to visit
        int full = (1 << n) - 1;
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[1 << n][n];               // dp[set][end]
        for (int[] row : dp) Arrays.fill(row, INF);
        dp[1][0] = 0;                                  // only home visited, standing at home

        for (int mask = 1; mask <= full; mask += 2) {  // odd masks: home is always in the set
            for (int u = 0; u < n; u++) {
                if (dp[mask][u] >= INF) continue;      // a page we never reached
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0) continue;   // already visited
                    int next = mask | (1 << v);
                    dp[next][v] = Math.min(dp[next][v], dp[mask][u] + dist[u][v]);
                }
            }
        }

        int best = INF;
        for (int u = 1; u < n; u++) best = Math.min(best, dp[full][u] + dist[u][0]);  // ride home
        return best;
    }
}

How long it takes: 2^N sets times N standing places, and each page tries N next places, O(N^2 * 2^N). For N = 20 that is about 400 million simple steps, which is fine, while 20! is hopeless. Extra room: the table, O(N * 2^N).

Watch out for

• Only one place: return 0. The final loop over u = 1..n-1 is empty and would return a huge number.
• Filling sets in increasing number order works, because adding a place always makes the number bigger.
• Missing roads are often given as 0 or -1. Turn them into a big number first, and do not add to INF in a way that overflows.
• Memory: 2^20 * 20 ints is about 80 MB. Around N = 20 to 25 is the practical limit.

What interviewers ask next

• Print the trip, not just its length. Store which u gave each best cell, then walk back from the best last place.
• You do not need to come home. Take the smallest dp[full][u] without adding the ride home.
• N is 100 or 1000. Then exact answers are out of reach (the problem is NP-hard). Use a good guess: nearest neighbor, then improve with 2-opt swaps. If distances obey the triangle rule, Christofides' method is never worse than 1.5 times the best.
• Visit only some must-see places on a big map. Run shortest paths between the must-see places first (Dijkstra or Floyd Warshall), then run this bitmask method on just those.
• Can you write it top down? Yes: solve(mask, u) with memo returns the best way to finish from there. Same complexity.

Remember this

Grown-up words: the places are vertices of a complete weighted graph, the round trip is a Hamiltonian cycle, the row of on and off switches is a bitmask, the notebook is a dynamic programming table (the Held Karp algorithm), and trying every order is brute force over permutations.