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

引言

动态规划是解决多阶段决策问题的强大工具，但在面对集合类问题时，传统DP的状态定义往往面临维度爆炸的困境。状态压缩动态规划（State Compression DP）巧妙地利用位运算将集合状态编码为整数，将指数级的状态空间压缩到多项式级别，使得许多NP-hard问题的精确求解成为可能。

旅行商问题（TSP, Traveling Salesman Problem）是最经典的状压DP应用场景之一。给定n个城市和它们之间的距离，寻找从起点出发经过所有城市恰好一次并返回起点的最短路径。当n≤20时，状压DP可以在O(n²·2ⁿ)时间内给出精确解，远优于朴素的O(n!)全排列枚举。

核心原理

状态压缩思想

在TSP问题中，核心状态需要记录：
1. 当前所在城市 i
2. 已经访问过的城市集合 S

如果直接用一个布尔数组表示集合S，状态转移需要O(n)时间来遍历集合，效率低下。状压DP的核心洞察是：n个城市的访问状态可以用一个n位二进制数表示——第j位为1表示城市j已访问，为0表示未访问。

例如，对于5个城市，state = 0b10101（十进制21）表示城市0、2、4已访问，城市1、3未访问。

位运算操作

状压DP的高效性建立在位运算的O(1)操作之上：

操作	表达式	含义
判断城市j是否访问	`(state >> j) & 1`	取出第j位
标记城市j为已访问	`state \\| (1 << j)`	将第j位置1
标记城市j为未访问	`state & ~(1 << j)`	将第j位置0
枚举子集	`for (sub = state; sub > 0; sub = (sub - 1) & state)`	遍历state的所有非空子集

状态转移方程

设 dp[state][i] 表示从起点出发，经过集合state中的所有城市（包含城市i），最终到达城市i的最短路径长度。

状态转移：

dp[state][i] = min{ dp[state ^ (1 << i)][j] + dist[j][i] }
               其中 j ∈ state 且 j ≠ i

边界条件：dp[1 << start][start] = 0，表示从起点出发，只访问了起点，路径长度为0。

最终答案：min{ dp[(1 << n) - 1][i] + dist[i][start] }，表示从某个终点i返回起点的最短总路径。

Java实现

基础TSP求解

import java.util.*;

/**
 * 状态压缩动态规划实现旅行商问题
 * 时间复杂度：O(n^2 * 2^n)
 * 空间复杂度：O(n * 2^n)
 */
public class StateCompressionDP {

    public static final int INF = Integer.MAX_VALUE / 2;

    /**
     * 求解TSP问题，返回最短回路长度
     * @param dist 距离矩阵，dist[i][j]表示城市i到城市j的距离
     * @param start 起点城市编号
     * @return 最短回路长度，若无可行解返回-1
     */
    public static int solveTSP(int[][] dist, int start) {
        int n = dist.length;
        if (n == 0) return 0;
        if (n == 1) return 0;

        // dp[state][i]：已访问城市集合为state，当前位于城市i的最短路径长度
        // state用n位二进制表示，state的第j位为1表示城市j已访问
        int totalStates = 1 << n;
        int[][] dp = new int[totalStates][n];

        // 初始化：所有状态设为无穷大
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }

        // 边界条件：从起点出发，只访问了起点
        dp[1 << start][start] = 0;

        // 按状态从小到大枚举（保证子状态已计算）
        for (int state = 0; state < totalStates; state++) {
            // 跳过不包含起点的状态
            if ((state & (1 << start)) == 0) continue;

            for (int current = 0; current < n; current++) {
                // 跳过当前不在state中的城市
                if ((state & (1 << current)) == 0) continue;
                // 跳过不可达状态
                if (dp[state][current] == INF) continue;

                // 尝试前往下一个未访问的城市
                for (int next = 0; next < n; next++) {
                    // 下一个城市必须未访问
                    if ((state & (1 << next)) != 0) continue;
                    // 必须存在路径
                    if (dist[current][next] == INF) continue;

                    int newState = state | (1 << next);
                    int newDist = dp[state][current] + dist[current][next];
                    if (newDist < dp[newState][next]) {
                        dp[newState][next] = newDist;
                    }
                }
            }
        }

        // 从所有终点返回起点，取最小值
        int fullState = totalStates - 1; // 所有位都为1，表示所有城市都已访问
        int ans = INF;
        for (int end = 0; end < n; end++) {
            if (end == start) continue;
            if (dp[fullState][end] == INF) continue;
            if (dist[end][start] == INF) continue;
            ans = Math.min(ans, dp[fullState][end] + dist[end][start]);
        }

