浅谈记忆化搜索算法
浅谈记忆化搜索算法
本篇随笔简单讲解一下算法竞赛中搜索算法的“记忆化搜索”部分。
来看一道例题：
洛谷 P1434 [SHOI2002]滑雪
题目描述
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 2424－1717－1616－11（从 2424 开始，在 11 结束）。当然 2525－2424－2323－\ldots…－33－22－11 更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 RR 和列数 CC。下面是 RR 行，每行有 CC 个数，代表高度(两个数字之间用 11 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
记忆化搜索的概念
以本蒟蒻的理解，记忆化搜索是剪枝的一种方式。
先来上记忆化的概念：
在一些问题中，我们的一些点的答案需要另一些点来统计出来，比如：
1号点答案需要2，3，4，5来统计。
6号点答案需要2，3，4，5来统计。
7号点答案需要2，3，4，5来统计。
8号点答案需要2，3，4，5来统计。
我们发现，1、6、7、8都需要2、3、4、5来得到，这个时候如果我们搜索的时候，每次都重新求一遍2、3、4、5，肯定是一种傻*行为，所以我们就把这些点的结果保存下来，然后在用的时候直接拿出来就可以了。这就是“记忆化”的概念。
所以我说这是一种剪枝，我们可以将其理解成标记：如果已经搜过就不再重复搜。当题目中每个点不是简单地表示“到达”或“不到达”，而是附加了一个答案的话，那么就是存储答案直接用。原理是大同小异的。
记忆化搜索的实现
记忆化搜索的实现非常简单，就是把搜索的答案记下来，然后以后搜索需要重复搜的时候直接调用累加就好。
拿例题举例：
现在我们要统计一个点\((3,3)\)的最大距离，根据题意，我们应该在上下左右四个方向找可行的继续向下搜索。那么假如我们已经搜过了\((3,2)\)，并且已经将其的结果保存下来了，那么在\((3,3)\)向左搜索到\((3,2)\)时，就直接返回\((3,2)\)的答案就OK。
很简单吧？
附上例题的记忆化搜索代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=110;
int n,m,ans;
int map[maxn][maxn];
int f[maxn][maxn];
int dx[]={0,0,0,-1,1};
int dy[]={0,1,-1,0,0};
int dfs(int x,int y)
{
if(f[x][y])
return f[x][y];
f[x][y]=1;
for(int i=1;i<=4;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1 || xx>n || yy<1 || yy>m || map[xx][yy]>=map[x][y])
continue;
dfs(xx,yy);
f[x][y]=max(f[x][y],f[xx][yy]+1);
}
return f[x][y];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,dfs(i,j));
printf("%d",ans);
return 0;
}