每日算法 — 使用java实现状态压缩DP：子集枚举与位运算优化

一、问题引入

动态规划的状态设计直接决定了算法的复杂度。在某些问题中，状态可以用一个二进制数紧凑地表示——这就是状态压缩动态规划（State Compression DP）。

状态压缩DP最常用于处理集合相关的决策问题，例如旅行商问题（TSP）、集合覆盖、分配问题等。本文将以经典的旅行商问题（TSP）为例，用Java实现状态压缩DP，并深入讲解位运算在状态转移中的优化技巧。

二、算法原理

2.1 什么是状态压缩？

假设有N个城市，我们需要记录哪些城市已经被访问过。如果用布尔数组visited[N]表示，DP状态就是dp[visited[]][current_city]，这在实现上很不方便。

如果用二进制数state代替visited数组：
– state的第i位为1，表示第i个城市已访问
– state的第i位为0，表示第i个城市未访问

这样，N个城市的访问状态就可以用一个N位整数表示，DP状态简化为dp[state][current_city]。

2.2 TSP问题定义

给定N个城市和两两之间的距离，从城市0出发，访问所有城市恰好一次后回到起点，求最短路径长度。

状态定义：dp[state][i] 表示已经访问了state中标记的城市，且当前位于城市i的最短距离。

状态转移：

dp[state][i] = min(dp[state ^ (1<<i)][j] + dist[j][i])
其中 j 是state中除了i之外的所有已访问城市

三、Java代码实现

import java.util.*;

/**
 * 状态压缩动态规划
 * 以旅行商问题(TSP)为例
 */
public class StateCompressionDP {

    private int n;
    private int[][] dist;
    private int INF = Integer.MAX_VALUE / 2;

    public StateCompressionDP(int[][] dist) {
        this.n = dist.length;
        this.dist = dist;
    }

    /**
     * TSP求解 - 状态压缩DP
     * 时间复杂度：O(N^2 * 2^N)
     * 空间复杂度：O(N * 2^N)
     *
     * @return 最短回路长度
     */
    public int solveTSP() {
        int fullState = (1 << n) - 1; // 所有位都为1，表示所有城市都已访问

        // dp[state][i]: 已访问state中的城市，当前在i的最短距离
        int[][] dp = new int[1 << n][n];

        // 初始化
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }

        // 从城市0出发
        dp[1][0] = 0; // state=1(只有第0位为1)，当前在城市0

        // 枚举所有状态
        for (int state = 1; state <= fullState; state++) {
            // 枚举当前所在城市
            for (int i = 0; i < n; i++) {
                if (dp[state][i] == INF) continue;
                if ((state & (1 << i)) == 0) continue; // i不在state中，跳过

                // 尝试前往未访问的城市j
                for (int j = 0; j < n; j++) {
                    if ((state & (1 << j)) != 0) continue; // j已访问，跳过

                    int nextState = state | (1 << j);
                    int newDist = dp[state][i] + dist[i][j];

                    if (newDist < dp[nextState][j]) {
                        dp[nextState][j] = newDist;
                    }
                }
            }
        }

        // 找最短的回到起点的路径
        int minTour = INF;
        for (int i = 1; i < n; i++) {
            if (dp[fullState][i] != INF) {
                minTour = Math.min(minTour, dp[fullState][i] + dist[i][0]);
            }
        }

