每日算法 — 使用java实现旅行商问题：状态压缩动态规划与贪心近似算法

问题描述

旅行商问题（Traveling Salesman Problem, TSP）：给定 n 个城市以及城市之间的距离，求从某个城市出发，经过每个城市恰好一次，最终回到起点的最短路径长度。

TSP 是组合优化中最著名的 NP 难问题之一，在物流路径规划、电路板钻孔、基因测序等领域有广泛实际应用。

解法一：状态压缩动态规划（精确解）

设 dp[mask][i] 表示已经访问过的城市集合为 mask，且当前位于城市 i 时的最短路径长度。

public class TSPDynamicProgramming {

    // 状态压缩DP，适用于 n <= 20 的情况
    public static int tsp(int[][] dist) {
        int n = dist.length;
        int fullMask = (1 << n) - 1;

        // dp[mask][i]: 已访问mask中的城市，当前在城市i的最小距离
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) java.util.Arrays.fill(row, Integer.MAX_VALUE / 2);

        // 从城市0出发
        dp[1][0] = 0;

        for (int mask = 1; mask <= fullMask; mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue; // last不在mask中
                if (dp[mask][last] >= Integer.MAX_VALUE / 2) continue;

                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue; // next已访问
                    int newMask = mask | (1 << next);
                    dp[newMask][next] = Math.min(dp[newMask][next], 
                                                  dp[mask][last] + dist[last][next]);
                }
            }
        }

        // 回到起点城市0
        int minCost = Integer.MAX_VALUE;
        for (int last = 1; last < n; last++) {
            minCost = Math.min(minCost, dp[fullMask][last] + dist[last][0]);
        }
        return minCost;
    }

    // 路径还原版本
    public static int tspWithPath(int[][] dist, int[] bestPath) {
        int n = dist.length;
        int fullMask = (1 << n) - 1;
        int[][] dp = new int[1 << n][n];
        int[][] parent = new int[1 << n][n];

        for (int[] row : dp) java.util.Arrays.fill(row, Integer.MAX_VALUE / 2);
        dp[1][0] = 0;

        for (int mask = 1; mask <= fullMask; mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue;
                if (dp[mask][last] >= Integer.MAX_VALUE / 2) continue;

                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;
                    int newMask = mask | (1 << next);
                    int newCost = dp[mask][last] + dist[last][next];
                    if (newCost < dp[newMask][next]) {
                        dp[newMask][next] = newCost;
                        parent[newMask][next] = last;
                    }
                }
            }
        }

        int minCost = Integer.MAX_VALUE;
        int lastCity = -1;
        for (int last = 1; last < n; last++) {
            int cost = dp[fullMask][last] + dist[last][0];
            if (cost < minCost) {
                minCost = cost;
                lastCity = last;
            }
        }

        // 回溯路径
        int mask = fullMask;
        for (int i = n - 1; i >= 0; i--) {
            bestPath[i] = lastCity;
            int prev = parent[mask][lastCity];
            mask ^= (1 << lastCity);
            lastCity = prev;
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };
        System.out.println("最短TSP路径长度: " + tsp(dist)); // 80

        int[] path = new int[dist.length];
        System.out.println("带路径的最短长度: " + tspWithPath(dist, path));
        System.out.println("路径: " + java.util.Arrays.toString(path));
    }
}

时间复杂度 O(n² × 2ⁿ)，空间复杂度 O(n × 2ⁿ)。当 n = 20 时，2²⁰ ≈ 100万，尚可接受。

解法二：最近邻贪心近似

public class TSPNearestNeighbor {

    // O(n²) 贪心近似，不保证最优，但速度快
    public static int tspNearestNeighbor(int[][] dist) {
        int n = dist.length;
        boolean[] visited = new boolean[n];
        int current = 0;
        visited[0] = true;
        int totalCost = 0;
        int count = 1;

        while (count < n) {
            int nearest = -1;
            int minDist = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && dist[current][i] < minDist) {
                    minDist = dist[current][i];
                    nearest = i;
                }
            }
            totalCost += minDist;
            visited[nearest] = true;
            current = nearest;
            count++;
        }

        // 返回起点
        totalCost += dist[current][0];
        return totalCost;
    }
}

解法三：最小生成树 2-近似

利用 MST 的性质：最优 TSP 回路去掉一条边后得到生成树，因此 MST 权重是 TSP 最优解的下界。对 MST 做前序遍历可得到 2-近似解。

import java.util.*;

public class TSPMSTApproximation {

    // Prim算法求MST
    public static int mstPrim(int[][] dist) {
        int n = dist.length;
        boolean[] inMST = new boolean[n];
        int[] minEdge = new int[n];
        Arrays.fill(minEdge, Integer.MAX_VALUE);
        minEdge[0] = 0;
        int totalWeight = 0;

        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u])) {
                    u = j;
                }
            }
            inMST[u] = true;
            totalWeight += minEdge[u];

            for (int v = 0; v < n; v++) {
                if (!inMST[v] && dist[u][v] < minEdge[v]) {
                    minEdge[v] = dist[u][v];
                }
            }
        }
        return totalWeight;
    }

    // 2-近似：TSP最优解 <= 2 * MST权重
    public static int tspApproximation(int[][] dist) {
        return 2 * mstPrim(dist);
    }
}

算法边界分析

实际应用

在真实物流场景中，城市数往往成千上万，精确 DP 不可行。此时通常采用：
– 遗传算法、模拟退火等元启发式算法
– 约束求解器（如 OR-Tools）
– 结合地理信息的启发式构造

总结

TSP 展示了计算复杂性理论对算法设计的深刻影响：当问题规模增大时，精确算法让位于近似算法与启发式方法。理解不同方法的适用边界，是算法工程师的核心能力之一。