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

问题引入

旅行商问题（TSP）是组合优化中最著名的问题之一：给定N个城市和两两之间的距离，求从起点出发经过所有城市恰好一次并返回起点的最短路径。该问题是NP-hard，但当N较小时（N≤20），可以使用状态压缩动态规划（简称状压DP）在O(N^2 * 2^N)时间内精确求解。本文用Java完整实现TSP的状压DP解法，并深入讲解子集枚举的高效位运算技巧。

算法原理

状态设计

用二进制数mask表示已访问的城市集合，第i位为1表示城市i已访问。dp[mask][i]表示从起点出发，已访问城市集合为mask，且当前位于城市i的最短路径长度。

状态转移方程：

dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])

其中j是mask中未访问的城市。

子集枚举优化

遍历所有状态时，只需枚举mask中包含起点的合法状态，并通过 submask = mask; submask = (submask - 1) & mask 技巧枚举子集。在TSP中，通过预计算每个mask中已设置的位数（popcount），可以快速判断状态是否合法。

完整Java实现

package algorithm.tsp;

import java.util.*;

/**
 * 旅行商问题（TSP）求解器
 * 使用状态压缩动态规划（状压DP）
 */
public class TSPBitmaskDP {

    private final int n;
    private final int[][] dist;
    private final int INF = Integer.MAX_VALUE / 4;
    private int[][] dp;
    private int[][] parent; // 用于路径回溯

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

    /**
     * 求解TSP最短回路（起点固定为0号城市）
     * @return 最短回路长度
     */
    public int solve() {
        int fullMask = (1 << n) - 1;
        dp = new int[1 << n][n];
        parent = new int[1 << n][n];

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

        // 初始状态：从城市0出发
        dp[1][0] = 0;

        // 枚举所有状态
        for (int mask = 1; mask <= fullMask; mask++) {
            // 只处理包含起点（城市0）的状态
            if ((mask & 1) == 0) continue;

            for (int i = 0; i < n; i++) {
                if (dp[mask][i] == INF) continue;
                if ((mask & (1 << i)) == 0) continue; // i不在当前状态中

                // 尝试前往未访问的城市j
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) != 0) continue; // j已访问
                    int newMask = mask | (1 << j);
                    int newCost = dp[mask][i] + dist[i][j];
                    if (newCost < dp[newMask][j]) {
                        dp[newMask][j] = newCost;
                        parent[newMask][j] = i;
                    }
                }
            }
        }

        // 找最短回路：从任意城市返回城市0
        int minCost = INF;
        int lastCity = -1;
        for (int i = 1; i < n; i++) {
            int cost = dp[fullMask][i] + dist[i][0];
            if (cost < minCost) {
                minCost = cost;
                lastCity = i;
            }
        }

        return minCost;
    }

    /**
     * 获取最短路径（城市编号序列）
     */
    public List<Integer> getPath() {
        int fullMask = (1 << n) - 1;
        int minCost = INF;
        int lastCity = -1;
        for (int i = 1; i < n; i++) {
            int cost = dp[fullMask][i] + dist[i][0];
            if (cost < minCost) {
                minCost = cost;
                lastCity = i;
            }
        }

        List<Integer> path = new ArrayList<>();
        int mask = fullMask;
        int city = lastCity;
        while (city != -1 && mask != 0) {
            path.add(city);
            int prev = parent[mask][city];
            mask ^= (1 << city);
            city = prev;
        }
        Collections.reverse(path);
        path.add(0); // 返回起点
        return path;
    }

    /**
     * 扩展：求解从起点到终点的最短Hamilton路径（不返回起点）
     */
    public int solvePath(int start, int end) {
        int fullMask = (1 << n) - 1;
        int[][] dpPath = new int[1 << n][n];
        for (int[] row : dpPath) Arrays.fill(row, INF);
        dpPath[1 << start][start] = 0;

        for (int mask = 0; mask <= fullMask; mask++) {
            if ((mask & (1 << start)) == 0) continue;
            for (int i = 0; i < n; i++) {
                if (dpPath[mask][i] == INF) continue;
                if ((mask & (1 << i)) == 0) continue;
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) != 0) continue;
                    int newMask = mask | (1 << j);
                    dpPath[newMask][j] = Math.min(dpPath[newMask][j], dpPath[mask][i] + dist[i][j]);
                }
            }
        }
        return dpPath[fullMask][end];
    }

    /**
     * 位运算子集枚举示例：枚举mask的所有非空子集
     */
    public static void enumerateSubsets(int mask) {
        System.out.println("枚举子集 of " + Integer.toBinaryString(mask) + ":");
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            System.out.println("  " + Integer.toBinaryString(sub));
        }
    }

    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}
        };
        TSPBitmaskDP tsp1 = new TSPBitmaskDP(dist1);
        int cost1 = tsp1.solve();
        System.out.println("最短回路长度: " + cost1);
        System.out.println("路径: " + tsp1.getPath());

        // 示例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}
        };
        TSPBitmaskDP tsp2 = new TSPBitmaskDP(dist2);
        int cost2 = tsp2.solve();
        System.out.println("\n5城市最短回路长度: " + cost2);
        System.out.println("路径: " + tsp2.getPath());

        // 示例3：Hamilton路径（不返回起点）
        int pathCost = tsp2.solvePath(0, 4);
        System.out.println("从城市0到城市4的Hamilton最短路径: " + pathCost);

        // 子集枚举演示
        System.out.println();
        enumerateSubsets(0b1011);
    }
}

复杂度分析

指标	暴力搜索	状压DP
时间	O(N!)	O(N^2 * 2^N)
空间	O(N)	O(N * 2^N)

当N=20时，N! ≈ 2.4×10^18，而N^2 * 2^N ≈ 4.2×10^8，差距极为悬殊。状压DP的核心优势在于将指数级状态空间从N!降到2^N，通过子集位图避免了重复计算相同城市集合的不同访问顺序。

关键技巧总结

mask | (1 << j) 是添加城市j到位图的标准写法
mask & (1 << j) 的结果非零表示城市j已在集合中
(sub - 1) & mask 是枚举mask所有非空子集的高效位运算技巧
Integer.bitCount(mask) 可快速计算集合大小（Java内置popcount）
对于N>20的情况，状压DP空间会爆炸，此时需要改用启发式算法（如模拟退火、遗传算法）

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