记忆化搜索(例)

作者: 日期:2019-10-08

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

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

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

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

③在递归函数里,首先加一句:if  return 这个值;其次,在后面的递归调用中,先给这个数组赋值,再return。

代码加持

int f[1000]
int count
if 
return f[n];//调取结果 if
return 1;//边界 int val=0; for val+=count; f[n]=val+1;//存取结果 return f[n]; //val是变量


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

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

 

首页
电话
短信
联系