Travelling Salesman Problem

Intuition

TSP: find minimum cost Hamiltonian cycle. DP with bitmask states: dp[mask][i] = min cost to visit exactly the nodes in mask, ending at node i.

Algorithm

1dp[1][0] = 0 (starting at node 0, visited only node 0).
2For each mask, for each node i in mask: for each j not in mask: dp[mask|(1<<j)][j] = min(dp[mask][j], dp[mask][i] + dist[i][j]).
3Answer = min(dp[(1<<n)-1][i] + dist[i][0]) for all i.

Common Pitfalls

•Time O(2^n * n^2). Feasible only for n <= 20. Final step: return to start node.

Travelling Salesman Problem.java

Java

// Approach: Bitmask DP. dp[mask][i] = min cost to visit all cities in mask ending at city i.
// Time: O(2^n * n^2) Space: O(2^n * n)
import java.util.*;

class Solution {
    public int tsp(int[][] cost) {
        int n = cost.length;
        int N = 1 << n;
        int INF = (int) 1e9;

        int[][] dp = new int[N][n];
        for (int i = 0; i < N; i++)
            Arrays.fill(dp[i], INF);

        dp[1][0] = 0;

        for (int mask = 0; mask < N; mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0)
                    continue;
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0)
                        continue;
                    int next = mask | (1 << v);
                    dp[next][v] = Math.min(dp[next][v], dp[mask][u] + cost[u][v]);
                }
            }
        }

        int ans = INF;
        int full = N - 1;
        for (int u = 0; u < n; u++)
            ans = Math.min(ans, dp[full][u] + cost[u][0]);

        return ans;
    }
}

Was this solution helpful?