动态规划算法的优化技巧分析课程设计.docx

1、动态规划算法的优化技巧分析课程设计课程设计题目：动态规划算法的优化技巧分析简介：动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法一、引言动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动

2、态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。二、动态规划时间复杂度的分析使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。但是，动态规划求解问题时，仍然存在冗余。它

3、主要包括：求解无用的子问题，对结果无意义的引用等等。下面给出动态规划时间复杂度的决定因素：时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间1下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。三、动态规划时间效率的优化3.1 减少状态总数我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态

4、规划优化的重要部分，本节将讨论减少状态总数的一些方法。1、改进状态表示状态的规模与状态表示的方法密切相关，通过改进状态表示减小状态总数是应用较为普遍的一种方法。例一、 Raucous Rockers 演唱组（USACO96）问题描述现有n首由Raucous Rockers 演唱组录制的珍贵的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：（1） 这组唱片中的歌曲必须按照它们创作的顺序排序；（2） 包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的

5、放在唱片中。输出所能包含的最多的歌曲数目。（1n, m, t20）算法分析本题要求唱片中的歌曲必须按照它们创作顺序排序，这就满足了动态规划的无后效性要求，启发我们采用动态规划进行解题。分析可知，该问题具有最优子结构性质，即：设最优录制方案中第i首歌录制的位置是从第j张唱片的第k分钟开始的，那么前j-1张唱片和第j张唱片的前k-1分钟是前1.i-1首歌的最优录制方案，也就是说，问题的最优解包含了子问题的最优解。设n首歌曲按照写作顺序排序后的长度为long1.n，则动态规划的状态表示描述为：gi, j, k，0in，0jm，0kt，表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目

6、，则问题的最优解为gn,m,0。由于歌曲i有发行和不发行两种情况，而且还要分另加的k分钟是否能录制歌曲i。这样我们可以得到如下的状态转移方程和边界条件：当klongi，i1时：gi, j, k=maxgi-1,j,k-longi，gi-1,j,k当klongi，i1时：gi, j, k=maxgi-1,j-1,t-longi，gi-1,j,k规划的边界条件为：当0kt-b时： a=a+1; b=longi;规划的边界条件：gi,0=(0,0) 0in这样题目所求的最大值是：ans=maxk| gn, k(m-1,t)改进后的算法，状态总数为O(n2)，每个状态转移的状态数为O(1)，每次状态转

7、移的时间为O(1)，所以总的时间复杂度为O(n2)。值得注意的是，算法的空间复杂度也由改进前的O(m*n*t)降至优化后的O(n2)。（程序及优化前后的运行结果比较见附件）通过对本题的优化，我们认识到：应用不同的状态表示方法设计出的动态规划算法的性能也迥然不同。改进状态表示可以减少状态总数，进而降低算法的时间复杂度。在降低算法的时间复杂度的同时，也降低了算法的空间复杂度。因此，减少状态总数在动态规划的优化中占有重要的地位。2、选择适当的规划方向 动态规划方法的实现中，规划方向的选择主要有两种：顺推和逆推。在有些情况下，选取不同的规划方向，程序的时间效率也有所不同。一般地，若初始状态确定，目标状

8、态不确定，则应考虑采用顺推，反之，若目标状态确定，而初始状态不确定，就应该考虑采用逆推。那么，若是初始状态和目标状态都已确定，一般情况下顺推和逆推都可以选用，但是，能否考虑选用双向规划呢？双向搜索的方法已为大家所熟知，它的主要思想是：在状态空间十分庞大，而初始状态和目标状态又都已确定的情况下，由于扩展的状态量是指数级增长的，于是为了减少状态的规模，分别从初始状态和目标状态两个方向进行扩展，并在两者的交汇处得到问题的解。上述优化思想能否也应用到动态规划之中呢？来看下面这个例子。例二、 Divide (Merc2000)问题描述有价值分别为1.6的大理石各a1.6块，现要将它们分成两部分，使得两部

9、分价值和相等，问是否可以实现。其中大理石的总数不超过20000。(英文试题详见附件)算法分析令S=(i*ai)，若S为奇数，则不可能实现，否则令Mid=S/2，则问题转化为能否从给定的大理石中选取部分大理石，使其价值和为Mid。这实际上是母函数问题，用动态规划求解也是等价的。mi, j，0i6，0jMid，表示能否从价值为1.i的大理石中选出部分大理石，使其价值和为j，若能，则用true表示，否则用false表示。则状态转移方程为：mi, j=mi, j OR mi-1,j-i*k (0kai)规划的边界条件为：mi,0=true； 0i6若mi, Mid=true，0i6，则可以实现题目要求

