动态规划的非常规优化.doc

动态规划的非常规优化湖南 周戈林1 内容介绍动态规划是信息学竞赛的重要分支，它以功能强大、技巧灵活著称。用动态规划解题，要简洁高效地表示状态，在这一基础上建立状态转移方程，从而由边界条件推出问题的解。但是在多数情况下，需要解决的问题规模是很大的，这就需要我们对动态规划算法进行优化。比较传统的优化方式有以下三种：减少需要计算的状态总数、减少每个状态转移的状态数、减少状态转移的时间。从一般意义上讲，这三种优化都是指对算法时间复杂度的优化，可参见论文动态规划算法的优化技巧（作者毛子青）。本文尝试阐述一些其它的优化方法，它们没有降低算法的时间复杂度，并且不同于常说的“代码优化”，却能给程序的速度带来质的飞跃。2 搜索和动态规划的比较动态规划和搜索是两类看上去差异很大的算法：前者以高效著称，常用于解决数据规模庞大的问题；后者却速度缓慢，往往只能解决范围很小的问题。但从某种意义上来讲，动态规划和搜索在本质上是相同的：1 动态规划和搜索都注重对状态的刻画；2 动态规划和搜索都通过转移状态计算问题结果。既然本质上相同，那么为什么两者的适用范围差别很大呢？事实上，某些算法中的状态表示很有规律，需要计算的状态数目也比较稳定，适合用几重循环的方式递推出解，这就是动态规划算法；某些算法中需要计算的状态数目极大但是大多无需计算，可以通过在状态转移时的判断和调整去除这些冗余状态，这就是搜索算法。动态规划和搜索并不是对立的，它们结合的经典例子就是记忆化搜索。记忆化搜索利用剪枝尽量不计算不可能成为最优解的状态。在本文中，作者将动态规划和搜索进一步结合，尝试利用搜索的优化方法加速动态规划，取得了很好的效果。3 范例例一：分配任务Jiajia、Wind和他们的m-2个孩子去郊外种树。他们认为树和人一样，都应该是一对一对的。因此他们想种偶数棵树，并且这偶数棵树排列在两行内，每行恰好n棵树。种每棵树的难度可能不相同，所以Jiajia很关心种每棵树的难度，并且打算把所有的树分成m个集合，每人种一个集合中的所有树。 每个人种的树都应该构成一个边平行于坐标轴的矩形区域。这个人种树的难度值就是他种的所有树的难度值之和。因为Jiajia总是会承担最难的一份任务（他当然不能把这份任务交给亲爱的Wind和可爱的孩子们），所以他希望使m份任务中最大的一份最小。 图1即为样例，不同的颜色代表不同的植树工作。图中是只有三个人（Jiajia,Wind和Autumn）的情况，但是你的程序应该能处理更复杂的情况，因为Jiajia和Wind有很多很多孩子。J图1输入描述输入文件第一行是n和m。此后两行，每行n个正整数从左到右描述每个位置的种树难度分。你可以认为n10000，mmin2n,1000，同时所有种树难度分之和不超过230。输出描述输出文件仅包含一个整数，为Jiajia工作难度的最小值。输入样例3 31 2 62 1 6输出样例6解法分析本题给定一个2n的矩阵，矩阵的每个元素都是正数，要求将其分成m个子矩阵，使元素和最大的子矩阵最小。这是一个传统问题（把一个序列分成m个连续子序列）的强化版。对于传统问题，现在最好的方法是二分答案法：二分枚举可能的最优值。对于每个被枚举的值，用贪心算出要得到这个最优值，至少需要分成多少块。根据这个块数与m的关系修正枚举范围。尝试仍然用二分答案来解决强化后的问题。现在的问题是如何尽快的计算需要分割的子矩阵数。贪心是肯定不行的，因为子矩阵的高可能是2也可能是1。尝试用最简单的动态规划计算，假设当前枚举的最大工作难度为l，定义f i, j表示把矩阵1,1到1, i以及2,1到2, j的部分，在满足每个子矩阵的元素和不超过l的前提下划分，所需的最小子矩阵数目。为了写出状态转移方程，还要定义一些辅助函数。设ai, j表示原矩阵中第i行第j列的元素值，定义，及，。这些函数都可以在线性时间内递推计算出来。然后就有状态转移方程如下：当ij时有；当ij时有；边界条件为f 0,0= 0，最终答案是f n, n。这个动态规划算法是正确的，但使用它进行一次判定需要O(n2)的时间和空间，对于本题的数据范围是完全不可接受的。为什么这个算法效率不高呢？这是因为f i, j的值是一段段增加的，相邻的一些状态值往往相同，如果把它们都计算出来就太浪费了。考虑到矩阵只有两行，因此子矩阵也只可能是一行或者两行，那么任意一个分配方案必然是一段两行的子矩阵与一段一行的子矩阵交错分布。由于两行的子矩阵比较整齐，我们以它作为状态，也就是只计算f i, i，不妨用另外一个函数gi来表示它。状态转移方程就是，其中cost j+1, i表示把第j+1列到第i列划分所需的最小子矩阵数。具体计算的时候并不是枚举j，而是设立两个指针p,q，初始时p = q = i。每次选择p和q中较大者尽量往回走（调用pre函数），然后用走的次数（也就是分出的子矩阵数目）c+gmax(p,q)来更新gi，直到再次出现p = q时停止。当然也要用gpre3,i+1去更新gi。这样优化后，首先空间复杂度就降为线性，同时由于m比较小，指针滑动的速度也比较快，因此每个状态转移的时间远小于O(n)。虽然时间复杂度仍然是O(n2logC)，但实际运行速度相当不错，即使是极端数据也能在0.3s内出解。小结本题的优化方法类似于搜索优化中对状态描述的简化和对搜索顺序的调整。这种思路可以优化很多传统的动态规划问题，但往往效果不明显，也就没有受到重视。从这一题可以看出，这种技巧有其价值，值得我们学习和研究。例二：DNA序列的最佳比对（POJ Monthly-2005.07.31, CHEN Shixi）Gnaileux Iew最近对生物信息学很感兴趣。他没日没夜地阅读论文，把所有的精力都花在研究上。今天他想复习一下生物信息学中最基本的问题：DNA序列的最佳比对。他希望能找到一个简单有效的算法计算两个很相似的DNA序列的比对。一个DNA序列可以看作一个只包含A,G,C,T的字符序列。为了比对这两个字符序列，可能需要在某些位置插入一些空格符，使得两个字符序列的长度相同。并且我们通过一个得分矩阵来计算每一对字符的得分。Gnaileux Iew使用了一个尽量小的得分矩阵。图2就是Gnaileux Iew使用的得分矩阵：举例来说， DNA序列AAGACG和CAGAGCTC的某个比对是：-AAGA-C-G CA-GAGCTC图2得分是3+0+3+0+0+3+0+3+4=16。Gnaileux Iew只对非常相似的序列最佳比对感兴趣。严格地说，LCS(A,B)| 2 / (|A |+ |B|)90%，这里A和 B是需要比对的DNA序列，LCS(A,B)是A和B的最长公共子序列长度。输入描述输入包含多组数据，每组数据包含两行，每行为一个只包含A,G,C,T四种字符的DNA序列。每个DNA序列的长度都不超过50000。输出描述对于每组数据输出一行，为DNA序列比对的最小得分。输入样例AGTGCTGAAAGTTGCGCCAGTGACAGTGCTGAAGTTCGCCAGTTGACGCACAATTTTTCCCAGAGAGACGAATTTTTCCCAGAGAGA输出样例127解法分析例二的核心问题是最长公共子序列问题的变形。对于这个问题，传统的解法是用f i, j表示第一个串比对到第i个字符、第二个串比对到第j个字符的最小得分。那么有以下方程： 其中scoreAi,Bj为这两个字符的对比得分。边界条件为f 0,0=0, f -1,i = f i,-1 = +。这个算法需要计算O(|A|B|)个状态，在本题条件下是明显要超时的。我们希望能像例一那样简化状态，但是本题中从f 0,0到f i, j的转移过程是一点一点进行的。即使能找到一个一维的状态描述，枚举转移的状态数也要到达完整的O(|A|B|)个，因此可以说本题的状态已经无法优化了。状态不能优化不等于算法不能优化，在已有的状态定义的基础上，我们可以尝试尽量少计算一些状态。首先把状态转移的方式变为前推式：只有当某个状态有可能影响最优解时才进行扩展。对于每个i，我们记录一个可能影响最优解的状态列表listi。在状态转移的过程中通过listi扩展listi+1，并利用以下三点剪枝：1设当前状态为f i, j，在listi+1中的后继状态为f i, j1，若f i, jf i, j1+3 ( j1-j)，那么这个状态是不需要扩展的。2设当前状态为f i, j，在listi+1中最新算出来的状态为f i+1, j2，若f i, jf i, j2+3 ( j-j2+1)，那么当前状态是不需要扩展的。3注意到LCS(A,B)| 2 / (|A |+ |B|)90%这个条件，这告诉我们比对最小得分l至多为。如果某个状态f i, j满足，那么这个状态就肯定不用扩展了。这三个剪枝操作的正确性都是显然的。因为无效状态到f |A|,|B|的路径总会被其他的状态“截断”，从而不对最终结果造成影响。经过以上剪枝，利用该算法编写的程序对于一组数据只需要计算约108个状态，远小于普通动态规划的500002=2.5109（个），运行速度被提高了几十倍。小结剪枝是搜索中手法最灵活的部分，本题的优化方法就类似于搜索优化中的剪枝。算法利用当前状态到目标状态的距离和相邻状态间的关系进行剪枝，减少了大量冗余。4 总结本文论述的算法忽略了动态规划与搜索的界限，成功利用搜索的优化思想来加速动态规划。例一注重于状态的刻画，例二关键在状态的转移。可见在实用主义的计算机科学中不能拘泥于前人的理论。敢于实践、敢于研究、敢于使