动态规划算法的优化技巧

福州第三中学毛子青第1页/共16页动态规划算法的优化技巧福州第三中学毛子青[关键词]动态规划、时间复杂度、优化、状态[摘要]动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。[正文]一、引言动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。二、动态规划时间复杂度的分析使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。下面给出动态规划时间复杂度的决定因素：时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1]下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。三、动态规划时间效率的优化3.1减少状态总数我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。福州第三中学毛子青第2页/共16页1、改进状态表示状态的规模与状态表示的方法密切相关，通过改进状态表示减小状态总数是应用较为普遍的一种方法。例一、RaucousRockers演唱组（USACO`96）[问题描述]现有n首由RaucousRockers演唱组录制的珍贵的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：（1）这组唱片中的歌曲必须按照它们创作的顺序排序；（2）包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。（1≤n,m,t≤20）[算法分析]本题要求唱片中的歌曲必须按照它们创作顺序排序，这就满足了动态规划的无后效性要求，启发我们采用动态规划进行解题。分析可知，该问题具有最优子结构性质，即：设最优录制方案中第i首歌录制的位置是从第j张唱片的第k分钟开始的，那么前j-1张唱片和第j张唱片的前k-1分钟是前1..i-1首歌的最优录制方案，也就是说，问题的最优解包含了子问题的最优解。设n首歌曲按照写作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为：g[i,j,k]，0≤i≤n，0≤j≤m，0≤kt，表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目，则问题的最优解为g[n,m,0]。由于歌曲i有发行和不发行两种情况，而且还要分另加的k分钟是否能录制歌曲i。这样我们可以得到如下的状态转移方程和边界条件：当k≥long[i]，i≥1时：g[i,j,k]=max{g[i-1,j,k-long[i]]，g[i-1,j,k]}当klong[i]，i≥1时：g[i,j,k]=max{g[i-1,j-1,t-long[i]]，g[i-1,j,k]}规划的边界条件为：当0≤kt时：g[0,0,k]=0;我们来分析上述算法的时间复杂度，上述算法的状态总数为O(n*m*t)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n*m*t)。由于n，m，t均不超过20，所以可以满足要求。[算法优化]当数据规模较大时，上述算法就无法满足要求，我们来考虑通过改进状态表示提高算法的时间效率。本题的最优目标是用给定长度的若干张唱片录制尽可能多的歌曲，这实际上等价于在录制给定数量的歌曲时尽可能少地使用唱片。所谓“尽可能少地使用唱片”，就是指使用的完整的唱片数尽可能少，或是在使用的完整的唱片数相同的情况下，另加的分钟数尽可能少。分析可知，在这样的最优目标之下，该问题同样具有最优子结构性质，即：设D在前i首歌中选取j首歌录制的最少唱片使用方案，那么若其中选取了第i首歌，则D-{i}是在前i-1首歌中选取j-1首歌录制的最少唱片使用方案，否则D前i-1首歌中选取j首歌录制的最少唱片使用方案，同样，问题的最优解包含了子问题的最优解。改进的状态表示描述为：福州第三中学毛子青第3页/共16页g[i,j]=(a,b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱片另加b分钟。由于第i首歌分为发行和不发行两种情况，这样我们可以得到如下的状态转移方程和边界条件：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的计算方法为：当long[i]≤t-b时：a’=a;b’=b+long[i];当long[i]t-b时：a’=a+1;b’=long[i];规划的边界条件：g[i,0]=(0,0)0≤i≤n这样题目所求的最大值是：ans=max{k|g[n,k]≤(m-1,t)}改进后的算法，状态总数为O(n2)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n2)。值得注意的是，算法的空间复杂度也由改进前的O(m*n*t)降至优化后的O(n2)。（程序及优化前后的运行结果比较见附件）通过对本题的优化，我们认识到：应用不同的状态表示方法设计出的动态规划算法的性能也迥然不同。改进状态表示可以减少状态总数，进而降低算法的时间复杂度。在降低算法的时间复杂度的同时，也降低了算法的空间复杂度。因此，减少状态总数在动态规划的优化中占有重要的地位。2、选择适当的规划方向动态规划方法的实现中，规划方向的选择主要有两种：顺推和逆推。在有些情况下，选取不同的规划方向，程序的时间效率也有所不同。一般地，若初始状态确定，目标状态不确定，则应考虑采用顺推，反之，若目标状态确定，而初始状态不确定，就应该考虑采用逆推。那么，若是初始状态和目标状态都已确定，一般情况下顺推和逆推都可以选用，但是，能否考虑选用双向规划呢？双向搜索的方法已为大家所熟知，它的主要思想是：在状态空间十分庞大，而初始状态和目标状态又都已确定的情况下，由于扩展的状态量是指数级增长的，于是为了减少状态的规模，分别从初始状态和目标状态两个方向进行扩展，并在两者的交汇处得到问题的解。上述优化思想能否也应用到动态规划之中呢？来看下面这个例子。例二、Divide(Merc`2000)[问题描述]有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值和相等，问是否可以实现。其中大理石的总数不超过20000。(英文试题详见附件)[算法分析]令S=∑(i*a[i])，若S为奇数，则不可能实现，否则令Mid=S/2，则问题转化为能否从给定的大理石中选取部分大理石，使其价值和为Mid。这实际上是母函数问题，用动态规划求解也是等价的。m[i,j]，0≤i≤6，0≤j≤Mid，表示能否从价值为1..i的大理石中选出部分大理石，使其价值和为j，若能，则用true表示，否则用false表示。则状态转移方程为：m[i,j]=m[i,j]ORm[i-1,j-i*k](0≤k≤a[i])规划的边界条件为：m[i,0]=true；0≤i≤6若m[i,Mid]=true，0≤i≤6，则可以实现题目要求，否则不可能实现。我们来分析上述算法的时间性能，上述算法中每个状态可能转移的状态数为a[i]，每次状态福州第三中学毛子青第4页/共16页转移的时间为O(1)，而状态总数是所有值为true的状态的总数，实际上就是母函数中项的数目。[算法优化]实践发现：本题在i较小时，由于可选取的大理石的价值品种单一，数量也较少，因此值为true的状态也较少，但随着i的增大，大理石价值品种和数量的增多，值为true的状态也急剧增多，使得规划过程的速度减慢，影响了算法的时间效率。另一方面，我们注意到我们关心的仅是能否得到价值和为Mid的值为true的状态，那么，我们能否从两个方向分别进行规划，分别求出从价值为1..3的大理石中选出部分大理石所能获得的所有价值和，和从价值为4..6的大理石中选出部分大理石所能获得的所有价值和。最后通过判断两者中是否存在和为Mid的价值和，由此，可以得出问题的解。状态转移方程改进为：当i≤3时：m[i,j]=m[i,j]ORm[i-1,j-i*k](1≤k≤a[i])当i3时：m[i,j]=m[i,j]ORm[i+1,j-i*k](1≤k≤a[i])规划的边界条件为：m[i,0]=true；0≤i≤7这样，若存在k，使得m[3,k]=true,m[4,Mid-k]=true，则可以实现题目要求，否则无法实现。（程序及优化前后的运行结果比较见附件）从上图可以看出双向动态规划与单向动态规划在计算的状态总数上的差异。回顾本题的优化过程可以发现：本题的实际背景与双向搜索的背景十分相似，同样有庞大的状态空间，有确定的初始状态和目标状态，状态量都迅速增长，而且可以实现交汇的判断。因此，由本题的优化过程，我们认识到，双向扩展以减少状态量的方法不仅适用于搜索，同样适用于动态规划。这种在不同解题方法中，寻找共通的属性，从而借用相同的优化思想，可以使我们不断创造出新的方法。3.2减少每个状态转移的状态数在使用动态规划方法解题时，对当前状态的计算都是进行一些决策并引用相应的已经计算过的状态，这个过程称为“状态转移”。因此，每个状态可能做出的决策数，也就是每个状态可能转移的状态数是决定动态规划算法时间复杂度的一个重要因素。本节将讨论减少每个状福州第三中学毛子青第5页/共16页态可能转移的状态数的一些方法。1、四边形不等式和决策的单调性例三、石子合并问题(NOI`95)[问题描述]在一个操场上摆放着一排n（n≤20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。[算法分析]这道题是动态规划的经典应用。由于最大得分和最小得分是类似的，所以这里仅对最小得分进行讨论。设n堆石子依次编号为1，2，…..，n。各堆石子数为d[1..n]，则动态规划的状态表示为：m[i,j]，1≤i≤j≤n，表示合并d[i..j]所得到的最小得分，则状态转移方程和边界条件为：m[i,j]=0i=jjiljkildjkmkimjim]}[],[]1,[{min],[i＜j同时令s[i,j]=k，表示合并的断开位置，便于在计算出最优值后构造出最优解。上式中jilld][的计算，可在预处理时计算ijjdit1][][，i=1..n；t[0]=0,则：]1[][][itjtldjil上述算法的状态总数为O(n2)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，所以总的时间复杂