动态规划加速原理

《动态规划加速原理》由会员分享，可在线阅读，更多相关《动态规划加速原理（5页珍藏版）》请在装配图网上搜索。

1、动态规划加速原理赵明阳【摘要】本文略述了动态规划的内容和基本特点，探讨了动态规划算法在不同适用场合的 优化方式。通过例子说明在时间或空间上的基本优化策略，和预处理、建立状态方程的技巧， 进而得出一般性的概括结论。对于动态规划的基本知识点则不再赘述，请参考相应的书籍资 料。作者假定读者已了解动态规划的知识点及基本思想。【关键字】动态规划 加速 优化一、弓|言现实生活中有许多多阶段决策问题，每个阶段的决策依赖于当前状态，又随即引起状态 的转移，从而动态地产生一个决策序列，这种解决多阶段决策最优化问题的过程叫作动态规 划。动态规划算法是一种常用算法，其特点是充分利用已得到的子问题的结果，避免了大量

2、冗余的重复计算。而在某些问题中，会存在比较苛刻的空间或时间的限制，这时我们需要对 朴素的动态规划算法进行进一步的优化。对动态规划算法的优化，可以较好地提高它的运行效率，从而扩大它的应用范围。它可 以在一定程度上克服计算机硬件的限制。而对于程序编写者，更具有一种挑战性，而在挑战 的过程中，更充分地认识算法的实质，综合提高水平。二、动态规划基本要素和优劣势【关键字】状态、阶段、转移、无后效性、边界性、最优子结构、子问题重叠性 其中：1、最优子结构：问题的最优解包含了其子问题的最优解。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不 总是新问题，有些子问题被反复计算多次，此称为子问

3、题具有重叠性。【优缺点】多项式级的动态规划与指数级的穷举法相比，大大减少了计算量。并且由于阶段性， 可以得出更为丰富的计算结果（当前状态到中间状态的最优值），这对于很多实际问题 来说是很有用的。动态规划相比一般穷举也存在一定缺点：空间占据过多。动态规划算法的基本思路 是用一个表来记录所有已解的子问题的答案，不管该子问题以后是否被用到，只要它被 计算过，就将其结果填入表中（具体的动态规划算法多种多样，但它们具有相同的填表 格式）。因而动态规划算法也被称作一种“用空间换时间”的算法。而动态规划子问题 中也有许多是多余的（它们对最终结果没有影响），对其进行剔除也比穷举搜索的剪枝 要复杂的多。三、常数

4、时间优化常数时间上的优化：循环次数与计算机翻页。对于多重循环，以二重循环为例，在外层循环次数I与内循环次数J满足I1*J1=I2*J2 的情况下，它们的实际效率并不相同。数组在计算机上存放实际是按一维存放的，数组存放 顺序：后继元素下标增量从右到左。数据在机器中存放2KB算一页，因此当寻址加上下表 值的位移量时要进行查页码，反复查询页码会耗费时间。所以当元素较多（大于2KB）时，应尽可能按照存放顺序安排计算。参见例一。【例一】花店橱窗布置1你希望以最美观的方式布置花店的橱窗。现在你有F束（1MFM100）不同品种的鲜花， 还有更多数量的花瓶来放这些鲜花。花瓶被按顺序摆成一行放在货架上，并从1至

5、V（FV100）依次编号（V是花瓶的数目）。1号瓶放在最左面，V号瓶放在最右面。鲜花 也被从1至F编号。编号小的鲜花所放的花瓶的编号也小。也就是说，如果IVJ,则放鲜花 I的花瓶一定放在鲜花J的花瓶的左边。假如你有一束杜鹃花（编号为1），一束秋海棠（编号为2），一束康乃馨（编号为3）。 现在你要把所有这些花放入花瓶中，并且杜鹃花必须放在秋海棠所在花瓶的左边，同样，秋 海棠必须放在康乃馨所在花瓶的左边。如果花瓶的数目比鲜花的数目多，那么将有一些花瓶 被空置。注意：一个花瓶中最多只能放一束鲜花。因为花瓶的形状，鲜花种类也不同，因此不同种类的鲜花放入不同形状的花瓶可能产生 不同的美学效果，并以美学值

6、（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示。花瓶12345鲜花1 （杜鹃花）723-5-24162 （秋海棠）521-410233 （康乃馨）-215-4-2020例如根据上表，杜鹃花放在2号瓶中最好看；而在4号瓶中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有多种这样的方案，输出其中的任何一种。【分析】由于花的放置是有序的，此题可以用动态规划求解。在状态上的选取就有了两 种不同的方法：optj,i:前j束花放在前i个花瓶中；opti,j:前i个花瓶中放j束花；由这两个状态得到的方

7、程是相似的，但是存在常数时间上的差异。第一种状态：转移时FOR J = 1 TO鲜花数目DOFOR J:=I+1 TO 花瓶数目 DOOptI,J6Best第二种状态：转移时FOR I = 1 TO花瓶个数DOFOR J =1 TO I-1 DOOptI,J（Best显然第二种状态循环次数更少。在数据较大时会有常数上的时间节约。相应地，在运算过程中存储中间结果时，计算机也要进行查页。此时运用滚动数组 可以达到空间（多项式）和时间（常数）的双重优化。四、二分法二分法在有序队列的效率优化上有着重要的应用。例如LIS的一种O（NLogN）的优化算 法即是添加一个有序的辅助队列，每次二分进行检索。这种