        return ans == INF ? -1 : ans;
    }

    /**
     * 求解TSP并输出具体路径
     */
    public static Result solveTSPWithPath(int[][] dist, int start) {
        int n = dist.length;
        if (n <= 1) return new Result(0, Collections.singletonList(start));

        int totalStates = 1 << n;
        int[][] dp = new int[totalStates][n];
        int[][] parent = new int[totalStates][n]; // 记录前驱城市

        for (int[] row : dp) Arrays.fill(row, INF);
        for (int[] row : parent) Arrays.fill(row, -1);

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

        for (int state = 0; state < totalStates; state++) {
            if ((state & (1 << start)) == 0) continue;

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

                for (int next = 0; next < n; next++) {
                    if ((state & (1 << next)) != 0) continue;
                    if (dist[current][next] == INF) continue;

                    int newState = state | (1 << next);
                    int newDist = dp[state][current] + dist[current][next];
                    if (newDist < dp[newState][next]) {
                        dp[newState][next] = newDist;
                        parent[newState][next] = current;
                    }
                }
            }
        }

        int fullState = totalStates - 1;
        int ans = INF;
        int endCity = -1;
        for (int end = 0; end < n; end++) {
            if (end == start) continue;
            if (dp[fullState][end] == INF) continue;
            if (dist[end][start] == INF) continue;
            int total = dp[fullState][end] + dist[end][start];
            if (total < ans) {
                ans = total;
                endCity = end;
            }
        }

        if (ans == INF) return new Result(-1, Collections.emptyList());

        // 回溯路径
        List<Integer> path = new ArrayList<>();
        int state = fullState;
        int city = endCity;
        while (city != -1) {
            path.add(city);
            int prev = parent[state][city];
            state ^= (1 << city);
            city = prev;
        }
        Collections.reverse(path);
        path.add(start); // 回到起点

        return new Result(ans, path);
    }

    static class Result {
        int distance;
        List<Integer> path;

        Result(int distance, List<Integer> path) {
            this.distance = distance;
            this.path = path;
        }

        @Override
        public String toString() {
            return "最短距离: " + distance + ", 路径: " + path;
        }
    }
}

空间优化版本

/**
 * TSP空间优化版本：使用滚动数组减少空间占用
 * 核心观察：dp[state]只依赖于dp[state去掉某一位]，可用一维数组优化
 */
public class TSPSpaceOptimized {

    public static final int INF = Integer.MAX_VALUE / 2;

    /**
     * 使用一维dp数组优化空间
     * dp[state]表示访问集合state后回到起点的最短距离（需要额外记录终点）
     * 这里使用dp[state] = 当前状态的最优值，配合终点信息
     */
    public static int solveTSPOptimized(int[][] dist, int start) {
        int n = dist.length;
        int totalStates = 1 << n;

        // dp[state][i]压缩为dp[state]存储向量，但这里为了代码清晰
        // 使用一个技巧：按状态位数的奇偶性进行滚动
        int[][][] dp = new int[2][totalStates][n];
        for (int[][] layer : dp) {
            for (int[] row : layer) {
                Arrays.fill(row, INF);
            }
        }

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

        for (int bits = 1; bits < n; bits++) {
            int cur = bits & 1;
            int prev = 1 - cur;

            // 清空当前层
            for (int[] row : dp[cur]) Arrays.fill(row, INF);

            for (int state = 0; state < totalStates; state++) {
                if (Integer.bitCount(state) != bits + 1) continue;
                if ((state & (1 << start)) == 0) continue;

                for (int current = 0; current < n; current++) {
                    if ((state & (1 << current)) == 0) continue;
                    int prevState = state ^ (1 << current);

                    for (int prevCity = 0; prevCity < n; prevCity++) {
                        if ((prevState & (1 << prevCity)) == 0) continue;
                        if (dp[prev][prevState][prevCity] == INF) continue;
                        if (dist[prevCity][current] == INF) continue;

                        int newDist = dp[prev][prevState][prevCity] + dist[prevCity][current];
                        if (newDist < dp[cur][state][current]) {
                            dp[cur][state][current] = newDist;
                        }
                    }
                }
            }
        }

        int fullState = totalStates - 1;
        int finalLayer = (n - 1) & 1;
        int ans = INF;
        for (int end = 0; end < n; end++) {
            if (end == start) continue;
            if (dp[finalLayer][fullState][end] == INF) continue;
            if (dist[end][start] == INF) continue;
            ans = Math.min(ans, dp[finalLayer][fullState][end] + dist[end][start]);
        }

        return ans == INF ? -1 : ans;
    }
}

扩展：集合覆盖状压DP

/**
 * 集合覆盖问题的状压DP解法
 * 给定n个元素的全集，以及m个子集，每个子集有选择成本
 * 求覆盖所有元素的最小成本
 */
public class SetCoverDP {

    public static final int INF = Integer.MAX_VALUE / 2;