10、，否则不可能实现。我们来分析上述算法的时间性能，上述算法中每个状态可能转移的状态数为ai，每次状态转移的时间为O(1)，而状态总数是所有值为true的状态的总数，实际上就是母函数中项的数目。算法优化实践发现：本题在i较小时，由于可选取的大理石的价值品种单一，数量也较少，因此值为true的状态也较少，但随着i的增大，大理石价值品种和数量的增多，值为true的状态也急剧增多，使得规划过程的速度减慢，影响了算法的时间效率。另一方面，我们注意到我们关心的仅是能否得到价值和为Mid的值为true的状态，那么，我们能否从两个方向分别进行规划，分别求出从价值为1.3的大理石中选出部分大理石所能获得的所有价值

11、和，和从价值为4.6的大理石中选出部分大理石所能获得的所有价值和。最后通过判断两者中是否存在和为Mid的价值和，由此，可以得出问题的解。状态转移方程改进为：当i3时：mi, j=mi, j OR mi-1,j-i*k (1kai)当i3时：mi, j=mi, j OR mi+1,j-i*k (1kai)规划的边界条件为：mi,0=true； 0i7这样，若存在k，使得m3,k=true, m4,Mid-k=true，则可以实现题目要求，否则无法实现。（程序及优化前后的运行结果比较见附件）从上图可以看出双向动态规划与单向动态规划在计算的状态总数上的差异。回顾本题的优化过程可以发现：本题的实际背景

12、与双向搜索的背景十分相似，同样有庞大的状态空间，有确定的初始状态和目标状态，状态量都迅速增长，而且可以实现交汇的判断。因此，由本题的优化过程，我们认识到，双向扩展以减少状态量的方法不仅适用于搜索，同样适用于动态规划。这种在不同解题方法中，寻找共通的属性，从而借用相同的优化思想，可以使我们不断创造出新的方法。3.2 减少每个状态转移的状态数在使用动态规划方法解题时，对当前状态的计算都是进行一些决策并引用相应的已经计算过的状态，这个过程称为“状态转移”。因此，每个状态可能做出的决策数，也就是每个状态可能转移的状态数是决定动态规划算法时间复杂度的一个重要因素。本节将讨论减少每个状态可能转移的状态数的

13、一些方法。1、四边形不等式和决策的单调性例三、石子合并问题(NOI95)问题描述 在一个操场上摆放着一排n（n20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。算法分析这道题是动态规划的经典应用。由于最大得分和最小得分是类似的，所以这里仅对最小得分进行讨论。设n堆石子依次编号为1，2，.，n。各堆石子数为d1.n，则动态规划的状态表示为：mi,j，1ijn，表示合并di.j所得到的最小得分，则状态转移方程和边界条件为：mi,j=0 i=j ij同时令

14、si,j=k，表示合并的断开位置，便于在计算出最优值后构造出最优解。上式中的计算，可在预处理时计算，i=1.n；t0=0, 则：上述算法的状态总数为O(n2)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n3)。算法优化当函数wi,j满足时，称w满足四边形不等式2。当函数wi,j满足wi,jwi,j 时称w关于区间包含关系单调。在石子归并问题中，令wi,j= ，则wi,j满足四边形不等式，同时由di0,ti0可知wi,j满足单调性。mi,j=0 i=j ij 对于满足四边形不等式的单调函数w，可推知由递推式定义的函数mi,j也满足四边形不等式，即。这一

15、性质可用数学归纳法证明如下：我们对四边形不等式中“长度”l=j-i进行归纳：当i=i或j=j时，不等式显然成立。由此可知，当l1时，函数m满足四边形不等式。下面分两种情形进行归纳证明：情形1：ii=jj。下面只讨论kj，kj的情况是类似的。情形1.1：kj，此时：情形2：iijy。下面只讨论zy，zy的情况是类似的。由izyj有：综上所述，mi,j满足四边形不等式。令si,j=maxk | mi,j=mi,k-1+mk,j+wi,j 由函数mi,j满足四边形不等式可以推出函数si,j的单调性，即si,jsi,j+1si+1,j+1, ij当i=j时，单调性显然成立。因此下面只讨论ij的情形。由

16、于对称性，只要证明si,jsi,j+1。令mki,j=mi,k-1+mk,j+wi,j。要证明si,jsi,j+1，只要证明对于所有ikkj且mki,jmki,j，有：mki,j+1mki,j+1。事实上，我们可以证明一个更强的不等式mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用递推定义式将其展开整理可得：mk,j+mk,j+1mk,j+mk,j+1，这正是kkjj+1时的四边形不等式。综上所述，当w满足四边形不等式时，函数si,j具有单调性。于是，我们利用si,j的单调性，得到优化的状态转移方程为：mi,j=0 i=j

