清华大学出版社 TSINGHUA UNIVERSITY PRESS 分析最优解的结构 特征:计算A[i:j的最优次序所包含的计算矩 阵子链A[:k]和A[k+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问 题的最优解。这种性质称为最优子结构性质 问题的最优子结构性质是该问题可用动态规划 算法求解的显著特征
11 分析最优解的结构 • 特征：计算A[i:j]的最优次序所包含的计算矩 阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 • 矩阵连乘计算次序问题的最优解包含着其子问 题的最优解。这种性质称为最优子结构性质。 问题的最优子结构性质是该问题可用动态规划 算法求解的显著特征
清华大学出版社 TSINGHUA UNIVERSITY PRESS 建立递归关系 设计算A[i:j,1≤≤j≤n,所需要的最少数乘次数 m[i,j,则原问题的最优值为m[1,n] 当i=j时,A[i:j=Ai,因此,m[i,i=0,i=1,2…,n 当i<j时 m[i,j]=m[i, k]+m[k+1,J]+p-lpkp 这里A的维数为P1×P 可以递归地定义m[门为 0 min(mi, k]+m[k+1,j]+pippi i<j i≤k<j k的位置只有j-i种可能 12
12 建立递归关系 ◼ 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数 m[i,j]，则原问题的最优值为m[1,n] ◼ 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n ◼ 当i<j时， ◼ 可以递归地定义m[i,j]为： pi pk pj m i j m i k m k j 1 [ , ] [ , ] [ 1, ] = + + + − 这里 Ai 的维数为 pi−1 pi + + + = = − m i k m k j p p p i j i j m i j i k j min { [ , ] [ 1, ] } 0 [ , ] 1 i k j k 的位置只有 j − i 种可能
清华大学出版社 TSINGHUA UNIVERSITY PRESS 计算最优值 对于1≤≤j≤n不同的有序对(i,j)对应于不同的子问题。 因此,不同子问题的个数最多只有 +n=(n2) 由此可见,在递归计算时,许多子问题被重复计算多 次。这也是该问题可用动态规划算法求解的又一显著 特征。 用动态规划算法解此问题,可依据其递归式以自底向 上的方式进行计算。在计算过程中,保存已解决的子 问题答案。每个子问题只计算一次,而在后面需要时 只要简单查一下,从而避免大量的重复计算,最终得 到多项式时间的算法 13
13 计算最优值 ◼ 对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。 因此，不同子问题的个数最多只有 ◼ 由此可见，在递归计算时，许多子问题被重复计算多 次。这也是该问题可用动态规划算法求解的又一显著 特征。 ◼ 用动态规划算法解此问题，可依据其递归式以自底向 上的方式进行计算。在计算过程中，保存已解决的子 问题答案。每个子问题只计算一次，而在后面需要时 只要简单查一下，从而避免大量的重复计算，最终得 到多项式时间的算法 ( ) 2 2 n n n + =
清华大学出版 用动态规划法求最优解 S public static void matrix chain(int p, int [l m, int [o s) Al A2A3A4A5A6 int n=p length-1 30×3535×1515×55×1010×2020×25 for(int i=1; i <=n; i++)m00=0 m{22]+m{3[5]+P1P2P5=0+2500+35×15×20=13000 for (int r= 2; r <= n; r++) m2]5=mmm2]3]+m4|5+PP3P=2625+1000+35×5×20=7125 for(inti=1;i<=n-「+1;|++){ m{24]+m{5]S]+P1P4P5=4375+0+35×10×20=11375 int =i+r-1 算法复杂度分析 m=m+1+p-pp:算法 matrixchain的主要计算量取决于算法中对r, s[]=i; 和k的3重循环。循环体内的计算量为O(1),而3重 for(int k=i+1; k<j; k++)i 循环的总次数为O(n3)。因此算法的计算时间上界 为O(η。算法所占用的空间显然为O(n2) int t= m[uk]+ m[+1il +p[i-1T pINI pI if (t <m[0D(12 i1015750787593751187515125i1011333 m00=t 026254375712510500 33 s[j=k;}4 010003500 2345 0 (a)计算次序 (c[
14 用动态规划法求最优解 public static void matrixChain(int [] p, int [][] m, int [][] s) { int n=p.length-1; for (int i = 1; i <= n; i++) m[i][i] = 0; for (int r = 2; r <= n; r++) for (int i = 1; i <= n - r+1; i++) { int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;} } } } A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025 + + = + + = + + = + + = + + = + + = = [2][4] [5][5] 4375 0 35 10 20 11375 [2][3] [4][5] 2625 1000 35 5 20 7125 [2][2] [3][5] 0 2500 35 15 20 13000 [2][5] min 1 4 5 1 3 5 1 2 5 m m p p p m m p p p m m p p p m 算法复杂度分析： 算法matrixChain的主要计算量取决于算法中对r， i和k的3重循环。循环体内的计算量为O(1)，而3重 循环的总次数为O(n3 )。因此算法的计算时间上界 为O(n3 )。算法所占用的空间显然为O(n2 )
清华大学出版社 TSINGHUA UNIVERSITY PRESS 动态规划算法的基本要素 、最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这 种性质称为最优子结构性质 在分析问题的最优子结构性质时,所用的方法具有普遍性:首 先假设由问题的最优解导岀的子问题的解不是最优的,然后再 设法说明在这个假设下可构造出比原问题最优解更好的解,从 而导致矛盾。 用问题的最优子结构性质,以自底向上的方式递归地从子问 题的最优解逐步构造岀整个问题的最优解。最优子结构是问题 能用动态规划算法求解的前提。 注意:同一个问题可以有多种方式刻划它的最优子结构,有些 表示方法的求解速度更快(空间占用小,问题的维度低)
15 动态规划算法的基本要素 一、最优子结构 •矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这 种性质称为最优子结构性质。 •在分析问题的最优子结构性质时，所用的方法具有普遍性：首 先假设由问题的最优解导出的子问题的解不是最优的，然后再 设法说明在这个假设下可构造出比原问题最优解更好的解，从 而导致矛盾。 •利用问题的最优子结构性质，以自底向上的方式递归地从子问 题的最优解逐步构造出整个问题的最优解。最优子结构是问题 能用动态规划算法求解的前提。 注意：同一个问题可以有多种方式刻划它的最优子结构，有些 表示方法的求解速度更快（空间占用小，问题的维度低）