寻宝与压缩状态dp

压缩状态的dp与记忆化存储

当我们面对多个不同状态有笛卡尔积个可能性时，即$2^n$个状态时，如果只使用平凡的空间来存储，那么空间复杂度是非常爆炸的。目前，有一种使用Unix中会用到的mask手法来压缩dp的状态空间占用。如果我们的状态个数n小于32时，我们通常会采用这种方法来对dp算法进行优化。通常，也会伴随记忆化存储来进优化时间。

这里，我挑选了一题，其非常具有代表性，可以灵活用到mask以及记忆化存储的方法。废话不多说，直接看题。

题目

我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。
迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 ‘S’ 表示），和唯一的宝藏地点（用 ‘T’ 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 ‘M’ 表示），只有所有机关均被触发，才可以拿到宝藏。
要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 ‘O’ 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。
迷宫中同样有一些墙壁（用 ‘#’ 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 ‘.’ 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。
我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。

寻宝示意图，来自leetcode

限制：

1 <= maze.length <= 100
1 <= maze[i].length <= 100
maze[i].length == maze[j].length
S 和 T 有且只有一个
0 <= M的数量 <= 16
0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。

心路历程

这是路径搜索的进阶题型。我们最终的目的是从S走到T，其中需要经过O与M，不难看出，我们需要计算从S到O，O到M，M到O，以及M到T的路径，并从中选择最短的排列组合。由于其中的状态较多，我们发现可以对其进行优化。

因为我们发现，所有组合的路径中，总有S->O->M，M->O->M，M->T。因此，我们可以将O优化掉。如果使用$s(i, j)$来表示从i点到j点的最短距离的话，我们可以得到以下的表达：

$$
s(i,j) = min{\ s(i, k)+s(k, j) \ \ \ for\ k\ in\ O\ }
$$

那么，算法的步骤大体就出来了，如下：

  1. 先计算如果有M点的话，是否有至少一个O点，如果没有，则直接返回-1，结束，题中的限制说明如果有M点，那么至少有一个O点，那么我们在这题就可以不考虑这种情形，但如果M点个数为0，该题退化为从S到T有障碍的最短路径问题。
  2. 再计算各个状态之间的最短路径；即$s(i,j)$，其中的i，j对应上述的路径。使用BFS的算法，每次有O(mn)的空间负责度，i，j等价，即$s(i, j)=s(j, i)$，只计算一次。
  3. 然后遍历除O以外的所有点，来消除O点，到这一步，我们有了S->M,M->M'，以及M->到’T’的最短路径大小。
  4. 到第三步，我们需要检查是否有点是不能到终点或起点的，如果有则返回-1；
  5. 到了这里，就使用dp，来计算总的路径。这里使用$f(mask, i)$来表示已经经过了mask表示的状态数之后，最后到i点的最短路径。由于比较复杂，具体步骤会在下面作详细介绍。
  6. 到这里，我们就可以使用$min{\ f(mask_final, i)+s(i, T)\ }$来表示最终的结果。

压缩状态的dp

这里我们使用mask中各个位的状态来表示各个点是否已经到达，如5(1001)，我们到达了4号点与一号点。这里记M点的个数为mumM，那么$mask=1<<j$表示最终的状态。
最初状态即$f(1<<i, i) = s(S, i)$。
状态转移方程为：
$$
f( mask| 1<<i, i ) = min{ f(mask, j)+s(j, i) }
$$

最后，我们选择$min{\ f(mask_final, i)+s(i, T)\ }$，其中$mask_final=1<<numM$。

题解代码

代码如下，使用java，附带必要的注释。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
class Solution {
    int m, n;

