第3章动态规划(new).ppt

引导例子(10/10) §3.1 矩阵连乘问题 　 给定n个矩阵{A1， A2，…, An},其中Ai与Ai+1 是可乘的。考察这N个矩阵的连乘积 A1A2…An 分析： 由于矩阵乘法满足结合律，故计算矩连乘积 A1A2…An可以有多个计算次序。 例如： (A1(A2(A3A4 ))) 等等 (A1((A2A3 )A4)) ((A1A2)(A3A4)) 先考虑两个矩阵乘积的计算量 　设A为ra?ca矩阵 B为rb?cb矩阵， void matrixMultiply(int **a, int **b, int **c, int ra, int ca, int rb, int cb ) { if(ca!=rb) error(“Can’t multiply”); for(i=0; ira; ++i) for(j=0; jcb; ++j) { c[i][j] =0; for(k=0;kca; ++k) c[i][j]+=a[i][k]*b[k][j]; } } 矩连连乘的不同计算次序会导致不同的计算量 例如 {A1，A2，A3} A1 10*100 A2 100*5 A3 5*50 第1种加括号 （（A1A2）A3） 10*100*5 +10*5*50 =7500 第2种加括号 （A1（ A2A3）） 100*5*50 +10*100*50 =75000 所谓矩阵连乘问题： 　 对于给定n个矩阵{A1， A2，…, An}， 其中Ai的维数是pi-1 ? pi 如何确定计算矩阵连乘积A1A2…An的计算次序，使得计算矩阵连乘积的数乘次数最少。 方法一： 枚举所有可能的计算次序。 ? (2n / n3/2) 方法二： 动态规划。 O (n3) 第一种：矩阵连乘的递归求解方法 记 A[i:j]为 AiAi+1…Aj 考察计算A[1:n]的最优计算次序 不妨设 计算A[1:n]最优次序的最后一次乘积位置在 K 处 （（A1A2…Ak)（Ak+1…An) ) k=1,2,…n-1 其计算量为 (1)计算 A[1:k] (2)计算 A[k+1:n] (3)最后一次矩阵乘积p0?pk?pn 1.分析最优解的结构 计算A[1:n]的最优次序所包含的子链计算 A[1:k] 和 A[k+1:n]也一定是最优次序的。 事实上 若有一个计算A[1:k]的次序所需的计算量更少，则取代之。类似，计算A[k+1:n]的次序也一定是最优的。 因此，矩阵连乘计算次序问题的最优解，包含了其子问题的最优解。 2.建立递归关系，定义最优值 设计算A[i:j]所需的最少数乘次数为m[i][j] 则原问题的最优值为m[1][n] 不妨设 计算A[i:j]最优次序的最后一次乘积位置在 K 处 (（AiA2…Ak)（Ak+1…Aj)) k=i,2,…j-1 则 m[i][j]= 0 i=j MIN{m[i][k]+m[k+1][j]+pi-1pkpj } ij i=kj 3.伪码分析 算法1 RecurMatrixChain(P,i,j)1. m[i,j]←∞2. s[i,j]←i3. for k←i to j?1 do4. q←RecurMatrixChain(P,i,k) +RecurMatrixChain(P,k+1,j)+pi?1pkpj5. if q m[i,j]6. then m[i,j]←q7. s[i,j]←k8. return m[i,j]这里没有写出算法的全部描述（递归边界） 4.子问题的产生 n=5 5.子问题的计数 边界不同的子问题：15个 递归计算的子问题：81个 边界 次数 边界 次数 边界 次数 1-1 8 1-2 4 2-4 2 2-2 12 2-3 5 3-5 2 3-3 14 3-4 5 1-4 1 4-4 12 4