论文--动态规划算法的优化技巧

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

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

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

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

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

5、张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。（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≤k

6、前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]}当k

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