关于记忆化搜索

关于记忆化搜索转载自:http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5847876记忆化搜索: 算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

转载自:http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5847876

记忆化搜索

 

算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。

一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。

更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多。

记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来,以后再次遇到这个状态的时候,就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点,因而还是很有实用价值的。上传/更换附件动态规划的另一种实现形式——记忆化搜索的应用。

 

动态规划和记忆化搜索:

 

动态规划:就是一个最优化问题,先将问题分解为子问题,并且对于这些分解的子问题自身就是最优的才能在这个基础上得出我们要解决的问题的最优方案,要不然的话就能找到一个更优的解来替代这个解,得出新的最优自问题,这当然是和前提是矛盾的。动态规划不同于 贪心算法,因为贪心算法是从局部最优来解决问题,而动态规划是全局最优的。用动态规划的时候不可能在子问题还没有得到最优解的情况下就做出决策,而是必须等待子问题得到了最优解之后才对当下的情况做出决策,所以往往动态规划都可以用 一个或多个递归式来描述。而贪心算法却是先做出一个决策,然后在去解决子问题。这就是贪心和动态规划的不同。

一般遇到一个动态规划类型的问题,都先要确定最优子结构,还有重叠子问题,这两个是动态规划最大的特征,然后就是要写 动态规划的状态方程,这个步骤十分十分的重要的,写动归方程是需要一定的经验的,这可以通过训练来达到目的。接着就是要自底向上的求解问题的,先将最小规模的子问题的最优解求出,一般都用一张表来记录下求得的解,到后来遇到同样的子问题的时候就可以直接查表得到答案,最后就是通过一步一步的迭代得出最后问题的答案了。

我的理解最重要的东西就是一定会要一个数组或者其他的存储结构存储得到的子问题的解。这样就可以省很多时间,也就是典型的空间换时间

动态规划的一种变形就是记忆化搜索,就是根据动归方程写出递归式,然后在函数的开头直接返回以前计算过的结果,当然这样做也需要一个存储结构记下前面计算过的结果,所以又称为记忆化搜索。

 

记忆化搜索/递归式动态规划:

 

1.记忆化搜索的思想

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

2、记忆化搜索的适用范围

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

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

3、记忆化搜索的核心实现

     a. 首先,要通过一个表记录已经存储下的搜索结果,一般用哈希表实现

     b.状态表示,由于是要用哈希表实现,所以状态最好可以用数字表示,常用的方法是把一个状态连写成一个p进制数字,然后把这个数字对应的十进制数字作为状态

    c.在每一状态搜索的开始,高效的使用哈希表搜索这个状态是否出现过,如果已经做过,直接调用答案,回溯

    d.如果没有,则按正常方法搜索

4、记忆化搜索是类似于动态规划的,不同的是,它是倒做的“递归式动态规划”。

 

 

 下面POJ 1691 paint a borad的题目:

 

先用普通的深度优先搜索来解答。

在这道题中需要注意的是:

1、如何记录某个矩形的信息,这里包括了坐标、颜色、是否涂色、上方矩形的个数、下方有哪几个矩形。

这些都是从便于程序设计的角度抽象出来的。

2、为了得到最少使用刷子的次数,涂色策略应该为:把当前可以涂色的矩形全部涂色。

3、还需要注意如何通过坐标判断:紧邻的处于上方的矩形

 


 

通过这道题可以看到dfs搜索算法的特点是这样的:

 

核心的搜索算法一般使用递归的形式,而且递归函数的参数往往直接和问题的求解对象有一定的关联。还有就是,在搜索算法函数的开头一般先放上剪枝条件,这样主要是起到回溯的作用,否则的话,函数就会无限递归了。可以发现对深度搜索进行合适的剪枝可以大大提高搜索的效率。另外,在执行递归之前,一般先对当前的局面状态进行保存,在递归函数返回时,在进行恢复。这有点类似于回溯算法的特点。其实dfs函数的参数表示的就是局面的一种状态。

 

 

下面对于这个问题使用记忆化搜索算法:

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164441.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 猿创征文|点亮JAVA技术之灯(线程篇)「建议收藏」

    猿创征文|点亮JAVA技术之灯(线程篇)「建议收藏」线程安全就是说多线程访问同一段代码,不会产生不确定的结果。又是一个理论的问题,各式各样的答案有很多,我给出一个个人认为解释地最好的:如果你的代码在多线程下执行和在单线程下执行永远都能获得一样的结果,那么你的代码就是线程安全的。(1)不可变像String、Integer、Long这些,都是final类型的类,任何一个线程都改变不了它们的值,要改变除非新创建一个,因此这些不可变对象不需要任何同步手段就可以直接在多线程环境下使用(2)绝对线程安全不管运行时环境如何,调用者都不需要额外的同步措施。……….

    2022年10月22日
  • 秒懂mysql中的group by用法

    秒懂mysql中的group by用法文章转载自:https://blog.csdn.net/u014717572/article/details/80687042先来看下表1,表名为test:执行如下SQL语句:SELECTnameFROMtestGROUPBYname你应该很容易知道运行的结果,没错,就是下表2:可是为了能够更好的理解“groupby”多个列“和”聚合函数“的应用,我建议在思考的过程中…

  • JPA 逻辑删除

    JPA 逻辑删除为了避免每次在查询的时候加上是否删除字段,做了一下封装。@NoRepositoryBean@RepositoryRestResource(exported=false)publicinterfaceBaseRepository<TextendsBaseEntity,IdTextendsLong>extendsJpaRepository<T…

  • python sqrt函数的使用

    python sqrt函数的使用摘自《python程序设计基础》蔡永铭主编工具:python3.764-bit官方链接:https://www.python.org/平台:Windows10sqrt函数的使用sqrt中文名:平方根在python中使用函数之前需要了解一下模块的含义。模块是一个包含所有定义的函数和变量的文件,模块可以被别的程序引入,以使用该模块中的函数等功能。因为sqrt函数在math模块中,所…

  • airtest测试用例_Airtest 常用方法[通俗易懂]

    airtest测试用例_Airtest 常用方法[通俗易懂]几个添加设备参数的例子#方法一:在auto_setup()接口添加设备auto_setup(__file__,devices=[“Android://127.0.0.1:5037/SJE5T17B17”])#方法二:用connect_device()方法连接设备dev=connect_device(“Android://127.0.0.1:5037/SJE5T17B17”)#方法三:用init…

  • steamvr插件怎么用_微信word插件加载失败

    steamvr插件怎么用_微信word插件加载失败本文基于SteamVR插件的开发文档翻译并总结SteamVR开发过程中的基本用法。本文总结汇总了SteamVR插件文档的内容,对文档部分内容进行了删减。目前仅仅只是翻译汇总,部分内容可能存在纰漏,后续会结合开发过程逐步更新修改此文章的内容。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号