    /*
     * 第一步，先进行初始化，拿到S，T，M，O的位置 
     * 第二步，判断边界条件，即M==0的情况，退化成S to T 
     * 第三步，计算S 到
     * O，O到M，M到O以及M到T的距离 
     * 第四步，合并S到M，M到M'以及M到T，消除O的中间状态 
     * 第五步，退化到最短路径问题
     */
    public int minimalSteps(String[] maze) {
        // step 1. to calculate s-> o for all o in the map.
        // also, o -> m, m->o, m->t
        // step 2. to obtain s->o->m, m->o->m' and m->t
        // step 3. use the shorest path al.

        if (maze.length == 0 || maze[0].length() == 0) {
            return 0;
        }
        m = maze.length;
        n = maze[0].length();

        var ms = new ArrayList<int[]>();
        var os = new ArrayList<int[]>();
        int[] s = new int[] { -1, -1 }, t = new int[] { -1, -1 };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char item = maze[i].charAt(j);
                if (item == 'S') {
                    s[0] = i;
                    s[1] = j;
                } else if (item == 'T') {
                    t[0] = i;
                    t[1] = j;
                } else if (item == 'M') {
                    ms.add(new int[] { i, j });
                } else if (item == 'O') {
                    os.add(new int[] { i, j });
                }
            }
        }
        int numM = ms.size();
        int numO = os.size();
        // calculate s->t for the corner case where numM==0;
        var ends = bfs(t[0], t[1], maze);
        if (numM == 0) {
            return ends[s[0]][s[1]];
        }

        int[][] dist = new int[numM][numM + 2];
        for (int i = 0; i < dist.length; i++) {
            Arrays.fill(dist[i], -1);
        }
        // before finding dist we need to obtain the mean state
        int[][][] temps = new int[numO][][];
        for (int i = 0; i < temps.length; i++) {
            var o = os.get(i);
            temps[i] = bfs(o[0], o[1], maze);
        }

        for (int i = 0; i < numM; i++) {
            var m1 = ms.get(i);
            // 1. m->s
            dist[i][numM] = getMinPathLen(m1, s, temps);
            // 2. m->t 不需要过O
            dist[i][numM + 1] = ends[m1[0]][m1[1]];
            // 3. m->m'
            for (int j = 0; j < numM; j++) {
                dist[i][j] = getMinPathLen(m1, ms.get(j), temps);
            }
        }
        // when the target is unreachable
        for (int[] d : dist) {
            if (d[numM] == -1 || d[numM + 1] == -1) {
                return -1;
            }
        }

        int[][] dp = new int[1 << numM][numM];
        for (int i = 0; i < 1 << numM; i++) {
            Arrays.fill(dp[i], -1);
        }
        // init s->m
        for (int i = 0; i < numM; i++) {
            dp[1 << i][i] = dist[i][numM];
        }

        for (int mask = 1; mask < (1 << numM); mask++) {
            for (int i = 0; i < numM; i++) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < numM; j++) {
                        if ((mask & (1 << j)) == 0) {
                            int next = mask | (1 << j);
                            if (dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dist[i][j]) {
                                dp[next][j] = dp[mask][i] + dist[i][j];
                            }
                        }
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        int mask = (1<<numM)-1;
        for (int i = 0; i < numM;i++) {
            if(res> dp[mask][i]+dist[i][numM+1]){
                res = dp[mask][i]+dist[i][numM+1];
            }
        }

        return res;
    }

    private int getMinPathLen(int[] s, int[] t, int[][][] temps) {
        int res = Integer.MAX_VALUE;
        for (int[][] dp : temps) {
            int tt = dp[s[0]][s[1]] + dp[t[0]][t[1]];
            if (tt>=0&& res > tt) {
                res = tt;
            }
        }
        return res==Integer.MAX_VALUE?-1:res;
    }

    private int[][] bfs(int i, int j, String[] maze) {
        int[][] res = new int[m][n];
        for (int k = 0; k < res.length; k++) {
            Arrays.fill(res[k], -1);
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { i, j });
        res[i][j] = 0;
        while (!queue.isEmpty()) {
            var item = queue.poll();
            for (int[] offset : state) {
                var x1 = item[0] + offset[0];
                var y1 = item[1] + offset[1];
                if (inBound(x1, y1) && maze[x1].charAt(y1) != '#' && res[x1][y1] == -1) {
                    queue.offer(new int[] { x1, y1 });
                    res[x1][y1] = res[item[0]][item[1]] + 1;
                }
            }
        }
        return res;

    }

    private int[][] state = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    private boolean inBound(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}
java
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！