动态规划法的基本思想.doc

一、动态规划的基本思想 在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。 贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。 在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。 比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。 二、动态规划的基本步骤 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行： （1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个最优解。 其中（1）（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。 三、典型的动态规划举例矩阵连乘问题 作为经典的动态规划算法举例，矩阵连乘问题很好地展现了动态规划的特点和实用价值。给定n个矩阵A1,A2,.,An,其中Ai与Ai+1是可乘的，i=1,2,.n-1。现在要计算这n个矩阵的连乘积。由于矩阵的乘法满足结合律，所以通过加括号可以使得计算矩阵的连乘积有许多不同的计算次序。然而采用不同的加扩号方式，所需要的总计算量是不一样的。若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一个p*r矩阵。如果用标准算法计算C，总共需要pqr次数乘。 现在来看一个例子。A1，A2，A3分别是10*100,100*5和5*50的矩阵。如果按照(A1A2)A3)来计算，则计算所需的总数乘次数是10*100*5+10*5*50=7500。如果按照(A1(A2A3)来计算，则需要的数乘次数是100*5*50+10*100*50=75000,整整是前者的10倍。由此可见，在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量有很大的影响。如何确定计算矩阵连乘积A1A2，.,An的一个计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少便成为一个问题。 对于这个问题，穷举法虽然易于入手，但是经过计算，它所需要的计算次数是n的指数函数，因此在效率上显得过于低下。现在我们按照动态规划的基本步骤来分析解决这个问题，并比较它与穷举法在时间消耗上的差异。 （1）分析最优解的结构。 现在，将矩阵连乘积AiAi+1.Aj简记为Ai:j。对于A1:n的一个最优次序，设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开(1 =k n)，那么完全加括号的方式为(A1.Ak)(Ak+1.An)。依此次序，我们应该先分别计算A1:k和Ak+1:n，然后将计算结果相乘得到A1:n，总计算量为A1:k的计算量加上Ak+1:n的计算量，再加上A1:k和Ak+1:n相乘的计算量。 通过反证法可以证明，问题的关键特征在于，计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种最优子结构性质是该问题可以用动态规划解决的重要特征。 （2）建立递归关系定义最优值。 设计算Ai:j(1 =i =j =n)所需的最少数乘次数为mij，则原问题的最优值为m1n。而且易见，当i=j时，mij=0。 根据上述最优子结构性质，当i j时，若计算Ai:j的最优次序在Ak和Ak+1之间断开，可以定义mij=mik+mk+1j+pi-1*pk*pj(其中，Ai的维数为pi-1*pi)。从而有： 当i=j时，mij=0。 当i j时，mij=minmik+mk+1j+pi-1*pk*pj (i =k j)。 除此之外，若将对应于mij的断开位置记为sij，在计算出最优值mij后，可以递归地由sij构造出相应的最优解。 （3）计算最优值。 如果直接套用mij的计算公式，进行简单的递归计算需要耗费指数计算时间。然而，实际上不同的子问题的个数只是n的平方项级(对于1 =i =j =n不同的有序对(i,j)对应于不同的子问题)。用动态规划解决此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。下面给出计算mij的动态规划算法： void matrixChain (int * p, int n, int * * m, int * * s) for ( int i=1;i =n;i+) mii=0; for ( int r=2;r =n;r+) /链长度控制 for ( int i=1;i =n-r+1;i+) /链起始位置控制 int j=i+r-1; /链终止位置 mij=mi+1j+pi-1*pi*pj; sij=i; for ( int k=i+1;k j;k+) int t=mik+mk+1j+pi-1*pk*pj; if (t mij) mij=t; sij=k; 算法首先设定mii=0(i=1,2,.,n)。然后再根据递归式按矩阵链长的递增方式依此计算出各个mij，在计算某个固定的mij时，只用到已计算出的mik和mk+1j。 稍加分析就可以得出，这个算法以O(n2)的空间消耗大大降低了时间复杂度，计算时间的上界为O(n3)。 （4）构造最优解。 通过以上算法的计算，我们知道了要计算所给矩阵连乘积所需的最少数乘次数，但是还不知道具体应该按照什么顺序来做矩阵乘法才能达到这个次数。然而，sij已经存储了构造最优解所需要的足够的信息。从s1n记录的信息可知计算A1:n的最优加括号方式为(A1:s1n)(As1n+1:n)。同理，每个部分的最优加括号方式又可以根据数组s的相应元素得出。照此递