每日算法 — 使用java实现TSP：状态压缩动态规划求解旅行商问题

引言

旅行商问题（Traveling Salesman Problem，TSP）是组合优化中最经典的NP-hard问题之一。给定 n 个城市及两两之间的距离，求从起点出发经过每个城市恰好一次并回到起点的最短回路长度。本文用Java实现基于状态压缩的动态规划解法（Held-Karp算法），时间复杂度为 O(n² × 2ⁿ)，是精确求解TSP的最优算法之一。

问题定义

输入：
– n 个城市，编号 0 到 n-1
– dist[i][j] 表示城市 i 到城市 j 的距离

输出：访问每个城市恰好一次并回到起点的最短回路长度。

示例：
– 4个城市，距离矩阵：
[0, 10, 15, 20]
[10, 0, 35, 25]
[15, 35, 0, 30]
[20, 25, 30, 0]
– 输出：80（路径 0→1→3→2→0）

状态压缩动态规划

核心思想

TSP 的状态可以用一个二进制数表示：第 i 位为 1 表示城市 i 已经被访问过。

设 dp[mask][i] 表示：
– 已经访问过的城市集合为 mask（二进制表示）
– 当前位于城市 i
– 从起点出发到达此状态的最短路径长度

状态转移：

dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])
              对于所有 j ∈ mask 且 j ≠ i

初始状态：dp[1<<0][0] = 0（从城市0出发，只访问了城市0）

最终答案：min(dp[(1<<n)-1][i] + dist[i][0])，对于所有 i

Java实现

public class TSP_DP {

    public static final int INF = Integer.MAX_VALUE / 2; // 避免溢出

    /**
     * 状态压缩DP求解TSP，时间 O(n² × 2ⁿ)，空间 O(n × 2ⁿ)
     * @param dist 距离矩阵，dist[i][j] 表示城市i到城市j的距离
     * @return 最短回路长度
     */
    public static int solveTSP(int[][] dist) {
        int n = dist.length;

        // 状态数：2^n，每个状态记录到达每个终点的最短距离
        int[][] dp = new int[1 << n][n];

        // 初始化所有状态为无穷大
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                dp[mask][i] = INF;
            }
        }

        // 初始状态：从城市0出发，距离为0
        dp[1 << 0][0] = 0;

        // 遍历所有状态
        for (int mask = 1; mask < (1 << n); mask++) {
            // 如果当前状态不包含起点，跳过（必须从起点出发）
            if ((mask & 1) == 0) continue;

            for (int last = 0; last < n; last++) {
                // 如果当前状态不包含last城市，跳过
                if ((mask & (1 << last)) == 0) continue;

                // 如果只有起点一个城市，且last不是起点
                if (mask == (1 << 0) && last != 0) continue;

                if (dp[mask][last] == INF) continue;

                // 尝试扩展到未访问的城市
                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue; // next已访问

                    int newMask = mask | (1 << next);
                    int newDist = dp[mask][last] + dist[last][next];

                    if (newDist < dp[newMask][next]) {
                        dp[newMask][next] = newDist;
                    }
                }
            }
        }

        // 最终答案：从所有城市返回起点
        int fullMask = (1 << n) - 1;
        int minTour = INF;
        for (int last = 1; last < n; last++) {
            if (dp[fullMask][last] + dist[last][0] < minTour) {
                minTour = dp[fullMask][last] + dist[last][0];
            }
        }

        return minTour;
    }

    /**
     * 同时记录路径的TSP解法
     */
    public static Result solveTSPWithPath(int[][] dist) {
        int n = dist.length;
        int[][] dp = new int[1 << n][n];
        int[][] parent = new int[1 << n][n]; // 记录前驱城市

        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                dp[mask][i] = INF;
                parent[mask][i] = -1;
            }
        }

        dp[1 << 0][0] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            if ((mask & 1) == 0) continue;

            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue;
                if (dp[mask][last] == INF) continue;

                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;

                    int newMask = mask | (1 << next);
                    int newDist = dp[mask][last] + dist[last][next];

                    if (newDist < dp[newMask][next]) {
                        dp[newMask][next] = newDist;
                        parent[newMask][next] = last;
                    }
                }
            }
        }

        // 找到最优终点
        int fullMask = (1 << n) - 1;
        int minTour = INF;
        int bestLast = -1;
        for (int last = 1; last < n; last++) {
            int tourLen = dp[fullMask][last] + dist[last][0];
            if (tourLen < minTour) {
                minTour = tourLen;
                bestLast = last;
            }
        }

        // 重构路径
        int[] path = new int[n + 1];
        path[n] = 0; // 回到起点
        int curMask = fullMask;
        int cur = bestLast;
        for (int i = n - 1; i >= 1; i--) {
            path[i] = cur;
            int prev = parent[curMask][cur];
            curMask ^= (1 << cur);
            cur = prev;
        }
        path[0] = 0;

        return new Result(minTour, path);
    }

    static class Result {
        int minDistance;
        int[] path;

        Result(int d, int[] p) {
            this.minDistance = d;
            this.path = p;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("最短距离: ").append(minDistance).append("\n路径: ");
            for (int i = 0; i < path.length; i++) {
                sb.append(path[i]);
                if (i < path.length - 1) sb.append(" → ");
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        // 示例1：4个城市
        int[][] dist1 = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        System.out.println("=== 4城市TSP ===");
        System.out.println("最短回路: " + solveTSP(dist1));
        System.out.println(solveTSPWithPath(dist1));

        // 示例2：5个城市
        int[][] dist2 = {
            {0, 2, 9, 10, 7},
            {2, 0, 6, 4, 3},
            {9, 6, 0, 8, 5},
            {10, 4, 8, 0, 1},
            {7, 3, 5, 1, 0}
        };

        System.out.println("\n=== 5城市TSP ===");
        System.out.println("最短回路: " + solveTSP(dist2));
        System.out.println(solveTSPWithPath(dist2));
    }
}

复杂度分析

扩展与变体

1. 非对称TSP：dist[i][j] ≠ dist[j][i]，上述算法同样适用
2. 多起点TSP：枚举每个起点，取最小值
3. 部分访问：允许跳过某些城市，增加收益权重，变为定向问题（Orienteering）
4. 时间窗口TSP：每个城市有访问时间窗口约束
5. 近似算法：当 n > 20 时，可使用贪心、模拟退火、遗传算法、蚁群算法等启发式方法

总结

TSP的状态压缩动态规划解法（Held-Karp算法）是精确求解中小规模TSP问题的经典方法。通过二进制数紧凑地表示城市访问集合，将指数级的路径枚举转化为可管理的动态规划。虽然时间复杂度仍是指数级，但 O(n² × 2ⁿ) 远优于全排列的 O(n!)。理解状态压缩DP的思想，对解决子集类问题（如集合覆盖、分配问题）具有重要的启发意义。