下载

2下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 高二下期4月16日记忆化搜索

高二下期4月16日记忆化搜索.doc

高二下期4月16日记忆化搜索

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《高二下期4月16日记忆化搜索doc》,可适用于工程科技领域

JSOI集训队论文浅谈记忆化搜索浅谈记忆化搜索江苏省常州高级中学吴景岳【摘要】搜索和动态规划是信息学中的两大重要算法。它们各有自己的优点和缺点。针对它们的优缺点一个新的算法“记忆化搜索”产生了。它采用了搜索的形式与动态规划的思想扬长避短在解决某些题目时有非常出色的表现。它在信息学竞赛中也有举足轻重的地位NOI的cannon与NOI的dragon都使用到了这个算法。这篇论文着重分析了搜索、动态规划和记忆化搜索之间的联系和区别以及各自的优缺点并通过几个例子使得大家对记忆化搜索有一个初步的了解。【关键字】重叠子问题拓扑关系形式思想【目录】、搜索.搜索树.例子words.效率低下的原因重叠子问题、动态规划.基本原理最优子结构、无后效性.拓扑关系(例子最长路径)、记忆化搜索.记忆化搜索=搜索的形式动态规划的思想.记忆化深度优先搜索()程序框架()例子words.记忆化宽度优先搜索()程序框架()例子cannon.缺点分析、总结【正文】、搜索.搜索树一道搜索题目拿到手我们往往要弄清楚这样一些问题:以什么作为状态?这些状态之间又有什么样的关系?其实在这样的思考过程中我们已经不知不觉地将一个具体的问题抽象成了一个图论的模型树。状态对应着顶点状态之间的关系(或者说从一个状态到另一个状态的形成过程)对应着边。这样的一棵树就叫做搜索树。初始状态对应着根结点目标状态对应着目标结点。我们的任务就是找到一条从根结点到目标结点的路径一个成功的解。.例子words问题描述Io和Ao在玩一个单词游戏。他们轮流说出一个仅包含元音字母的单词并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。游戏可以从任何一个单词开始。任何单词禁止说两遍游戏中只能使用给定词典中含有的单词。游戏的复杂度定义为游戏中所使用的单词的长度总和。编写程序求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。数据规模限制:单词总数不超过单词长度不超过。算法分析这是省集训队冬令营的一道题目当时大多数同学都用了搜索。让我们看看他们是如何搜索的。状态:现在说到哪一个单词已经说过的单词集合我们将状态表示为(I,S)表示说到了单词I已经说过的单词集合为S。状态之间的关系:(I,S)>(j,S)(S=Sj)的条件为单词J不在集合S中并且单词J可以接在单词I后面。但是这样搜索效率是不会高的。所以当时很多人都是因为超时最后三个点没有出来。那么搜索效率低下的根本原因是什么呢?.重叠子问题在一些复杂的搜索问题中搜索树是极其庞大的结点数量非常多结点之间的关系也非常复杂这是导致搜索算法效率低下的重要原因。其实在有的情况下状态的总数并没有多少有可能很多结点表示的都是同一个状态我们把这样的状态叫做“重叠子问题”。由于搜索算法本身性质的制约它不能把这些重叠子问题记录下来只能不知疲倦地继续访问下去不断遇到这些讨厌的重叠子问题。显然如果能不把时间放在处理重叠子问题上算法的效率将发生一个质的飞跃。那么有没有这样一种可以避免重复地处理重叠子问题的算法呢?这就是、动态规划.基本原理动态规划是大家极为熟悉的一种算法实际上一道动态规划的问题也可以转化为求解搜索树的问题。同样是搜索树动态规划却比搜索算法高效很多这是因为它把每个状态的最优值都记录了下来于是成功地避免了重复地处理重叠子问题。不过动态规划的使用是要满足两个基本条件的:·最优子结构用动态规划解决一个问题的第一步是刻划一个最优解的结构。如果一个问题的最优解中包含了子问题的最优解我们就说这个问题具有最优子结构。·无后效性动态规划的过程是一个状态转移的过程:不断地从一个已知的状态出发推出一个新的状态。但是如果新的状态又能够推出前面的状态(影响前面的状态)那么这样的状态划分就具有了后效性。动态规划能够成功的一个必要条件就是无后效性。.拓扑关系我们同样地对动态规划问题进行抽象:状态>结点状态之间的关系>边。这样一个动态规划的问题就可以抽象成为一个图。因为动态规划是满足无后效性的这样的图必将是一个有向无环图。在动态规划中状态之间有着严格的递推关系我们必须确定哪些状态必须先推出哪些应当后推出。这就称为拓扑关系。将点(状态)按照拓扑关系排序就叫做拓扑排序。拓扑排序保证:除初始状态以外每个状态都可以由它前面的状态推出。举一个例子:下图是一个有向无环图求从顶点到顶点的最长路径。(规定边的方向从左到右)我们将从起点(顶点)开始到某个顶点的最长路径作为状态用一维数组opt记录。显然opt=这是初始状态即动态规划的边界条件。于是我们很容易地写出状态转移方程式:optj=max{optkak,j}(k到j有一条长度为ak,j的边)。虽然有了完整的状态转移方程式但是我们还不知道动态规划的顺序。所以我们还需要先进行一下拓扑排序按照排序的顺序推下去opt就是问题的解。可以看出动态规划相比搜索之所以高效是因为它将所有的状态都保存了下来。当遇到重复子问题时它就不会像搜索那样把这个状态的最优值再算一遍只要把那个状态的最优值调出来就可以了。例如当计算opt和opt的时候我们都用到了opt的值。因为我们将它保存下来了所以就没有必要再去搜索了。但是动态规划仍然是有缺点的。一个很突出的缺点就是要进行拓扑排序。这道题的拓扑关系是很简单的但有些题的拓扑关系是很复杂的。对于这些题目如果也进行拓扑排序工作量巨大。遇到这种情况我们又该怎么办呢?、记忆化搜索.概念讲了那么多有关搜索和动态规划的东西终于进入正题了记忆化搜索。什么是记忆化搜索呢?前面我们分析了搜索和动态规划各自的优缺点:搜索的低效在于没有能够很好地处理重叠子问题动态规划虽然比较好地处理了重叠子问题但是在有些拓扑关系比较复杂的题目面前又显得无奈。记忆化搜索正是在这样的情况下产生的它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起扬长避短简单实用在信息学中有着重要的作用。用一个公式简单地说:记忆化搜索=搜索的形式动态规划的思想。既然它具有搜索的形式那么我们也按照讨论搜索算法的方式讨论这个新事物:.记忆化深度优先搜索()程序框架constnonsense={这个值可以随意定义表示一个状态的最优值未知}var……{全局变量定义}functionwork(s:statetype):longintvar……{局部变量定义}beginifopts<>nonsensethenbeginwork:=optsexitend{如果状态s的最优值已经知道直接返回这个值}枚举所有可以推出状态S的状态Sbegintemp:=由S推出的S的最优值{有关work(s)的函数}if(opts=nonsense)or(temp优于opts)thenopts:=tempendwork:=opts{用动态规划的思想推出状态s的最优值}end记忆化深度优先搜索采用了一般的深度优先搜索的递归结构但是在搜索到一个未知的状态时它总把它记录下来为以后的搜索节省了大量的时间。可见记忆化搜索的实质是动态规划效率也和动态规划接近形式是搜索简单易行也不需要进行什么拓扑排序了。()例子words我们继续讨论这个老题目words(问题描述见)不过这次我们不再讨论如何搜索了而是讨论如何记忆化搜索。先回顾一下状态和状态之间的关系:状态:到某一时刻为止的最后一个单词已经说过的单词集合我们将状态表示为(I,S)表示说到了单词I已经说过的单词集合为S。状态之间的关系:(I,S)>(j,S)的条件为单词J不在集合S中并且单词J可以接在单词I后面(S=Sj)。按照这样的状态表示方法状态总数最多为^。在FreePascal下是完全可以存得下的。经过这样的划分状态转移方程式显而易见:optj,s=max{optI,slengthj}单词J不在集合S中并且单词J可以接在单词I后面(S=Sj)。初始条件:optI,{I}=lengthI不过值得注意的是集合的表示方法:将一个集合与一个二进制数对应再将二进制数与十进制数对应。为了方便操作单词的编号也可以从…N改成…N。比如:集合>集合>()>^^^=。这样操作不但节省了空间而且在进行集合操作时可以用位操作又节省了时间。我们再来考虑算法的实现如果用一般的动态规划就需要先进行拓扑排序很显然这样做是不可取的因为状态之间的关系十分复杂。于是我们将目光投向了记忆化搜索。记忆化搜索是不需要拓扑排序的这正好避免了我们的问题复杂的拓扑关系。按照推导出的状态转移方程式和前面展示的框架相信大家都可以轻松地写出源程序了。(源程序见附录)在这个解法中虽然我们想到了如何表示状态以及状态之间的关系但是如果没有记忆化搜索的参与我们对于如此复杂的拓扑关系仍是无所适从。所以记忆化搜索的参与可以使得这类具有复杂拓扑关系的动态规划问题得到了较为圆满的解决。.记忆化宽度优先搜索()程序框架记忆化宽度优先搜索实际上是把一般的动态规划倒过来了。动态规划在计算每一个状态的最优值时总是寻找可以推出该状态的已知状态然后从中选择一个最优的决策。而记忆化宽度优先搜索是不断地从已知状态出发看看能推出哪些其它的状态并修改其它状态的最优值。这个算法有两大优点:·与记忆化深度优先搜索相似避免了对错综复杂的拓扑关系的分析·化倒推为顺推更加符合人类的思维过程而且在顺推比倒推简单时可以使问题简单化下面我们通过一个例子具体问题具体分析。()例子cannon问题描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成地图的每一格可能是山地(用“H”表示)也可能是平原(用“P”表示)如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队)一支炮兵部队在地图上的攻击范围如图中黑色区域所示:PPHPHHPPPHPHPHPPPPPHHHPHHPHPPPPHHPPPPHPHHPPHPHHPHHHPPPPH如果在地图中的灰色所标识的平原上部署一支炮兵部队则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。现在将军们规划如何部署炮兵部队在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内)在整个地图区域内最多能够摆放多少我军的炮兵部队。数据限制:N<=M<=算法分析这一题目若用图论的模型来做就是一个最大独立集问题而最大独立集问题确实一个NP问题。并且我们也做过这种题目的原型题目大部分都必须通过搜索来解决。故我们需要考察这个问题的特殊性。由数据限制可知mmax<<nmax。注意这是唯一一个与原型题目不同的地方。可是如何使用呢?我们先考虑一种极端情况例如m=的情况。这个时候我们可以用如下的动态规划方程来解出结果:其中ci的含义是在前i行各自中可以放置的最多炮兵数cn即为解答。这种方法是否可以扩展到m列呢?我们这时用ci表示m列时在前i行格子中可以放置的最多炮兵数。然后把每一行可能放置炮兵的方法求出来然后就可以只考虑行与行之间放置炮兵的关系了。不过这样我们还是无法写出规划方程。观察这个时候情况与m=式情况的不同:就是对于每以列我们多需要保存各自的ci和ci。有鉴于此我们需要增设一个参数p来满足动态规划的需要。这里p应是一个m位的数组并且每一位都有三种选择第k列的三种选择分别代表该列取ci、ci、ci时所对应的最值。这样我们有:最后的答案就是。我们虽然写出了状态转移方程式但是如果用这样的方程式进行动态规划实现起来是非常烦琐的尤其涉及到了参数p的倒推颇为复杂。于是我们又将目光投向了记忆化搜索化倒推为顺推。把算法进行一些修改:c,p为边界状态以阵地的行作为阶段进行搜索从cI,p推出所有cI,p再从cI,p推出cI,p……直到cn,p。这样使用记忆化搜索使得问题得到了圆满的解决!(源程序见附录)小结一下:首先在“m<=”的启发下找到了动态规划的算法这是主要的一个步骤其次我们选择了记忆化搜索使得算法的实现变得容易了许多这也是不可或缺的一步。总而言之记忆化宽度优先搜索将宽度优先搜索的结构和动态规划的思想有机地结合在一起为我们的解题提供了一个新的途径。.缺点分析以上所说的几乎都是记忆化搜索的优势但是我们也无法忽略记忆化搜索的缺点。因为记忆化搜索利用的是搜索算法的结构尤其是记忆化深度优先搜索用了递归的过程导致算法时间复杂度的系数较大。我写了两个计算斐波那契数列第项的程序。第一个用的是一般的递推(也可以看作是一般的动态规划)另外一个是用的记忆化搜索。由于两个程序的运行时间都很短我们将他们运行遍发现两个程序的运行时间有明显的差别。在PentiumIIIMHz的机器上第一个程序用时sec而第二个程序用时sec。这两个算法应该具有相同的时间复杂度(O(n))但是由于记忆化搜索算法的系数较大导致第二个程序比第一个慢了一个常数倍。这看上去影响不大但是现在竞赛的时限越来越苛刻我们也应当小心谨慎即在可以比较简单的写出一般的动态规划程序的时候不要乱用记忆化搜索。、总结“记忆化搜索=搜索的形式动态规划的思想”这个公式确切地反映了记忆化搜索的实质。既具有动态规划的高效性也具有搜索算法的易实现性是它的优点效率有所降低(比递推式的动态规划慢一个常数倍)是它的缺点。总体来说记忆化搜索仍然是利大于弊的。我们要从正反两方面认识它以便扬长避短充分应用。有的人把它看作搜索的一种优化或者动态规划的一种实现方法这种说法未尝不可但是既然它有着自己的独特结构那么不妨把它看作一种新的算法。其实就这个算法本身而言也是值得我们思考的。近几年来信息学奥赛题的难度不断增加这里的难度主要是指算法的不确定性不稳定性和综合性也就是说一道题目的解法可能并不是我们通常碰到的经典算法而是从来没有见过的新的算法。这就要求选手们创造性地去应答没有遇到过的挑战。在提出记忆化搜索之前我们首先对两种经典算法进行了深刻的分析然后在加以综合。由此可见记忆化搜索是搜索和动态规划两种经典算法的结合物是创造性思维的典范。掌握了记忆化搜索不但可以解决一类题目而且可以学会解决问题的一种方法分析综合。【参考资料】《实用算法的分析与程序设计》电子工业出版社编著:吴文虎王建德《IntroductiontoAlgorithms》TheMITPress编著:ThomasHCormenCharlesELeisersonRonaldLRivestCliffordStein附录:programWordsconstmaxn=pow:arrayoflongint=(,,,,,,,,,,,,,,,,){的次幂}maxtotal=varw:arraymaxnofstring{单词}a:arraymaxn,maxnofboolean{单词之间的关系}c:arraymaxn,maxtotaloflongint{最优值}len:arraymaxnoflongint{单词长度}n,i,j,ans,temp,total:longintfunctionwork(i,j:longint):longint{计算(单词I集合J)状态的最优值}varj,k,temp:longintbeginifci,j>thenbeginwork:=ci,jexitendj:=jpowifork:=tondoifak,iand(powkandj<>)thenbegintemp:=work(k,j)leniiftemp>ci,jthenci,j:=tempendwork:=ci,jendbeginassign(input,'wordsin')assign(output,'wordsout')reset(input)readln(n)fori:=tondobeginreadln(wi)leni:=length(wi)endclose(input){读入数据}fillchar(a,sizeof(a),)fori:=tondoforj:=tondoif(i<>j)and(wi,leni=wj,)thenai,j:=true{建立单词间的关系}total:=pownfillchar(c,sizeof(c),)fori:=tondoci,powi:=leni{初始条件只有一个单词的情况}ans:=fori:=tondoforj:=tototaldoif(powiandj)<>thenbegin{搜索每一个可能的状态}temp:=work(i,j)iftemp>ansthenans:=tempendrewrite(output)writeln(ans)close(output){输出结果}end附录:{NOIDayTaskCannonByWuJingyue}programcannonconstmaxm=maxn=pow:arrayoflongint=(,,,,,,,,,,){的次幂}maxtotal=typestatetype=arraymaxnoflongint{状态类型}vara:arraymaxm,maxnofboolean{地图}c,c:arraymaxtotaloflongint{最优值}t:arraymaxnofboolean{搜索堆栈}state,state:statetypem,n,i,j,total,s,ans:longintch:charprocedurenumtoarr(k:longintvara:statetype){将一个十进制的数转化为三进制的数}varj:longintbeginforj:=tondoaj:=(kdivpowj)modendprocedurearrtonum(a:statetypevark:longint){将一个三进制的数转化为一个十进制的数}varj:longintbegink:=forj:=tondoinc(k,aj*powj)endproceduresearch(top,now:longint){对每一层的炮兵的放法进行搜索}varj,j,temp:longintbeginiftop>nthenbeginforj:=tondoiftjthenstatej:=elseifstatej=thenstatej:=elsestatej:=statejarrtonum(state,j)temp:=cinowiftemp>cjthencj:=tempexitendttop:=falsesearch(top,now)ifas,topand(statetop=)thenbeginttop:=trueiftop<=nthenttop:=falseiftop<=nthenttop:=falsesearch(top,now)endendbeginassign(input,'cannonin')assign(output,'cannonout')reset(input)readln(m,n)fori:=tomdobeginforj:=tondobeginread(ch)ifch='H'thenai,j:=falseelseai,j:=trueendreadlnendclose(input){读入数据}total:=pownforj:=tototaldocj:=c:={初始条件}fors:=tomdobegin{按行记忆化搜索}fori:=tototaldoci:=fori:=tototaldoifci<>thenbegin{状态可达}numtoarr(i,state)search(,)endc:=cendans:=forj:=tototaldoifcj>ansthenans:=cj{最优值}rewrite(output)writeln(ans)close(output){输出结果}end根结点目标结点一个成功的解边界条件进入队列找到一个没有扩展过的且肯定最优的状态没有则退出扩展该状态并修改扩展到的状态的最优值回第二步第页共页unknownunknownunknown

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/13

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利