8、方法是可行的，而且绝大多数有 序队列进行二分时时间复杂度的常数系数是较小的。但是对于LIS这样的原本无序的队列 （辅助队列必须要一个排序的过程），如何能使它的常数系数尽可能的更小？解决方式是很多的。这里主要介绍基于二分的堆和线段树的优化方式。堆大根堆（或小根堆）是优先队列的一种实现方式，堆是一棵满二叉树，根结点总保 持最大（或最小）的性质。如果LIS中元素是连续的，那么利用堆并不会造成空间上的浪费。1 IOI1999 Day1 但如果元素不连续，可以采用离散化的方法，但这样的编程代价太高，我们可以采用同样基 于二分的二叉排序树来进行二分优化。对于不平衡的二叉排序树(最坏情况退化为单链)， 可以

9、用Treap来旋转为平衡二叉树。堆(Heap)与二叉排序树的组合称为Treap。线段树又称为区间树，因为它的一条线段总是对应于一个区间。值得一提的是，在用 线段树优化LIS时，求得原序列最长下降序列长度的同时，我们也完成了对原序列用最少的 不下降序列进行覆盖的构造。虽然当数据范围很大时它同样会造成空间和时间上的浪费，但 是总体效率仍是非常高的。这一点同样可以通过离散来解决。举个例子来说：给出平面上N个点的坐标，需要求出每一个点，位于它的左下角的点 的个数。2常规的方法是朴素的O(N2)的枚举算法。利用线段树可以达到O(NLogN)的效率。我们可以将点按Y的升序，Y相同按X升序排列，因此很容易想

10、到忽略Y坐标，在横 坐标X上使用线段树，计算从1到N的X坐标在当前线段树上小于等于X的个数，然后再 将X插入线段树。这样，横和纵坐标都比第i个结点小的个数就出来了，再加入结果中。这是一个动态规划的过程。实际上这也是一个求前缀和的过程。所以求前缀和同样可以 通过线段树进行优化。容易看出，可以用BST代替线段树的优化。实际上这个优化不需要真正构造出一棵线 段树。我们可以用虚线段树来实现同样的效果。五、利用数学方法的优化所有的动态转移方程都是满足Bellman最优性原理3的。Bellman原理常常被用于计算 一些非线性规划问题。由Bellman原理推导出的各种方程，最终都可以化作适合矩阵乘法运 算的

11、方程。而在进行矩阵乘法时运算顺序的不同可能会造成一些非常数的时间差度。下面主要介绍一种常用的加速算法：四边形不等式。四边形不等式 主要运用在这样的一类问题中：设mi,j表示动态规划的状态量。mi,j 有类似如下的状态转移方程：miJ=optmi,k+mkJ(iWkWj)如果对于任意的 abcd， 有 ma,c+mb,dWma,d+mb,c，那么 mi,j满足四边形 不等式(如果m是一个函数，则称m满足关于区间包含的单调性)。以上是适用这种优化方法的必要条件。对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明， 根据题目的不同而不同。最常见的适合这种优化方法的题目是“最小

12、代价子母树4”。动态规划的复杂度通常是O(n3)，我们可以优化到O(n2)设 si,j为 mi,j的决策量，即 mi,j=mi,si,j+msi,j+j。我们可以证明5： si,j-1Wsi,jWsi+1,j那么改变状态转移方程为：miJ=optmi,k+mkj(siJ-1WkWsi+1J)复杂度决定于s的值，以求mi,i+L为例：(s2,L+1-s1,L)+(s3,L+2-s2,L+1).+(sn-L+1,n-sn-L,n-1)=sn-L+1,n-s1,LWn故总复杂度是O(n2)需要注意的是：以上所给出的状态转移方程比较一般，实际上很多状态转移方程都满足 四边形不等式优化的条件。我们可以通

13、过如下步骤解决这类问题：2 参见 Ural1028 Stars Time Limit: 0.25 second; Memory Limit: 16 MB; (1=N=15000)3关于Bellman原理请读者查阅相关资料4可以参考NOI1995的石子合并问题1. 证明w满足四边形不等式，这里w是m的附属量，形如 mi,j=optmi,k+mk,j+wi,j。注意：大多要先证明w满足条件才能进一步证明 m满足条件。w与m的单调性是统一的。2. 证明m满足四边形不等式3. 证明 si,j-1Wsi,jWsi+1,j六、小结动态规划的加速大多是作用在存在某种单调关系的问题上的。本文主要围绕着的线性单 调问题的解决。其实对于非线性问题，可以展开为线性离散之后用同样于的方式解决。其中 在介绍二分的时候，补充了一个LIS的例子，它提醒我们在多数有序问题中，采用不同形式 的二分法可能会起到画龙点睛的作用。【参考资料】1、算法艺术与信息学竞赛刘汝佳、黄亮著清华大学出版社2、算法导论Cormen,T.H.等著;潘金贵等译机械工业出版社3、 全国信息学奥林匹克联赛培训教程吴文虎王建德著清华大学出版社3、NOI97、NOI98、IOI97、IOI98 试题，ACM97 亚洲赛区试题4、USACO training gate 本文发表在Noi导刊2010-6