《把握本质,灵活运用——动态规划的深入探讨(来煜坤)》由会员分享，可在线阅读，更多相关《把握本质,灵活运用——动态规划的深入探讨(来煜坤)（37页珍藏版）》请在金锄头文库上搜索。
1、IOI99 中国集训队优秀论文选 - 79 -把握本质，灵活运用动态规划的深入探讨浙江省萧山中学 来煜坤【关键字】 动态规划 构思 实现【摘要】 本文讨论了动态规划这一思想的核心内容和其基本特点，探讨了动态规划思想的适用范围，动态规划子问题空间和递推关系式确立的一般思路。通过例子说明在子问题确立过程中的一些问题的解决办法：通过加强命题或适当调节确定状态的变量等手段帮助建立动态规划方程，通过预处理使动态规划的过程容易实现等。接着，分析动态规划实现中可能出现的空间溢出问题及一些解决办法。总结指出，动态规划这一思想，关键还在于对不同的问题建立有效的数学模型，在把握本质的基础上灵活运用。一、引言动态规
2、划是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态规划思想来解决的问题，使用动态规划是比较明智的选择。能够用动态规划解决的问题，往往是最优化问题，且问题的最优解(或特定解)的局部往往是局部问题在相应条件下的最优解，而且问题的最优解与其子问题的最优解要有一定的关联，要能建立递推关系。如果这种关系难以建立，即问题的特定解不仅依赖于子问题的特定解，而且与子问题的一般解相关，那么，一方面难以记录下那么多的“一般解” ，另一方面，递推的效率也将是很低的；此外，为了体现动态规划的高时效，子问题应当是互相重叠的，即很多不同的问题共享
3、相同的子问题。(如果子问题不重叠，则宜使用其它方法，如分治法等。)动态规划一般可以通过两种手段比较高效地实现，其一是通过自顶向下记忆化的方法，即通过递归或不递归的手段，将对问题最优解的求解，归结为求其子问题的最优解，并将计算过的结果记录下来，从而实现结果的共享；另一种手段，也就是最主要的手段，通过自底向上的递推的方式，由于这种方式代价要比前一种方式小，因而被普遍采用，下面的讨论均采用这种方式实现。动态规划之所以具有高时效，是因为它在将问题规模不断减小的同时，有效地把把握本质，灵活运用动态规划的深入探讨- 80 - IOI99 中国集训队优秀论文选解记录下来，从而避免了反复解同一个子问题的现象，
4、因而只要运用得当，较之搜索而言，效率就会有很大的提高。动态规划的思想，为我们解决与重叠子问题相关的最优化问题提供了一个思考方向：通过迭代考虑子问题，将问题规模减小而最终解决问题。适于用动态规划解决的问题，是十分广泛的。动态规划的思想本身是重要的，但更重要的是面对具体问题的具体分析。要分析问题是否具备使用动态规划的条件，确定使用动态规划解题的子问题空间和递推关系式等，以及在(常规)内存有限的计算机上实现这些算法。下面分别就构思和实现两个方面进一步探讨动态规划这一思想。二、动态规划解题的构思当我们面对一个问题考虑用动态规划时，十分重要的一点就是判断这个问题能否用动态规划高效地解决。用动态规划构思算
5、法时，往往要考虑到这个问题所涉及到的子问题(子问题空间)，以及如何建立递推式，并最终实现算法。其实，这些过程往往是交织在一起的，子问题空间与递推关系本身就是紧密相联的，为了有效地建立起递推关系，有时就要调整子问题空间；而根据大致确定的子问题空间又可以启发我们建立递推关系式。而能否最终用一个递推关系式来联系问题与其子问题又成了判断一个问题能否使用动态规划思想解决的主要依据。因而孤立地来看这其中的每一部分，硬把思考过程人为地分成几个部分，是困难的，也是不必要的。而且动态规划这种思想方法，没有固定的数学模型，要因题而异，因而也就不可能归纳出一种“万能”的方法。但是对大多数问题而言，还是能够有一个基本
6、的思考方向的。首先，要大致分析一个问题是否可能用动态规划解决。如果一个问题难以确定子问题，或问题与其子问题的特殊解之间毫无关系，就要考虑使用其它方法来解决( 如搜索或其它方法等 )。做一个大概的判断是有必要的，可以防止在这上面白花时间。通常一个可以有效使用动态规划解决的问题基本上满足以下几方面的特性：1、 子问题的最优解仅与起点和终点(或有相应代表意义的量)有关而与到达起点、终点的路径无关。2、 大量子问题是重叠的，否则难以体现动态规划的优越性。下面以 IOI97 的“字符识别 ”问题为例进行分析一般情况下动态规划思路的建立。把握本质，灵活运用动态规划的深入探讨IOI99 中国集训队优秀论文选
7、 - 81 -IOI97 的字符识别问题，题目大意是：在 FONT.DAT 中是对(空格)、AZ 这 27 个符号的字形说明。对每一个符号的字符点阵，用 20 行每行 20 个“0”或者“1”表示。在另一个输入文件中，描述了一串字符的点阵图象(共 N行)，但字符可能是 “破损的” ，即有些 0 变成了 1，而有些 1 变成了 0。每行固定也为 20 个“0”或“1” ，但每一个字符对应的行可能出现如下情形： 仍为 20 行，此时没有丢失的行也没有被复制的行； 为 19 行，此时有一行被丢失了； 为 21 行，此时有一行被复制了，复制两行可能出现不同的破损。要求输出，在一个假定的行的分割情况下，
8、使得“0”与“1”的反相最少的方案所对应的识别结果(字符串)。在初步确定这个问题可以用动态规划思想解决之后，我认为可以考虑用数学的方法( 或观点 )来刻划这个问题，比如通常的最优化问题(这也是动态规划解决的主要问题) ，总会有一个最优化的标准，动态规划要通过递推来实现，就要求分析确定这个状态所需要的量。比如字符识别问题，在问题规模下相当于求N 行的一种分割与对应方法，因而很自然地，考虑前几行就成了一个确定状态的量。最优的标准题中已经给出，即在某种假设(包括分割方法与对应识别方法 )下，使得“0”与“1”反相数最少。如果把这个度量标准看作一个函数，这实际上就是一个最优化函数(指标函数)，最优化函
9、数的值依赖于自变量，即确定状态的量。自变量的个数(这里是一个，即行数，考虑前几行之意 )，要因题而异，关键是要有效地确定状态，在这种状态下，因保证靠这些量已经能够确定最优化函数的值，即最优化函数在这些量确定的时候理论上应有确定的值，否则量是不够的或要使用其它量来刻划，而即使能够完全确定，但在建立递推关系式时发生困难，也要根据困难相应调整确定最优化函数值的自变量。而反过来，如果设定了过多的量来确定最优化函数值，那么，动态规划的效率将会大大下降，或者解了许多不必要解的子问题，或者将重叠子问题变成了在这种自变量条件下的非重叠子问题，从而大大降低效率，甚至完全失去动态规划的高效。在这个例子中，对于前
10、L 行，此最优化函数显然有确定的值。动态规划的递推的一种重要思想是将复杂的问题分解为其子问题。因而确定子问题空间及建立递推关系式是十分重要的。根据确定最优化函数值的自变量，往往对子问题空间有着暗示的作用。通常，通过对最接近问题的这步进行倒推，可以得到这个问题规模减小一些的子问题，不断这样迭代考虑，就往往能够体会到问题的子问题空间。而在这个过程中，通过这种倒推分析，也比较容易得出这种递推关系。需要指出，这仅仅是对一些题目解题思考过程的总结，把握本质，灵活运用动态规划的深入探讨- 82 - IOI99 中国集训队优秀论文选不同的题目原则上仍应区别对待。比如字符识别问题，考虑 n 行该最优化函数值时
11、，注意到最终一定是按照字符分割与识别的，因而最后一个字符或者是 19行，或者是 20 行，再或者是 21 行，仅这样三种可能情况，依次考虑这三种分割方法，对于切割下来的这一段对应于一个字符，对于每一种切割方案，当然应该选择最匹配的字符(否则，如果不使用反相情况最少的字符作为匹配结果而导致全局的最优，那么只要在这一步换成反相情况最少的字符，就得到比假定的“最优”更优的结果，从而导致矛盾)。在去除一个字符后，行数有所减少，而这些行去匹配字符显然也应当使用最优的匹配(可以用反证法证明，与前述类似)，于是得到一个与原问题相似(同确定变量，同最优化标准)但规模较小的子问题，与此同时子问题与原问题的递推关
12、系事实上也得到了建立：fi:=minCompare19i-19+1+fi-19,Compare20i-20+1+fi-20, Compare21i-21+1+fi-21fi表示对前 i 行进行匹配的最优化函数值；Compare19i、Compare20i、Compare21i 分别表示从 i 行开始的 19 行、20 行、21 行与这三种匹配方式下最接近的字符的反相的“0”与“1”的个数。初始情况，f0=0，对于不可能匹配的行数，用一个特殊的大数表示即可。当然，本题的问题主要还不在于动态规划的基本思考上(这里只是通过这个例子，讲一下对于不少动态规划问题的一种基本的思考方向)，还有数学建模 (用
13、 2 进制表示 0、1 串) 等( 源程序见附录中的程序 1)。有时虽然按上述思路得出的确定状态的量已经能够使最优化函数具有确定的值，但是在建立递推关系时发生困难，通过引入新的变量或调整已有变量，也是一条克服困难的途径。比如，NOI97 的一题“积木游戏 ”，题目大意是：积木是一个长方体，已知 N 个有编号的积木的三边 (a、b、c 边)长，要求出用 N 块中的若干块堆成 M(1MN100)堆，使总高度最大的高度值，且满足： 第 K 堆中任意一块的编号大于第 K+1 堆中任意一块积木的编号； 任意相邻两块，下面的块的上表面要能包含上面的那块的下表面，且下面的块的编号要小于上面积木的编号。因为题
14、目要求编号小的堆的积木编号较大，这不太自然，在不改变结果的前提下，把题目改作编号小的堆的积木编号较小，这显然不会影响到最终的高度和，而且，此时每一种合理的堆放方法可看作，按编号递增的顺序选择若干积木，按堆编号递增的顺序逐堆放置，每堆中积木依次在前一个上面堆放而最终形成一种堆放方案。使用上面一般的分析方法，很容易看出，考虑前 i 个木把握本质，灵活运用动态规划的深入探讨IOI99 中国集训队优秀论文选 - 83 -块放置成前 j 堆，这样，i、j 两个量显然能够确定最优函数的值，然而递推关系却不易直接建立，稍作分析就会发现，问题主要出在第 i 块到底能否堆放到其子问题(i-1,j 作变量确定的状
15、态)的最优解方案的最后一堆上。如果考虑增加该序列最后一块的顶部的长与宽的(最小)限制这两个变量，建立递推关系并不困难，然而，很明显，递推过程中大量结果并未被用到，这就人为地扩大了子问题空间，不仅给存储带来麻烦，而且效率也很低。其实，建立递推需要的仅仅是在子问题解最后一堆顶部能否容纳当前积木块，而题中可能产生的这种限制性的面最多仅有 3*100+1(无限制)=301 种情况，这样在多引入一个“最后一堆顶部能够容纳下第 k 种面的要求”这个量后，递推关系只要分当前块另起一堆、当前块加在前一堆上(如果可能的话)和当前块不使用这三种情况就可以了。(源程序参见所附程序 2)此外，有些问题可能会出现仅靠这
16、种调整递推关系仍难以建立，这时，通过增加其它量或函数来建立递推关系式也是一种思考方向(类似于数学归纳法证明时的“加强命题”)。因为，用动态规划解题的一个重要特征是通过递推，而递推是利用原有结果得到新结果的过程。如果在理论上可以证明，一个难以直接实现递推的问题可以通过引入新的递推关系，同时将两者解决，这看起来把问题复杂化了，而实际上由于对于每一步递推，在增加了解决的问题的同时也增加了条件（以前解决的值） ，反而使递推容易进行。举例说明，IOI98 中的“多边形”一题，大意如下：有一个多边形（N 边形） ，顶点上放整数，边上放 “+”或“*” ，要寻找一种逐次运算合并的顺序，通过 N-1 次运算，使最后结果最大。如果单纯考虑用 MAXI,L，从 I 开始进行 L 个运算所得的最大值，则难以实现递推，而根据数学知识，引入了 MINI,L为从 I 开始进行 L 个运算所得的最小值，在进行递推时，却能够有效地用较小的 I，L 来得到较