        return minTour;
    }

    /**
     * TSP求解 - 带路径记录
     * @return 包含最短距离和路径的结果
     */
    public TSPResult solveTSPWithPath() {
        int fullState = (1 << n) - 1;
        int[][] dp = new int[1 << n][n];
        int[][] parent = new int[1 << n][n]; // 记录前驱城市

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

        dp[1][0] = 0;

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

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

                    int nextState = state | (1 << j);
                    int newDist = dp[state][i] + dist[i][j];

                    if (newDist < dp[nextState][j]) {
                        dp[nextState][j] = newDist;
                        parent[nextState][j] = i;
                    }
                }
            }
        }

        // 找最优终点
        int minTour = INF;
        int lastCity = -1;
        for (int i = 1; i < n; i++) {
            if (dp[fullState][i] != INF) {
                int tourLen = dp[fullState][i] + dist[i][0];
                if (tourLen < minTour) {
                    minTour = tourLen;
                    lastCity = i;
                }
            }
        }

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

        return new TSPResult(minTour, path);
    }

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

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

    /**
     * 子集枚举工具方法
     * 枚举state的所有非空子集
     */
    public static void enumerateSubsets(int state) {
        System.out.println("State " + state + " (binary: " + 
            String.format("%" + Integer.SIZE + "s", 
                Integer.toBinaryString(state)).replace(' ', '0') + ") 的子集：");

        // 枚举子集：for (int sub = state; sub > 0; sub = (sub - 1) & state)
        for (int sub = state; sub > 0; sub = (sub - 1) & state) {
            System.out.println("  子集: " + sub + " (" + 
                Integer.toBinaryString(sub) + ")");
        }
    }

    /**
     * 位运算技巧演示
     */
    public static void bitOperationsDemo() {
        System.out.println("=== 位运算技巧 ===");
        int state = 0b10110; // 二进制：10110

        System.out.println("原始状态: " + Integer.toBinaryString(state));
        System.out.println("第1位是否为1: " + ((state & (1 << 1)) != 0));
        System.out.println("第2位是否为1: " + ((state & (1 << 2)) != 0));
        System.out.println("设置第0位为1: " + Integer.toBinaryString(state | (1 << 0)));
        System.out.println("清除第1位: " + Integer.toBinaryString(state & ~(1 << 1)));
        System.out.println("翻转第2位: " + Integer.toBinaryString(state ^ (1 << 2)));
        System.out.println("最低位的1: " + Integer.toBinaryString(state & (-state)));
        System.out.println("清除最低位的1: " + Integer.toBinaryString(state & (state - 1)));
        System.out.println("1的个数: " + Integer.bitCount(state));
    }

    /**
     * 集合覆盖问题的状态压缩DP
     * 给定若干集合，选择最少数量的集合使其并集为全集
     */
    public int solveSetCover(int[] sets, int numElements) {
        int fullMask = (1 << numElements) - 1;
        int[] dp = new int[1 << numElements];
        Arrays.fill(dp, INF);
        dp[0] = 0; // 覆盖空集需要0个集合

        for (int mask = 0; mask <= fullMask; mask++) {
            if (dp[mask] == INF) continue;

            for (int set : sets) {
                int newMask = mask | set;
                if (dp[newMask] > dp[mask] + 1) {
                    dp[newMask] = dp[mask] + 1;
                }
            }
        }

        return dp[fullMask];
    }

    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问题 ===");
        StateCompressionDP solver = new StateCompressionDP(dist);
        int minTour = solver.solveTSP();
        System.out.println("最短回路长度: " + minTour);

        TSPResult result = solver.solveTSPWithPath();
        System.out.println("最短路径: " + result.path + " -> 0");
        System.out.println("路径长度: " + result.distance);

        // 位运算演示
        System.out.println("\n=== 位运算技巧 ===");
        bitOperationsDemo();

        // 子集枚举演示
        System.out.println("\n=== 子集枚举 ===");
        enumerateSubsets(0b1011);

        // 集合覆盖测试
        System.out.println("\n=== 集合覆盖问题 ===");
        int[] sets = {
            0b0011, // 集合1覆盖元素0,1
            0b0110, // 集合2覆盖元素1,2
            0b1100, // 集合3覆盖元素2,3
            0b1001  // 集合4覆盖元素0,3
        };
        int minSets = solver.solveSetCover(sets, 4);
        System.out.println("覆盖所有元素最少需要 " + minSets + " 个集合");
    }
}

四、复杂度分析

状态压缩DP的状态数呈指数级增长，因此通常只适用于N ≤ 20的问题。对于更大的规模，需要结合其他优化策略（如分支限界、启发式搜索等）。

五、位运算核心技巧

六、总结

状态压缩DP将集合状态巧妙地编码为整数，使得原本需要高维数组的DP问题可以紧凑地表示。它是理解位运算与动态规划结合的绝佳切入点，也是解决中小规模集合决策问题的利器。

掌握状态压缩DP后，读者可以将其应用于更多场景：棋盘覆盖、任务分配、子集选择等问题都可以用这个框架求解。关键在于识别出问题中的”集合选择”特征，并将选择状态正确地映射为二进制编码。