山东理工大学：《计算机算法设计与分析》课程教学课件（PPT讲稿）第三章 动态规划 Dynamic Programming

归本程子末军 2.1问题定义 SHANDONG UNIVERSITY OF TECINOLOGY 华器会空空合安会空会的会 ●矩阵连乘法的代价与计算顺序的关系 ■棱A=10×100矩阵，A2=100x5矩阵，A3=5×50矩 阵 T(A1×A2)×A3)=10×100×5+10×5×50=7500 T(A1×(A2×A3)=100×5×50+10×100x50=75000 结论：不同计具收序有不同的代价 2025年4月3日 16

2025年4月3日 16 2.1 问题定义 ⚫ 矩阵连乘法的代价与计算顺序的关系 ◼设A1 =10100矩阵, A2 =1005矩阵, A3 =550矩 阵 T((A1A2 )A3 )=101005+10550=7500 T(A1(A2A3 ))=100550+1010050=75000 结论: 不同计算顺序有不同的代价！

山东程子太置 HANDONG UNIVERSITY OF TECINOLOGY 会是3会33 设有四个矩阵A,B,C,们的维数分别是： A=50×10B=10×40C=40×30D=30×5 总共有五中完全加括号的方式 (A((BC)D)) (A(B(CD)) ((AB(CD)) (((AB)C)D) ((A(BC)D) 16000,10500,36000,87500,34500 采同计算顺序有采同的代价/ 2025年4月3日

2025年4月3日 17 A, B,C, D A= 5010 B =1040 C = 4030 D = 305 (A((BC)D)) ((( AB)C)D) ((A(BC))D) (A(B(CD))) ((AB)(CD)) 16000, 10500, 36000, 87500, 34500 ◆ 设有四个矩阵 ，它们的维数分别是： ◆总共有五中完全加括号的方式 不同计算顺序有不同的代价！

矩阵连乘问题 归本程子末军 SHANDONG UNIVERSITY OF TECHNOLOGY 给定n个矩阵{A,A,2,募钟与是可乘的， 考察这个矩阵的连乘积 442.An 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许 多不同的计算次序。这种计算次序可以用加括号的方式来 确定。 。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘 积已完全加括号，则可以依此次序反复调用2个矩阵相乘的 标准算法计算出矩阵连乘积 2025年4月3日 18

2025年4月3日 18 矩阵连乘问题 ⚫ 给定n个矩阵 ， 其中 与 是可乘的， 。 考察这n个矩阵的连乘积 ⚫ 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许 多不同的计算次序。这种计算次序可以用加括号的方式来 确定。 ⚫ 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘 积已完全加括号，则可以依此次序反复调用2个矩阵相乘的 标准算法计算出矩阵连乘积 { , ,., } A1 A2 An Ai Ai+1 i =1,2,.,n −1 A A An . 1 2

白东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 矩阵连乘问题 给定n个矩阵{A1,A2,An},其中Ai与Ai+1 是可乘的，i=1,2.,n-1。如何确定计算矩 阵连乘积的计算次序，使得依此次序计算矩阵连 乘积需要的数乘次数最少。 ◆穷举法：列举出所有可能的计算次序，并计算 出每一种计算次序相应需要的数乘次数，从中找 出一种数乘次数最少的计算次序。 2025年4月3日 19

2025年4月3日 19 矩阵连乘问题 给定n个矩阵｛A1,A2,.,An｝，其中Ai与Ai+1 是可乘的，i=1，2.，n-1。如何确定计算矩 阵连乘积的计算次序，使得依此次序计算矩阵连 乘积需要的数乘次数最少。 ◆穷举法：列举出所有可能的计算次序，并计算 出每一种计算次序相应需要的数乘次数，从中找 出一种数乘次数最少的计算次序

归本程上太军 2.2矩阵连乘问题的解空间 SHANDONG UNIVERSITY OF TECHNOLOGY 会会是会会8会 ●设p)=计算n个矩阵乘积的不同计算次序 ●pn)的递方程： (A x.xAx(Ak+ix.XA p(n= 1 if n=1 p(= ∑pk)pn-k) if n>1 k= p-(a-Cata数=20=e(e公y 品比之大的解空同是元依用牧举方依本化景优解的/ 2025年4月3日 20

2025年4月3日 20 p(n)= 1 if n=1 p(n)= if n>1 p(n)=C(n-1)=Catalan数= = (4 n /n 3/2 ) ⚫ 设p(n)=计算n个矩阵乘积的不同计算次序 ⚫ p(n)的递归方程： p k p n k k n ( ) ( − ) = −  1 1 （A1 . Ak )(Ak+1.An )         − − 1 1 2( 1) n n n 如此之大的解空间是无法用枚举方法求出最优解的！ 2.2 矩阵连乘问题的解空间