动态规划的优化技巧

《动态规划的优化技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划算法的优化技巧福州第三中学毛子青［关键词］动态规划、时间复杂度.优化、状态［摘要］动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素,然后分别阐述了对各个决定因素的优化方法，最后总结全文。［正文］一、引言动态规划是--种重要的程序设计方法，在信息学竞赛小具有广泛的应用。使用动态规划方法解题，对于不少问题具冇空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运丿IJ各种技巧将空间需求控制在软唤件可以

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

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

4、模肓接彩响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。1、改进状态表示状态的规模与状态表示的方法密切相关，通过改进状态衣示减小状态总数是应用较为普遍的一•种方法。例一、例一、RaucousRockers演唱纽（USACO'96）［问题描述］现有n首由RaucousRockers演唱组录制的珍贵的歌llll,计划从屮选择一些歌

5、111來发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌Illi不能重叠。按下面的标准进行选择：(1)(1)这组唱片中的歌曲必须按照它们创作的顺序排序;(2)(2)包含歌曲的总数尽可能多。输入n,m,t,和n首

6、歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。(lWn,m,tW20)[算法分析]本题要求唱片中的歌曲必须按照它们创作顺序排序，这就满足了动态规划的无后效性要求，启发我们采用动态规划进行解题。分析可知，该问题具有最优子结构性质，W：设最优录制方案中笫i首歌录制的位置是从笫j张唱片的笫k分钟开始的，那么前j・l张唱片和笫j张唱片的前k・l分钟是前首歌的最优录制方案，也就是说，问题的最优解包含了子问题的最优解。设n首歌曲按照写作顺序排序后的长度为long[1..n],则动态规划的状态表示描述为:g[i,j,k],

7、OWiWn,OWjWm,OWkvt,表示前i咅歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数口，则问题的最优解为g[n,m,0]o由于歌曲i有发行和不发行两种情况，而且还要分另加的k分钟是否能录制歌Illii。这样我们可以得到如卜•的状态转移方程和边界条件：当k>long[i],时:g[i,j,k]=max{g[i-1,j,k-long[i]],g[i-1,j,k]}当k

8、的状态总数为O(rTnTt),每个状态转移的状态数为0(1),每次状态转移的时间为0(1),所以总的时间复杂度为O(n*m*t)o由于n,m,t均不超过20,所以町以满足要求。[算法优化]当数据规模较大吋，上述算法就无法满足要求，我们来考虑通过改进状态表示提高算法的时间效率。本题的最优冃标是用给定长度的若干张唱片录制尽对能多的歌曲，这实际上等价于在录制给定数屋的歌曲时尽可能少地使用唱片。所谓“尽可能少地使用唱片”，就是指