《动态规划优化》PPT课件.ppt

浅谈动态规划优化,2009曹文信息学奥林匹克夏令营Author:Will,简介,动态规划优化的主要方法：1、降维（优化状态）2、优化转移3、常数优化,1.降维,降维是一个通用的说法，其实质就是通过改变动态规划的状态含义，或者抛弃一些冗余状态环节，达到减少状态，加速动态规划的目的,1.1转变思路,很多时候，当得出某种动态规划模型的时候，不要着急动手，而是需要仔细思考一下，是不是有更好的状态表示方法多积累经验，同时又不能拘泥于死板的模型理论，要有创新意识。,1.1.1例题,给定N*M的空白棋盘，在其中放任意放车（可以不放），要使得放在棋盘上的车两两不能攻击，求方案总数MODP的值。,1.1.1.1思路一,按照基本的状态压缩动态规划模型进行解答。optKS表示已经放了前K行，并且每一列是否有车的状态为S（S为一个0/1的2进制序列，那一位为1则表示对应一列已经放过了一个车）的合法方案的数量。比如opt2(101)2即表示前2行放了车且第1，3列有车的状态。,1.1.1.1思路一,则转移就是枚举这一行放还是不放，如果放的话则枚举所有没有放车的行，将对应的2进制位标记为1，进行转移。时间复杂度O(NM2M)空间复杂度O(2M)但是如果N,M1000该怎么办呢？,1.1.1.2思路二,换一个角度来分析问题可以发现，我们需要知道的只是有多少列目前没有放车，并不需要知道具体是哪些列没有放车！因此optk(101)2和optk(110)2是本质等价的。于是我们可以把状态改为：optkS表示放置了前k行，并且有S列没有放置。,1.1.1.2思路二,此时转移稍有不同optk+1S=optkS+optkS+1*(S+1)此时时间复杂度为O(NM)空间复杂度为O(NM)问题得到了解决可见对问题透彻的分析是得出最有效规划方式的前提。,1.2抛弃冗余,很多时候一些状态是不需要的，或者某些维是可以合并的。经过合理的分析我们可以抛弃一些冗余信息，减少状态，加速转移。,1.2.1例题,poet(NOI2009day1p2)有N个诗句，要每个诗句有一个长度Li，要将其排版，一行可以放若干诗句并且每句诗中间用一个空格隔开，有一标准长Len，每一行的难看度是当前行长度C与Len之差绝对值的P次方。求一种最好看的排版方式使得总难看度最小。N10000L2001PL则所有i之前的决策都是无用的。,1.2.1.2思路二,时间复杂度O(NL)空间复杂度O(N)不难发现我们是利用L200这个条件在动态规划中进行了一个剪枝从而将一个空间复杂度无法估计的动态规划成功降低到了O(N)，并成功将复杂度降低。剔除动态规划中的冗余信息是优化动态规划的重要方面。,2.优化转移,1、优化转移方式2、预处理3、费用提前计算4、参数分离5、单调性,2.1优化转移方式,基本的转移方式共有两种1、通过状态选择决策2、通过决策来更新状态,2.1.1状态选择决策,对于每个状态会有一些决策来选择，我们从中选择一个最优的决策，来实现规划的过程，并完成了当前这一状态的计算。可以认为这是一个正向过程。一个简单的例子optk=min(opti+1|AiAk)这是一个不下降子序列的动态规划方程不难得到这个方法O(NlogN)转移方式,2.1.2决策更新状态,当一个状态计算完毕，那么这个状态就自然的成为了后面状态选择的一个决策，于是我们可以在刚产生这个决策的时候更新所有可能用到这个决策的状态。可以说这是一个逆向行为的过程。大多数时候正向方式和逆向方式是差不多的，或者正向方式优于逆向方式，当然也有例外，因此需要我们自己根据实际情况灵活选择。,2.1.2.1例题,给N*M的存在一些障碍的棋盘，在其中放置1*2的多米诺骨牌，问合法的放置总数MODP是多少。,2.1.2.1.1说在前面,我们这里先介绍一种对于状态压缩动态规划转移和状态表示的一般方法按格（点）转移。optxyS表示当前决策格为(x,y)同时2进制状态S表示当前扫描线上每个格子是否被覆盖的状况。,2.1.2.1.1说在前面,x,y,OPT,x,y,(000000)2,2.1.2.1.2分析,不难发现我们之前选择了一种逆向转移的方式即从当前状态枚举下一步行为，并向后更新这样的好处在于（1）方便情况的讨论，简化转移（2）避免了很多不可能出现的状态（3）加速了决策时间复杂度O(N2M)其实，还有一些情况是只有这种更新方式才能优化的，限于篇幅和难度问题这里就不多说了,2.2预处理,预处理就是将动态规划中常用的一些计算环节预先处理好，方便动态规划中重复用到，很多时候利用这种并行计算的问题是可以大大降低算法复杂度的。,2.2.1例题,Grid(BOI2008)有分成N*M格的土地，每个土地有一个工作时间，现在可以将这些土地分成(r+1)*(s+1)块，每块由一个工作人员来完成工作，问最快能多长时间完成全部格子上的工作？rN18sM18,2.2.1.1分析,简单的想法是首先枚举横向如何对土地进行分割，然后再对纵向进行动态规划。枚举部分我们不多说，这里共需要C(N,r)的时间，我们用数组lis记录分割情况关于动态规划，不难得到如下方程：optik表示第i个竖线为第k个分割线。转移比较简单optik=minmax(optjk-1,f(j,i),2.2.1.1分析,代价f我们可以边转移边计算。我们从i开始从后往前枚举j，那么我们显然每次只需要O(N)的代价就可以计算出当前的f。动态规划的时间复杂度为O(rsM2)算法的总体复杂度为O(C(N,r)rsM2),TLE！,2.2.1.2优化,1.预处理出sumxy数组，记录矩形(1,1)-(x,y)中每个格子的工作量之和。则对于任意矩形，我们都可以在O(1)时间内计算出部分和。2.搜索完行的拆分之后，我们预处理出所有f数组。计算f数组的时间复杂度为O(M2r)此时动态规划复杂度为O(M2s)总复杂度降为O(C(N,r)M2(r+s),2.3费用提前计算,在动态规划问题中很多时候计算转移代价成了我们一个很棘手的问题，有些时候我们可能要花费很多的力气来计算某一些特定状态下的费用（比如边界状态等等）其实很多时候我们可以用一些方法，把费用计算花去的时间平摊到其他的地方，从而优化动态规划,2.3.1例题,Sue的小球(sdtsc2008)天空中有N个坐标为(xi,yi)的小球，并会以vi速度匀速下降，这个小球的价值就是其y坐标的1000分之一你有一个在x坐标轴上滑行的飞行器，可以以单位速度在x轴上平移，只要和小球到同一x坐标就能收获那个小球。假设你一开始在(0,0)，并且希望收获所有小球，问可能的最大收益是？N1000,2.3.1.1分析,由于所有小球的x坐标是不变的，因此我们按照x坐标将小球排序。观察一个性质：我们获得球必然是一个连续区间。因此不难得出动态规划表示方法：optLR0/1表示获得球的区间是L,R，同时此时飞行器在左边/右边球所对应的x坐标。,2.3.1.1分析,但是，如何计算代价呢？考虑到一个很好的性质：飞行器的移动速度是单位速度。一种简单的方式是增加一维时间：optLRT0/1表示时刻T此时的状态。可以使用队列保存可行状态，再使用更新状态的方法进行转移。,N=1000！,TLE+MLE!,2.3.1.2优化,现在问题的关键在于如何快速的计算费用。我们现在纠结的问题在于，我们并不知道之前我们是如何行走的，所以如果没有T，我们并不知道当前我们面对的球到底是多少价值。,2.3.1.2优化,我们不妨换个思路，为什么要去纠结于之前的状态呢？当我们做了一个决策之后，对后面的影响我们是知道的，为什么不能把握这一我们清楚的信息呢？道理很清楚：,不要纠结于过去，把眼光方向未来！,天涯何处无芳草，未来永远是光明的！,2.3.1.2优化,每次决策后，我们将这一次移动对所有我们还没有得到的小球产生的费用损失都在决策时计算。我们可以看作小球都没有动，只是在我们每次决策是损失了一些价值。假设当前移动花费了时间T，我们还没有得到的小球的速度和是SV，那么损失的代价就是T*SV/1000,2.3.1.3问题的解决,我们用SI记录前I个小球的速度和那么我们的转移方程就是：optLR0/1-(SN-SR+SL-1)*T/1000+valueoptLR0/1时空复杂度O(N2),2.4参数分离,这是一个信息学竞赛中非常重要的手段，当然难度也比较大，这里限于篇幅和难度，只是简单说一下。参数分离就是通过数学变形将和决策有关的变量和状态有关的变量分开，从而发现一些性质来优化动态规划。,2.4.1例题,Triangles(POI07-08StageIII)给定平面上N1000个点，则显然会构成N(N-1)(N-2)/3个三角形求所有这些三角形的面积和,2.4.1.1预备知识,首先必须要知道叉积向量a=(x1,y1)，b=(x2,y2)则有：ab=x1*y2x2*y1=|a|b|sin为有向角度因此只要保证方向为正，那么向量a和b组成的三角形面积即为(ab)/2,2.4.1.2分析,首先我们花O(N)的时间枚举左下角c所有需要计算的点都以点c为原点建系假设坐标为xi和yi按极角排序后，我们要求的就是不难得出一个O(N3)的算法,2.4.1.3优化,我们给式子做一个变形我们用Syi记录yi到yN的和，Sxi记录xi到xN的和，那么要求的就是,AC,注意此时i和j这两个参数相互分离！,2.5单调性,这是很难的一部分内容，个人认为，如果是把目标放在NOIP级别的比赛，是不用掌握这部分内容的。但是，本着更高更快更强的精神：为了未来我们那崇高的理想！我们不应该着眼于现在！不要为现在而伤感，要相信自己！为了传递这份精神，还是浅浅谈一下,2.5.1四边形不等式,权函数w(i,j)，对于iijj如果满足w(i,j)w(i,j)则称w满足区间单调性如果满足w(i,j)+w(i,j)w(i,j)+w(i,j)则称w满足四边形不等式记忆：交叉不如包含,2.5.1四边形不等式,我们设s(i,j)为opt(i,j)的决策对于如下的普适性动态规划方式：opt(i,j)=min(opt(i,k-1)+opt(k,j)+w(i,j)如果w函数满足四边形不等式则s函数满足决策单调性s(i,j)s(i,j+1)s(i+1,j+1)在普适性的区间动态规划问题中利用单调性可以将复杂度优化至O(N2),2.5.1普适性单调性模型,只要动态规划满足决策单调性，那么就可以至少将一个指数阶的时间复杂度降为一个log阶的复