状态压缩在算法中的应用

发表于 更新于 分类于 Waline：

在计算机算法中，状态压缩是一种优化技术，它通过将一些状态信息压缩成更小的数据结构来减少内存使用和提高程序效率。通常情况下，状态压缩适用于需要处理大量状态的算法，例如搜索、动态规划等。状态压缩的常见方法包括使用位运算、哈希表、数组等数据结构来存储状态信息。这些方法可以显著减少算法的时间和空间复杂度，提高算法的执行效率。

简单来说，状态压缩就是在一个用一种更加巧妙地方式去减少算法运行过程中各种状态的CURD，从而减少时间复杂度和空间复杂度。

我们就以leetcode上的一道题来实战下状态压缩在动态规划中的应用：

这是题干：

给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。

任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

这个题目也是个二分图的问题，不过和匈牙利算法所解决的问题不同，这里的配对不是只能一对一，而是可以多对多，只要每个点都和另一个图中的某个点相连就好

我们来看一下这道题的解题思路

记第一组点数为size1size_1，第二组点数为size2size_2。根据数据范围，我们可以使用二进制数 s 来表示一个点集，s 的第 k 位为 1 表示第 k 个点在点集 s 中，s 的第 k 位为 0 表示第 k 个点不在点集 s 中。使用 dp[i][s] 表示第一组的前 iii 个点（前 i 个点指第 0,1,2,…,i−1 个点）与第二组的点集 s 的最小连通成本（因为 size1≥size2，所以将第二组作为点集），有四种情况：

  • i=0 且 s=0：
    两组点都为空，因此最小连通成本为 dp[0][0]=0。

  • i=0 且 s≠0
    第一组的点为空，第二组的点不为空，因此无法连通，令 dp[0][s]=∞。

  • i≠0 且 s=0：
    第一组的点不为空，第二组的点为空，因此无法连通，令 dp[i][0]=∞。

  • i≠0 且 s≠0
    考虑第一组第 i−1 个点与第二组点集 s 的第 k 个点连接，使用s−ks_{-k}表示点集 s 去除第 k 个点后的剩余点集，那么连通成本 c 有三种情况：

    • 第二组点集 s 的第 k 个点不再与其他点连接，那么 c=dp[i][s−k]+cost[i−1][k]；

    • 第一组第 i−1 个点不再与其他点连接，那么 c=dp[i−1][s]+cost[i−1][k]；

    • 第一组第 i−1 个点和第二组点集 s 的第 k 个点都不再与其他点连接，那么 c=dp[i−1][s−k]+cost[i−1][k]。

枚举第一组第 i−1 个点与第二组点集 s 中任一 k∈s 的点连接，那么状态转移方程如下：

dp[i][s]=min⁡k∈s{min⁡{dp[i][s−k],dp[i−1][s],dp[i−1][s−k]}+cost[i−1][k]}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var connectTwoGroups = function(cost) {
    const size1 = cost.length;
    const size2 = cost[0].length;
    const m = 1 << size2;
    const dp = Array.from(Array(size1 + 1), () => new Array(m).fill(Number.MAX_SAFE_INTEGER / 2));

    dp[0][0] = 0;

    for (let i = 1; i <= size1; i++) {
        for (let s = 0; s < m; s++) {
        for (let k = 0; k < size2; k++) {
            if ((s & (1 << k)) === 0) {
            continue;
            }
            dp[i][s] = Math.min(dp[i][s], dp[i][s ^ (1 << k)] + cost[i - 1][k]);
            dp[i][s] = Math.min(dp[i][s], dp[i - 1][s] + cost[i - 1][k]);
            dp[i][s] = Math.min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost[i - 1][k]);
        }
        }
    }

    return dp[size1][m - 1];
};

数据结构上进行压缩

这个算法中的动态规划不用多讲了，其实这里面也蕴含着状态压缩，比如将一个布尔数组压缩为一个二进制的数字就是一个常见的做法，可能从空间上讲看不出多大提升，但是在本题中，我们需要以布尔数组表示状态，并以这个状态为key时，那么我们只能用map来存储键值对，但是如果我们实用二进制数字作为key，我们就可以使用数组来存储键值对了。

剔除无用的中间状态的存储

另一种状态压缩指的是识别出无用的状态并进行剔除

转移方程的 dp[i][∗] 计算只与 dp[i−1][∗] 和 dp[i][∗] 相关，因此我们可以只使用一维数组来保存，从而节省空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var connectTwoGroups = function(cost) {
    const size1 = cost.length;
    const size2 = cost[0].length;
    const m = 1 << size2;
    const dp1 = new Array(m).fill(Number.MAX_SAFE_INTEGER / 2);
    const dp2 = new Array(m);
    
    dp1[0] = 0;

    for (let i = 1; i <= size1; i++) {
        for (let s = 0; s < m; s++) {
        dp2[s] = Number.MAX_SAFE_INTEGER / 2;
        for (let k = 0; k < size2; k++) {
            if ((s & (1 << k)) === 0) {
            continue;
            }
            dp2[s] = Math.min(dp2[s], dp2[s ^ (1 << k)] + cost[i - 1][k]);
            dp2[s] = Math.min(dp2[s], dp1[s] + cost[i - 1][k]);
            dp2[s] = Math.min(dp2[s], dp1[s ^ (1 << k)] + cost[i - 1][k]);
        }
        }
        dp1.splice(0, m, ...dp2);
    }

    return dp1[m - 1];
};