记忆化搜索(例)

2018-07-17 03:56:24来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

前言:记忆化搜索是在递归的基础上进行优化,这种方法综合了搜索和动态规划两方面的优点。

记忆化搜索的思想是:在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量

实现方式

①定义好一个数组,用来存储递归所求出来的值,以便接下来进行访问;

②在主程序里,memset一下,一般都是赋初值为-1,然后把这个数组的边界值设置好;

③在递归函数里,首先加一句:if (这个数组的值>=0) return 这个值【如果赋初值为-1的话,一般都是>=0】;其次,在后面的递归调用中,先给这个数组赋值,再return。

代码加持

int f[1000]
int count(int n)
{
if(f[n]) 
return f[n];//调取结果 if(n==1)
return 1;//边界 int val=0; for(int i=1;i<=n/2;++i) val+=count(i); f[n]=val+1;//存取结果 return f[n]; } //val是变量

记忆化搜索的适用范围

    根据记忆化搜索的思想,它是解决重复计算,而不是重复生成,也就是说,这些搜索必须是在搜索扩展路径的过程中分步计算的题目,也就是“搜索答案与路径相关”的题目,而不能是搜索一个路径之后才能进行计算的题目,必须要分步计算,并且搜索过程中,一个搜索结果必须可以建立在同类型问题的结果上,也就是类似于动态规划解决的那种。

也就是说,他的问题表达,不是单纯生成一个走步方案,而是生成一个走步方案的代价等,而且每走一步,在搜索树/图中生成一个新状态,都可以精确计算出到此为止的费用,也就是,可以分步计算,这样才可以套用已经得到的答案.

 号 外 号 外并不是所有算法都适用哦!

使用条件

  • 对于一定状态有唯一相同的解,不应对于一个状态有多个解(解不相同);
  • 到达底层时可立即返回解,不应得出路径后才能计算解;
  • 状态数量和规模应能够在有限数据结构中存储。

TIP

  • 遵循无后效性原则//某阶段的状态一旦确定,则此后过程的演变不再受此前各种状态及决策的影响。
  • 局限性:可十分简洁的优化为递归,即动态规划。
  • 往往对于dfs才会使用记忆化,因为bfs并不会重复搜索到某一个状态,而一旦搜索到结果就是最优解,此时立即退出;

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:CBCGPImage的GetSize的问题及解决方法

下一篇:P3366 最小生成树【模板+Kruscal讲解】