动态规划入门讲解

Click to edit the title text format,Click to edit the outline text format,Second Outline Level,Third Outline Level,Fourth Outline Level,Fifth Outline Level,Sixth Outline Level,Seventh Outline Level,Eighth Outline Level,Ninth Outline Level,*,动态规划,入门讲解,by,张惜今,引入,我们用一个简单的例子来让大家了解什么是动态规划,灵梦的灵符,博丽灵梦是东方幻想乡中博丽神社的巫女，她跟幻想乡中最老资格的妖怪八云紫一起维护着隔绝幻想乡与现实世界的大结界，维护现实世界不被幻想乡中的妖怪侵害，幻想乡中的生物也可以自由自在的维持古老的生活方式。,但不幸的是，每隔六十年，结界会有一次大异变，为了维护结界的完整，博丽灵梦必须将灵力注入灵符，让灵力以最好的方式游走来修复结界。,灵梦的灵符是一个三角形，由一堆数字组成，每个数字表示灵力经过这个位置获得的修复值，三角形共,n,层，第,i,层有,i,个数字，从上方的最尖端注入灵力，灵力只能前往前位置的左下方或者右下方，最终走的下面的边的某个位置释放，问灵梦最多可以获得多少修复值？,灵梦的灵符（,USACO 1.5.1,）,最容易想到的方法,：,回溯法,我们可以,列举每一条可能的路线，分别累加比较每条路线的修复值进行比较，取得最大的一条作为答案。我们先不引入时间复杂度的计算，来用一个,n,较小的例子手工计算我们需要做的计算量。,为什么会计算那么多次呢？,因为这个算法有,天然呆,的属性，,多次经过同一个点,，,太健忘了,！,到这个点为止的最大和其实已经算出来了,，,而,回溯法在,每次,回溯时会重复计算,！,这样要计算多少次？,我们先不引入时间复杂度的计算，来用一个,n,较小的例子手工计算我们,需,要做的计算量。,n,4,，共有,2(4-1),8,条路线,每条两次加法和一次比较，共,24,次计算。,但是如果,n=100,呢？,n=1000,呢？指数级的运算量将会飞快增长,无法接受,换一种方法,取当前和较大的一种路线记录下来，往下走的时候直接用这个数跟下面点的修复值相加,。,每一层都看做一个这样的问题，也就是到当前位置可以获得的最大值，依次类推,。,原问题答案：到最下面某个位置（也就是最后一层子问题的当前位置）的最大修复值。,这就是传说中的：,动态规划,这样的计算次数,进行,1,次比较和,1,次加法,（,1+4,）*,4/2-1=9,个点,共计算,18,次,。,虽然只少了,6,次，但,n,增长时与,n2,成正比的计算量就可以接受了。,动态规划的,定义,动态规划,是：,运筹学的一个分支,解决策过程最优化的数学方法,把多阶段过程转化为一系列单阶段问题,动态规划,求解可以划分阶段的最优化问题的方法,效率高,局限性,必须可以划分阶段并满足几个条件,指数级,-,多项式级,动态规划的,适用条件,不是一个纯理论的知识,看出来这个题题是考用动态规划求解,感性的认识,1.,最优子结构,当前取得了最优值,那么直接用这个值来参与计算后面的状态能使后面的也最优,只要比较取一个值最优的保存,2.,无后效性,当前作出决策只会影响后面的状态,前面的决策的影响都在状态中被包含了顺序,3.,重叠子问题,也就是有前所述的那种重复计算的减少,动态规划才能减少算法的运行时间,动态规划的,要素,阶段,状态,决策,阶段,每个状态属于一个阶段有了前后关系保证最优子结构和无后效性比较明显,是前提也是一种特征,比如：时间的前后,，,灵梦的灵符那种层次关系,状态,动态规划时操作的对象,表示我们解到了哪一个子问题,1,维或者多维,所属的阶段，一些相关信息,决策,是前面阶段的状态向后面的状态转移的操作,是决策把各个阶段的状态依次求出,动态规划的,求解模式,和,程序实现,划分阶段,设计状态,确定决策写出转移,写出方程和边界,递推：看作递推方程，用循环依次递推出每一个状态,记忆化搜索：按搜索的方式写，但是对于已经搜索过的状态直接返回最优值，不再次搜索,按照方程的形态大致分类的几个例题,线性选择,背包问题,区间,DP,TreeDP,空的裂解原子核（,POJ1887,）,灵乌路空有着特别姿态的鸦。左足是“分解之足”、右足是“融合之足”、还有制御两者的右手“第三足”，她以这三足操控著究极的能源。,空居住在地灵殿在无聊的时候经常控制原子核进行核裂解来练习自己的能力。她捕捉到了,N,个原子核，控制每个原子核进行裂解会获得,Ci,的能量值，她可以依次挑选一个序列进行裂变（不必连续）,。,但是由于她能力的特殊性，她用来裂解的原子核的能量只能越来越低，否则会导致控制失败而造成核反应制御不能的后果。但是空是一个低智力的笨蛋，她想让你帮忙计算她最多可以控制几个原子核进行裂变。,分析,经典的,LIS,模型，也就是线性选择型的,DP,阶段：按顺序处理到哪一个原子核,状态,:fi,表示处理到第,i,个，且选取第,i,个的最大序列长度,决策：上一个原子核是哪一个（逆推）,方程,fi=max(fj)+1 1=ji f1=1,帕秋莉的图书（,POJ3624,）,帕秋莉诺蕾姬是幻想乡中红魔馆的图书馆管理员，管理着图书馆中,10,万本魔法书。她总是试图整理这些图书，把质量好的放在一个专门的书架上。,这个专用书架承受的最大重量是,M,，总共有,N,本候选图书，编号,1,n,，每本有一个重量和知识值,Wi,和,Ki,，她想知道，在书架不会超过承重的情况下，图书的知识值最大。,分析,阶段：物品随意排列，以做决定到了哪个物品作为阶段,状态：,fij,表示处理到第,i,个物品，已经使用重量,j,得到的最大知识值,决策与转移：决策就是对每个物品是否取用，分别转移，取较大的。,方程：,fij=max(fi-1j,fi-1j-Wi+Ki),1=i=n 0=j=M,后面部分要求,Wi=j f0=0,萃香的的西瓜,伊吹萃香是被赶到幻想乡的鬼，位列鬼族四天王之一，据传为“怪力乱神”四天王中怪的代表。,虽然看上去是一个少女，但其实已活了几百年。她有操纵密和疏的能力，可以任意合并和分解周围的东西。,幻想乡的夏天的一天，萃香得到了,N,堆西瓜，她想把这些西瓜合并成一堆，每次只能合并相邻的两堆，合并的代价为这两堆西瓜的数量之和，合并后与这两堆西瓜相邻的西瓜将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，找出一种合理的方法，使总的代价最小。,分析,阶段：顺序排列的西瓜堆将随着合并逐渐减少从,i,到,j,的长为,j-i+1,的区间可以认为是阶段,状态：,fij,表示从,i,到,j,合并完成后的最小代价,决策和转移：决策就是应该从区间选哪个点分别合并两边（也就是最后一次合并的位置），从,i,到,J-1,选一个位置分开合并,方程：,fij=min(fik+fk+1j+sum(i,k)+sum(k+1,j) i=kj fii=0,美铃的看守方案,(POJ1463),红美铃是一个来自中国的妖精，因为她会一些中国功夫，所以被红魔馆招募做看门人。红魔馆从外面看上去并不是很大，但是由女仆长咲夜控制时间和空间造成的混乱，馆里面空间很大不容易看守。,红魔馆内部的建筑房间和道路可以简化成一棵无根树，也就是有,N,个房间，,N-1,条路连接这,N,个房间，并且没有环路。如果美铃在一个房间设置一个监控点，它就可以看守住与这个房间相邻的所有路，她想知道最少设置多少个看守点就能看住所有路。,分析,状态：,ft0.1,表示对于,t,号节点,0,表示在这个点上设置,看住子树的最数,1,表示不在这个点设置,看着子树的最小数,决策：设置在这个点或不设置在这个点。如果设置，对子节点设置或不设置取较小的来求和，最后再,1,，如果不设置，则对子节点设置来求和（原因）,方程,:ft0=sum(min(fj1,fj0)+1 ft1=sum(fj0) j,是,t,的子节点 如果,i,是叶子节点：,fi0=1 fi1=0,其他,：,可行性,计数,自动机上的DP,贪心DP,集合DP,多进程DP,好题推荐：,CDOJ1503,USACO2.3.4,POJ3691,CDOJ1510,小结,动态规划一般是想起来不容易写起来简单,需要很多题目的练习来找到感觉,动态规划是很优美的,YM各位神犇,谢谢！,mfs6174,