啥是记忆化搜索？

作者：在线问答5 | 2024-08-18 19:09:10

踩

记忆化搜索

关注下方公众号，分享硬核知识

作者 | 小K

出品 | 公众号：小K算法（ID：xiaok365）

故事起源

有一天小K去滑雪，雪山高低不平，当然小K只能从高的地方向低的地方滑，那如何选择路线才能滑的最远呢？

把这个问题抽象描述如下：
在一个二维地图中，数值代表此处山的高度，在某个点只能滑向上下左右4个相邻的点，最远的滑行路线，也就等价于找出一条最长的数值下降路线。
比如下图中的红色路线就是此时最长的一条路线，长度为10。那要如何找出这样的一条路线呢？

分析

在每个点上，只能向周围4个方向滑行，当然前提是此处的高度必须比周围高。

我们当然可以选择尽可能高的位置出发，比如图中17比15要高。

但这种有可能会陷入局部最优解，比如从下图中的15开始，最大长度为2。而从13开始会更优，长度为5。

所以启示我们，不能简单的贪心，而是要考虑全局最优，因为每一个起点都有可能是最优的起点。
那就有了初步的框架了，从每一个起点出发，把可行的路线都找出来，也就是能走的路线都走一遍，再比较全局最优的就行了，而且这也正好符合深搜的算法框架。

伪代码


int find(int i,int j){
  // 向4个方向尝试
  for (i=0->3){
    if (ok){
      return find(next)+1
    }
  }
}
int main(){
  for (i=0->n) {
    for (j=0->m) {
      t=find(i,j)
      ans=max(ans,t)
    }
  }
}

问题

上面的做法可以得到最优解，但有一个问题。如下例，以15为起点的时候，会尝试把6->5->4->3->2->1走一遍。但以16为起点的时候，还会尝试把这条路线走一遍，这就会导致大量的重复计算。

那能不能优化呢？
之所以重复计算，是因为每一次尝试都是重新的开始，它并不知道这条路已经走过了，也就是没有记忆，所以我们引入一种优化的方法，就是记忆化搜索。

记忆化搜索

可以引入一个f[i][j]数组，记录以(i,j)为起点所能找到的最长路线的长度，初始赋值为-1，表示还没有走过。

当走过一点，就将对应的f[i][j]更新为以(i,j)为起点的最大长度。
再回到上面的问题，因为之前肯定走过了(2,3)，对应的f[2][3]为6，当尝试从(2,4)出发时，会发现周围已经走过了，只需要更新当前的值+1即可，就避免了重复计算。

代码实现

路线搜索


int find(vector<vector<int>> &snowMountain, vector<vector<int>> &f, int i, int j, int r, int c) {
    int x, y;
    if (f[i][j] != -1)
        return f[i][j];
    f[i][j] = 1;
    for (int k = 0; k < 4; k++) {
        x = i + direction[k][0];
        y = j + direction[k][1];
        //valid direction
        if (x >= 0 && x < r && y >= 0 && y < c && snowMountain[i][j] > snowMountain[x][y]) {
            f[i][j] = maxOfTwo(f[i][j], find(snowMountain, f, x, y, r, c) + 1);
        }
    }
    return f[i][j];
}

main函数


int main() {
    ifstream fin("a.in");
    ofstream fout("a.out");
    int i, j, r, c, maxHeight = 0;
    fin >> r >> c;
    vector<vector<int>> snowMountain(r, vector<int>(c, 0));
    vector<vector<int>> f(r, vector<int>(c, -1));
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            fin >> snowMountain[i][j];
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++) {
            maxHeight = maxOfTwo(maxHeight, find(snowMountain, f, i, j, r, c));
        }
    fout << maxHeight << endl;
    fin.close();
    fout.close();
    return 0;
}