消除重复的矩阵连乘算法 Void Matrix Chain(int p, int n, int **m, int *xs) f for(int i=1;i<=n; i++)mli=0 ∥将对角线元素赋值为零,即单个矩阵计算量为0 for(intr=2;r<=n;r++) for(int i=l; i<=n-r+l; i++)i int i=i++r-1 (5)mi mi+1l+pi-1p*pl /计算Ai,j=AiAi+1:能(5是 s[训j]=i;∥记下断点i (7 for (int k=i+l; k<j; k++)t 能畬噔確赋祤值。 int t=milk+ m[k+1l+ pli-1splk pll kj,逐个计算A[ij=A[i:k]Ak+1:j if(t< mi[([jl=t;sl=k; 5 记下较小的m[订及相应的断点k 算法设计与分析
算法设计与分析 11 消除重复的矩阵连乘算法 ◼ Void MatrixChain(int p, int n, int **m, int **s) ◼ { for (int i = 1; i <= n; i++) m[i][i] = 0; ◼ //将对角线元素赋值为零，即单个矩阵计算量为0 ◼ for (int r = 2; r <= n; r++) ◼ for (int i = 1; i <= n – r +1; i++) { ◼ int j = i + r – 1; ◼ (5) m[i][j] = m[i+1][j] + p[i–1]*p[i]*p[j]; ◼ //计算A[i, j] = A[i: i] A[i+1: j] ◼ s[i][j] = i; //记下断点i ◼ (7) for (int k = i + 1; k < j; k++) { ◼ int t = m[i][k] + m[k+1][j] + p[i–1]*p[k]*p[j]; ◼ //对i<k<j, 逐个计算A[i, j] = A[i: k] A[k+1: j] ◼ if (t < m[i][j]) {m[i][j] = t; s[i][j] = k;} ◼ //记下较小的m[i][j]及相应的断点k ◼ }}} 第(5)步与第(7)步 能否合在一起? 能。此处分开是为 了给m[i][j]赋初值
Matrix chain的运行举例 由m[l6=15125可知这6个矩阵连乘积的最小运算次数为 15125。由s[6=3可知A[1:6]的最优计算次序为A[1:3] A[4:6];由s[l]B3]=1可知A1:3]的最优计算次序为A[1:1] A[2:3];由s[46]=5可知A4:6]的最优计算次序为A[4:5] A[6:6];因此最优计算次序为:(A1(A243)(A4As)A6)。 2 3 5 123 56 15%5078%59375m875|1525 333 26254375712510500 233|3 7025005353 333 4 milll 01600|3500 930005 算法设计与分析 12
算法设计与分析 12 MatrixChain的运行举例 设要计算矩阵连乘积A1A2A3A4A5A6，其维数分别 为35×35, 35×15, 15×5, 5×10, 10×20, 20×25, 即p0=35, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。 MatrixChain用矩阵m[i][j], s[i][j]存放子问题A[i: j] 的最小计算量以及相应的断点。 1 2 3 4 5 6 1 2 3 4 5 6 m[i][j] 1 2 3 4 5 6 1 2 3 4 5 6 s[i][j] MatrixChain将如下面红色箭头所示的过程逐个计算 子问题A[i: j]： 执行for (int i = 1; i <= n; i++) m[i][i] = 0后将对角线元素全 部置零，即子问题A[i][i] = 0。 0 0 0 0 0 0 当r=2，执行第(5)句完成了相邻矩阵A[i][i+1]=p[i–1]*p[i]*p[j] 的计算，并在s[i][j]中添入了相应的断点。其中的第(7)句因 为j = i+1(k=i+1)而被跳过去了，实际并没有执行。 15750 2625 750 1000 5000 1 2 3 4 5 当r=3，i=1时，执行第(5)句计算A[1:1][2:3]， m[1][3] = m[2][3] + p[0]*p[1]*p[3] = 2625 +30*35*5 = 7875 7875 1 执行第(7)句计算A[1:2][3:3]， t = m[1][2] + m[3][3] + p[0]*p[2]*p[3] = 15750+0+35*15*5 = 18375＞7875，所以 m[1][3]不变，断点仍为1。 当r=3，i=2时，执行第(5)句计算A[2:2][3:4]，m[2][4] = m[3][4] + p[1]*p[2]*p[4] = 750 +35*15*10 = 6000 6000 2 执行第(7)句计算A[2:3][4:4]， t = m[2][3]+m[4][4]+ p[1]*p[3]*p[4] = 2625+0+35*5*10 = 4375＜6000，所以 m[2][4]改为4375，断点改为3。 4375 3 当r=3，i=3时，执行第(5)句计算A[3:3][4:5]，m[3][5] = m[4][5] + p[2]*p[3]*p[5] = 1000 +15*5*20 = 2500 2500 3 执行第(7)句计算A[3:4][5:5]， t = m[3][4]+m[5][5]+ p[2]*p[4]*p[5] = 750+0+15*10*20 = 3750＞2500，所以 m[3][5]仍为2500，断点仍为3。 当r=3，i=4时，执行第(5)句计算A[4:4][5:6]，m[4][6] = m[5][6] + p[3]*p[4]*p[6] = 5000 +5*10*25 = 6250 6250 4 执行第(7)句计算A[4:5][6:6]， t = m[4][5]+m[6][6]+ p[3]*p[5]*p[6] = 1000+0+5*20*25 = 3500＜6250，所以 m[4][6]改为3500，断点改为5。 3500 5 类似的，当r=4、5、6时，可以计算出相应的m[i][j]及其相 应的断点s[i][j]，如下图中所示： 9375 3 7125 3 5375 3 11875 3 10500 3 15125 3 由m[1][6]=15125可知这6个矩阵连乘积的最小运算次数为 15125。由s[1][6] = 3可知A[1: 6]的最优计算次序为A[1: 3] A[4: 6]；由s[1][3]=1可知A[1: 3]的最优计算次序为A[1: 1] A[2: 3]；由s[4][6]=5可知A[4: 6]的最优计算次序为A[4: 5] A[6: 6]；因此最优计算次序为：(A1 (A2A3 ))((A4A5 )A6 )
Matrix chain的时间复杂性 ■算法 MatrixChain的主要计算取决于程序 中对r、ik的三重循环。循环体内的计 算量为O(1),1≤r、i、k<n,三重循环的 总次数为O(n)。因此该算法时间复杂性 的上界为O(n3),比直接递归算法要有效 得多。算法使用空间显然为O(n2) ■这种算法称为动态规划。 算法设计与分析 13
算法设计与分析 13 MatrixChain的时间复杂性 ◼ 算法MatrixChain的主要计算取决于程序 中对r、i和k的三重循环。循环体内的计 算量为O(1)，1≤ r、i、k≤n，三重循环的 总次数为O(n3 )。因此该算法时间复杂性 的上界为O(n3 )，比直接递归算法要有效 得多。算法使用空间显然为O(n2 )。 ◼ 这种算法称为动态规划
动态规划的基本思想 ■将原问题分解为若干个子问题,先求子问题的 解,然后从这些子问题的解得到原问题的解 这些子问题的解往往不是相互独立的。在求解 的过程中,许多子问题的解被反复地使用。为 了避免重复计算,动态规划算法采用了填表来 保存子问题解的方法 在算法中用表格来保存已经求解的子问题的解, 无论它是否会被用到。当以后遇到该子问题时 即可查表取出其解,避免了重复计算。 算法设计与分析
算法设计与分析 14 动态规划的基本思想 ◼ 将原问题分解为若干个子问题，先求子问题的 解，然后从这些子问题的解得到原问题的解。 ◼ 这些子问题的解往往不是相互独立的。在求解 的过程中，许多子问题的解被反复地使用。为 了避免重复计算，动态规划算法采用了填表来 保存子问题解的方法。 ◼ 在算法中用表格来保存已经求解的子问题的解， 无论它是否会被用到。当以后遇到该子问题时 即可查表取出其解，避免了重复计算
动态规划的基本要素 ■最优子结构:问题的最优解是由其子问题的最 优解所构成的。 最优子结构性质使我们能够以自底向上的方式 递归地从子结构的最优解构造出问數的最优解。 重叠子问题:子问题之间并非相互独立的,而 是彼此有重叠的 因为子问题重叠,所以存在着重复计算。这样 就可以用表保存子问题解的方法来提高数率。 算法设计与分析 15
算法设计与分析 15 动态规划的基本要素 ◼ 最优子结构：问题的最优解是由其子问题的最 优解所构成的。 ◼ 重叠子问题：子问题之间并非相互独立的，而 是彼此有重叠的。 最优子结构性质使我们能够以自底向上的方式 递归地从子结构的最优解构造出问题的最优解。 因为子问题重叠，所以存在着重复计算。这样 就可以用填表保存子问题解的方法来提高效率