107 动态规划法.ppt

例10.1 求 Sn=1+1/2+?+1/n. float sum(int n) { int i，fib，fibl，fib2； float s=0,t； //迭代变量赋初值for(i=1；i=n；i++) //循环语句 { t=1/i； //计算迭代值 s=s+t； //新值取代旧值 } return s； } 这个例子很具一般性，读者可找一些其它例子试试。 解：只需确定出穷举的方案即可，显然，按行优先方案依次比较是最自然的选择,见图10.2。 10.2.1 递归技术 例10.7 求阶乘n!问题 动态规划法通常用于求一个问题在某种意义下的最优解。设计一个动态规划算法，通常可按以下几个步骤进行： ①分析最优解的性质，并刻画其结构特征。 ②递归地定义最优值。 ③以自底向上的方式计算出最优值。 ④根据计算最优值时得到的信息，构造一个最优解。 步骤①～③是动态规划法的基本步骤。在只需要求出最优值的情形下，步骤④可以省去。若需要求出问题的一个最优解；则必须执行步骤④。此时，在步骤③中计算最优值时，通常需要记录更多的信息，以便在步骤④中根据所记录的信息快速地构造出一个最优解。 下面以具体的例子来说明如何运用动态规划算法的设计思想，并分析可用动态规划法求解的问题所应具备的一般特征。 观察这n个矩阵的连乘积A1A2…An，由于矩阵乘法满足结合律，所以计算矩阵的连乘积可以有许多不同的计算次序。这种计算的次序可以用加括号的方式来确定。若矩阵的连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可以根据此次序反复调用两个矩阵相乘的标准算法计算出矩阵的连乘积。 例10.21 计算矩阵连乘积 矩阵连乘问题是：给定n个矩阵{A1,A2,…,An},令A[1..n]=A1A2…An,其中Ai与Ai+1是可乘的，i= 1,2,…,n-1。 完全加括号的矩阵连乘积可递归地定义为： ①单个矩阵也是完全加括号的。 ②矩阵A是完全加括号的，则A可表示为两个完全加括号的矩阵B和C的乘积加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4可有如下5种不同的完全加括号方式： (A1(A2(A3A4))) (A1((A2A3)A4)) ((A1A2)(A3A4)) ((A1(A2A3))A4) (((A1A2)A3)A4) 每一种完全加括号方式对应于一个矩阵连乘积的计算次序，而矩阵连乘积的计算次序与其计算量有密切关系。 两个矩阵的乘积的标准算法如下，其中ar、ac和br、bc分别表示矩阵A和B的行数和列数。 matrixMultiply(int a[][]，int b[][]，int c[][]，int ar，int ac，int br，int bc) { if (ac!=br) printf (″\nerror″)； else { for (i=0；iar；i++) for (j=0；jbc；j++) { c[i][j]=0； for (k=0；kac；++k) c[i][j]+=a[i][k]*b[k][j] } //for } //else } //matrixMultiply 算法10.13 矩阵乘积 从计算矩阵连乘积最优计算次序的动态规划法可以看出，该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。一般说来，问题所具有的这两个重要性质是该问题可用动态规划法求解的基本要素。这对于我们在设计求解具体问题的算法时，是否选择动态规划法具有指导意义。下面我们着重研究动态规划法的这两个基本要素以及动态规划法的一个变形——备忘录方法。 10.7.2 动态规划法的基本要素 设计动态规划法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划法求解的重要线索。 1．最优子结构性质 在矩阵连乘积最优计算次序问题中，我们注意到，若A1…An的最优完全加括号方式在Ak和Ak+1之间将矩阵链断开，则由该次序确定的子链A1A2…Ak和Ak+1Ak+2…An的完全加括号方式也是最优的。也就是说该问题具有最优子结构性质。在分析该问题的最优子结构性质时，我们所用的方法是具有普遍性的。首先假设由问题的最优解导出的其子问题的解不是最优的，然后再设法证明