Application of State Compression in Algorithms

Posted on Edited on In Waline:

In computer algorithms, state compression is an optimization technique that reduces memory usage and improves program efficiency by compressing some state information into smaller data structures. Typically, state compression is applied to algorithms that need to handle a large amount of state, such as search, dynamic programming, etc. Common approaches to state compression include using data structures such as bitwise operations, hash tables, arrays, etc. to store state information. These methods can significantly reduce the time and space complexity of the algorithm and improve the execution efficiency of the algorithm.

Simply put, state compression is a more subtle way to reduce the CURD of various states during the operation of an algorithm, thus reducing both time and space complexity.

Let’s use a problem from leetcode to demonstrate the use of state compression in dynamic programming:

This is the stem of the question:

You are given two sets of points, where the first set has size1 points and the second set has size2 points, and size1 >= size2.

The cost of connection between any two points is given by a matrix of size1 x size2, where cost[i][j] is the cost of connection between point i in the first group and point j in the second group. Two groups of points are said to be connected if each point in both groups is connected to one or more points in the other group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.

Returns the minimum cost required to connect the two sets of points.

This topic is also a dichotomous graph problem, but it is not the same as匈牙利算法The problem solved is different in that the pairing here is not one-to-one, but many-to-many, as long as each point is connected to a point in another graph

Let’s look at the solution to this problem

Let the first set of points besize1size_1 and the second set of points besize2size_2. Depending on the range of the data, we can use the binary number s to represent a point set, where the kth bit of s is 1 to indicate that the kth point is in point set s, and the kth bit of s is 0 to indicate that the kth point is not in point set s. Use dp[i][s] to denote the first iii points of the first set (the first i points are the 0th,1st,2nd,…,i-1st points). ,i-1 points) with the minimum connectivity cost of the second set of points s (since size1 ≥ size2, the second set is taken as the set of points) in four cases:

  • i=0 and s=0:
    Both sets of points are empty, so the minimum connectivity cost is dp[0][0] = 0.

  • i=0 and s≠0
    The points in the first group are empty and the points in the second group are not empty, so they cannot be connected, such that dp[0][s] = ∞.

  • i≠0 and s=0:
    The points in the first group are not empty, and the points in the second group are empty, so they cannot be connected, such that dp[i][0] = ∞.

  • i≠0 and s≠0
    Consider the first set of i-1 points connected to the kth point of the second set of points s. Usings−ks_{-k} to denote the remaining set of points after the kth point is removed from the point set s, then the connectivity cost c has three cases:

    • the kth point of the second set of points s is no longer connected to other points, then c = dp[i][s-k] + cost[i-1][k];

    • the first group of points i-1 is no longer connected to other points, then c = dp[i-1][s] + cost[i-1][k];

    • The first set of points i-1 and the kth point of the second set of points s are no longer connected to other points, then c=dp[i-1][s-k]+cost[i-1][k].

Enumerate the first set of points i-1 connected to any point k ∈ s in the second set of points s. Then the state transfer equation is as follows:

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];
};

Compression on data structure

The dynamic programming in this algorithm needs no further explanation, in fact, it also contains state compression, for example, compressing a boolean array into a binary number is a common practice, which may not see much improvement in terms of space, but in this problem, we need to represent the state with a boolean array and use this state as the key, then we can only use map to store the key-value pairs, but if we use binary numbers as key, we can use arrays to store key-value pairs.

Eliminate storage of useless intermediate states

Another type of state compression refers to identifying useless states and eliminating them

The calculation of dp[i][∗] for the transfer equation is only related to dp[i-1][∗] and dp[i][∗], so we can save space by using only one-dimensional arrays to keep it.

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];
};