记忆化搜索(例)
2018-07-17 03:56:24来源:博客园 阅读 ()
前言:记忆化搜索是在递归的基础上进行优化,这种方法综合了搜索和动态规划两方面的优点。
记忆化搜索的思想是:在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量。
实现方式
①定义好一个数组,用来存储递归所求出来的值,以便接下来进行访问;
②在主程序里,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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 二叉搜索树_BST 2020-05-30
- C语言实现经典游戏——扫雷! 2020-04-17
- 线段树学习资料 2020-03-19
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
- 二叉搜索树3 2020-02-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash