2024年1月24日发(作者：)

记忆化搜索搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用，在信息学中有着重要的作用。用一个公式简单地说：记忆化搜索=搜索的形式+动态规划的思想。1.记忆化搜索的思想记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量2、记忆化搜索的适用范围根据记忆化搜索的思想，它是解决重复计算，而不是重复生成，也就是说，这些搜索必须是在搜索扩展路径的过程中分步计算的题目，也就是“搜索答案与路径相关”的题目，而不能是搜索一个路径之后才能进行计算的题目，必须要分步计算，并且搜索过程中，一个搜索结果必须可以建立在同类型问题的结果上，也就是类似于动态规划解决的那种。也就是说，他的问题表达，不是单纯生成一个走步方案，而是生成一个走步方案的代价等，而且每走一步，在搜索树/图中生成一个新状态，都可以精确计算出到此为止的费用，也就是，可以分步计算，这样才可以套用已经得到的答案3、记忆化搜索的核心实现a.首先，要通过一个表记录已经存储下的搜索结果，一般用哈希表实现b.状态表示，由于是要用哈希表实现，所以状态最好可以用数字表示，常用的方法是把一个状态连写成一个p进制数字，然后把这个数字对应的十进制数字作为状态c.在每一状态搜索的开始，高效的使用哈希表搜索这个状态是否出现过，如果已经做过，直接调用答案，回溯d.如果没有，则按正常方法搜索4、记忆化搜索是类似于动态规划的，不同的是，它是倒做的“递归式动态规划”实例Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必需向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度，下面是一个例子：12343

98767一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的不滑坡为14－13－12－11－10－9－8－7－6（从14开始，在6结束）。在一个二维地图中，数值代表此处山的高度，在某个点只能滑向上下左右4个相邻的点，最远的滑行路线，也就等价于找出一条最长的数值下降路线。比如下图中的红色路线就是此时最长的一条路线，长度为10。那要如何找出这样的一条路线呢？分析：在每个点上，只能向周围4个方向滑行，当然前提是此处的高度必须比周围高。

我们当然可以选择尽可能高的位置出发，比如图中17比15要高。但这种有可能会陷入局部最优解，比如从下图中的15开始，最大长度为2。而从13开始会更优，长度为5。所以启示我们，不能简单的贪心，而是要考虑全局最优，因为每一个起点都有可能是最优的起点。那就有了初步的框架了，从每一个起点出发，把可行的路线都找出来，也就是能走的路线都走一遍，再比较全局最优的就行了，而且这也正好符合深搜的算法框架。伪代码

intfind(inti,intj){//向4个方向尝试for(i=0->3){if(ok){returnfind(next)+1}}}intmain(){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即可，就避免了重复计算。代码实现：

路线搜索intfind(vector>&snowMountain,vector>&f,inti,intj,intr,intc){intx,y;if(f[i][j]!=-1)returnf[i][j];f[i][j]=1;for(intk=0;k<4;k++){x=i+direction[k][0];y=j+direction[k][1];//validdirectionif(x>=0&&x=0&&ysnowMountain[x][y]){f[i][j]=maxOfTwo(f[i][j],find(snowMountain,f,x,y,r,c)+1);}}returnf[i][j];}intmain(){ios::sync_with_stdio(false);(0);freopen("","r",stdin);freopen("","w",stdout);inti,j,r,c,maxHeight=0;cin>>r>>c;vector>snowMountain(r,vector(c,0));vector>f(r,vector(c,-1));for(i=0;i>snowMountain[i][j];for(i=0;i

总结：记忆化搜索是一种非常实用的算法，因为深搜用递归很容易实现，记忆化又避免了重复子问题的计算，提高了运行效率。这其实就是动态规划的思想，常见的动态规划用递推实现，相比记忆化搜索实现上会更难一点，而记忆化搜索就没有这个问题。算法的适用场景也需要根据具体的问题来分析，一般常用在地图或者树型结构中。