17、iy，下面仅讨论zy，zy的情况是类似的。由izyj有： 接着，我们用数学归纳法证明函数m也满足四边形不等式。对四边形不等式中“长度”l=j-i进行归纳：当i=i或j=j时，不等式显然成立。由此可知，当l1时，函数m满足四边形不等式。下面分两种情形进行归纳证明：情形1：ii=jj。下面只讨论kj，kj的情况是类似的。情形2：iijy。情形2.1，当zyjj时：情形2.2，当i-1i-1yzj时：最后，我们证明决策si,j满足单调性。为讨论方便，令mki,j=mi-1,k+wk+1,j；我们先来证明si-1,jsi,j，只要证明对于所有ikkj且mki-1,jmki-1,j，有：mki,jmki

18、,j。类似地，我们可以证明一个更强的不等式mki-1,j-mki-1,jmki,j-mki,j也就是： mki-1,j+mki,jmki,j+mki-1,j利用递推定义式展开整理的：mi-2,k+mi-1,kmi-1,k+mi-2,k，这就是i-2i-1kk时m的四边形不等式。我们再来证明si,jsi,j+1，与上文类似，设kkj，则我们只需证明一个更强的不等式： mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用递推定义式展开整理的：wk+1,j+wk+1,j+1wk+1,j+1+wk+1,j，这就是k+1k+1jj+1时w

19、的四边形不等式。综上所述，该问题的决策si,j具有单调性，于是优化后的状态转移方程为：m1,j=w1,j ij si,j=k同上文所述，优化后的算法时间复杂度为O(n*p)。（程序及优化前后的运行结果比较见附件） 四边形不等式优化的实质是对结果的充分利用。它通过分析状态值之间的特殊关系，推出了最优决策的单调性，从而在计算当前状态时，利用已经计算过的状态所做出的最优决策，减少了当前的决策量。这就启发我们，在应用动态规划解题时，不仅可以实现状态值的充分利用，也可以实现最优决策的充分利用。这实际上是从另一个角度实现了“减少冗余”。2、决策量的优化通过分析问题最优解所具备的性质，从而缩小有可能产生最优

20、解的决策集合，也是减少每个状态可能转移的状态数的一种方法。大家所熟悉的NOI96中的添加号问题，正是从“所得的和最小”这一原则出发，仅在等分点的附近添加号，从而大大减少了每个状态转移的状态数，降低了算法的时间复杂度。让我们在再来看一例。例五、石子归并的最大得分问题问题描述 见例三，本例只考虑最大得分问题。算法分析 设n堆石子依次编号为1，2，.，n。各堆石子数为d1.n，则动态规划的状态表示为：mi,j，1ijn，表示合并di.j所得到的最大得分，则状态转移方程和边界条件为：mi,j=0 i=j ij同时令si,j=k，表示合并的断开位置，便于在计算出最优值后构造出最优解。 该算法的时间复杂度

21、为O(n3)。算法优化仔细分析问题，可以发现：si,j要么等于i+1，要么等于j，即：证明可以采用反证法，设使mi,j达到最大值的断开位置为p，且i+1pj，下面分为2种情形讨论。情形1、yz由pj，可设sp,j=k，则相应的合并方式可以表示为：( (aiap-1) ( (ap.ak-1) (ak.aj) ) )相应的得分为：下面考虑另一种合并方案si,j=k，si,k=p，表示为：( ( (aiap-1) (ap.ak-1) ) (ak.aj) )相应的得分为：由yz可得，TT，这与使mi,j达到最大值的断开位置为p的假设矛盾。情形2、yz 与情形1类似。于是，状态转移方程优化为：mi,j=

22、0 i=j ij优化后每个状态转移的状态数减少为O(1)，算法总的时间复杂度也降为O(n2)。（程序及优化前后的运行结果比较见附件）本题的优化过程是通过对问题最优解性质的分析，找出最优决策必须满足的必要条件，这与搜索中的最优性剪枝的思想十分类似，由此我们再次看到了相同的优化思想应用于不同的算法设计方法。同时，我们也认识到：动态规划的优化必须建立在全面细致分析问题的基础上，只有深入分析问题的属性，挖掘问题的实质，才能实现算法的优化。3、合理组织状态 在动态规划求解的过程中，需要不断地引用已经计算过的状态。因此，合理地组织已经计算出的状态有利于提高动态规划的时间效率。例六、求最长单调上升子序列问题

23、描述给出一个由n个数组成的序列x1.n，找出它的最长单调上升子序列。即求最大的m和a1,a2,am，使得a1a2am且xa1xa2xam。算法分析这也是一道动态规划的经典应用。动态规划的状态表示描述为：mi，1in，表示以xi结尾的最长上升子序列的长度，则问题的解为 maxmi,1in，状态转移方程和边界条件为：mi=1+max0, mk|xkxi , 1k1时，令pi=k，表示最优决策，以便在计算出最优值后构造最长单调上升子序列。上述算法的状态总数为O(n)，每个状态转移的状态数最多为O(n)，每次状态转移的时间为O(1)，所以算法总的时间复杂度为O(n2)。算法优化我们先来考虑以下两种情况：1、若xixj，m