    /**
     * @param subsets 每个子集包含的元素列表
     * @param costs 每个子集的选择成本
     * @param n 全集元素个数
     * @return 覆盖所有元素的最小成本
     */
    public static int minSetCover(List<List<Integer>> subsets, int[] costs, int n) {
        int m = subsets.size();
        int fullMask = (1 << n) - 1;

        // dp[mask]表示覆盖mask对应元素集合的最小成本
        int[] dp = new int[1 << n];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        // 预处理：将每个子集转换为位掩码
        int[] subsetMasks = new int[m];
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int elem : subsets.get(i)) {
                mask |= (1 << elem);
            }
            subsetMasks[i] = mask;
        }

        // 枚举所有状态
        for (int mask = 0; mask <= fullMask; mask++) {
            if (dp[mask] == INF) continue;

            // 尝试选择每个子集
            for (int i = 0; i < m; i++) {
                int newMask = mask | subsetMasks[i];
                int newCost = dp[mask] + costs[i];
                if (newCost < dp[newMask]) {
                    dp[newMask] = newCost;
                }
            }
        }

        return dp[fullMask] == INF ? -1 : dp[fullMask];
    }

    /**
     * 更高效的枚举：对每个状态只枚举其超集
     */
    public static int minSetCoverOptimized(List<List<Integer>> subsets, int[] costs, int n) {
        int m = subsets.size();
        int fullMask = (1 << n) - 1;

        int[] dp = new int[1 << n];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        int[] subsetMasks = new int[m];
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int elem : subsets.get(i)) {
                mask |= (1 << elem);
            }
            subsetMasks[i] = mask;
        }

        // 子集枚举优化：对每个mask，枚举所有超集
        for (int mask = 0; mask <= fullMask; mask++) {
            if (dp[mask] == INF) continue;

            // 枚举补集的子集，即枚举所有可能的扩展
            int complement = fullMask ^ mask;
            for (int sub = complement; sub > 0; sub = (sub - 1) & complement) {
                // 检查sub是否恰好是某个子集
                for (int i = 0; i < m; i++) {
                    if (subsetMasks[i] == sub) {
                        int newMask = mask | sub;
                        int newCost = dp[mask] + costs[i];
                        if (newCost < dp[newMask]) {
                            dp[newMask] = newCost;
                        }
                    }
                }
            }
        }

        return dp[fullMask] == INF ? -1 : dp[fullMask];
    }
}

测试用例

public class StateCompressionDPDemo {
    public static void main(String[] args) {
        // TSP测试
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        System.out.println("=== TSP基础版本 ===");
        int tspResult = StateCompressionDP.solveTSP(dist, 0);
        System.out.println("最短回路长度: " + tspResult);

        System.out.println("\n=== TSP路径版本 ===");
        StateCompressionDP.Result result = StateCompressionDP.solveTSPWithPath(dist, 0);
        System.out.println(result);

        System.out.println("\n=== TSP空间优化版本 ===");
        int tspOpt = TSPSpaceOptimized.solveTSPOptimized(dist, 0);
        System.out.println("最短回路长度: " + tspOpt);

        // 集合覆盖测试
        System.out.println("\n=== 集合覆盖问题 ===");
        List<List<Integer>> subsets = Arrays.asList(
            Arrays.asList(0, 1),
            Arrays.asList(1, 2),
            Arrays.asList(0, 2),
            Arrays.asList(0, 1, 2)
        );
        int[] costs = {3, 2, 2, 5};
        int coverResult = SetCoverDP.minSetCover(subsets, costs, 3);
        System.out.println("最小覆盖成本: " + coverResult);
    }
}

复杂度分析

问题	时间复杂度	空间复杂度	适用规模
TSP基础	O(n² · 2ⁿ)	O(n · 2ⁿ)	n ≤ 20
TSP空间优化	O(n² · 2ⁿ)	O(2 · n · 2ⁿ) → O(n · 2ⁿ)	n ≤ 20
集合覆盖	O(m · 2ⁿ)	O(2ⁿ)	n ≤ 20

状压DP的核心瓶颈在于状态数2ⁿ，因此仅适用于n≤20左右的小规模问题。对于更大规模的问题，需要结合分支限界、启发式搜索或近似算法。

经典应用场景

TSP及其变种：配送路线规划、电路板钻孔优化
集合覆盖：广告投放优化、传感器部署
图论问题：最小权顶点覆盖、最大权独立集
博弈问题：小型棋类游戏的必胜策略
分配问题：任务分配、资源调度

技巧总结

状态设计：准确识别需要记录的集合信息，避免冗余状态
位运算优化：善用Integer.bitCount()计算1的个数，用位运算代替数组操作
枚举顺序：通常按状态值从小到大枚举，保证子状态先计算
子集枚举：for (sub = mask; sub > 0; sub = (sub - 1) & mask)是枚举mask所有非空子集的高效写法
空间优化：当dp[state]只依赖于特定层的状态时，可用滚动数组

总结

状态压缩动态规划通过位运算将集合编码为整数，在指数级状态空间中实现了多项式时间的状态转移。本文以TSP为核心案例，展示了状压DP的完整实现，并扩展到集合覆盖问题。掌握状压DP的位运算技巧，能够有效解决规模适中的组合优化问题。

Tagged with: Java 动态规划子集枚举旅行商问题状压DP 状态压缩