矩阵连乘问题 3 问题描述 给定n个矩阵：{A1,A2,,An},其中A与A+1可乘 求解这n个矩阵的连乘积：A1A2.An ·问题：矩阵乘法满足结合率，因此矩阵连乘有多种计算次序 问题分析 通过加括号的方式可以确定矩阵连乘问题的计算次序 若矩阵连乘的计算次序完全确定，则称该连乘积已完全加括号 可以按计算次序反复调用两个矩阵相乘的标准算法求解 风 完全加括号的矩阵连乘积可递归定义如下： ·单个矩阵是完全加括号的 矩阵连乘积A是完全加括号的，则A可以表示为两个完全加 括号的矩阵连乘积B和C的乘积并加括号，即：A=(BC)
矩阵连乘问题 问题描述 给定n个矩阵：{A1 , A2 , ……, An }，其中Ai与Ai+1可乘 求解这n个矩阵的连乘积： A1A2…… An 问题：矩阵乘法满足结合率，因此矩阵连乘有多种计算次序 问题分析 通过加括号的方式可以确定矩阵连乘问题的计算次序 若矩阵连乘的计算次序完全确定，则称该连乘积已完全加括号 • 可以按计算次序反复调用两个矩阵相乘的标准算法求解 完全加括号的矩阵连乘积可递归定义如下： • 单个矩阵是完全加括号的 • 矩阵连乘积A是完全加括号的，则A可以表示为两个完全加 括号的矩阵连乘积B和C的乘积并加括号，即：A = (BC)
完全加括号的矩阵连乘积 R 设有四个矩阵：A50x10,B10x40,C40x30,D30x5 3连乘积ABCD总共有五种完全加括号的方式 (A((BC)D)) 计算次数：16000 (A(B(CD))) 计算次数：10500 ((AB)(CD)) 计算次数：36000 (((AB)C)D) 计算次数：87500 ((A(BC))D) 计算次数：34500 计算次数（以①为例） NBg=10x40x30=12000; N(BCD)=10x30x5=1500; Φ Na(BCD)=50x10x5=2500 N包=12000+1500+2500=16000
完全加括号的矩阵连乘积 设有四个矩阵：A50x10，B10x40，C40x30，D30x5 连乘积ABCD总共有五种完全加括号的方式 ① （A（（BC）D）） ② （A（B（CD））） ③ （（AB）（CD）） ④ （（（AB）C）D） ⑤ （（A（BC））D） 计算次数（以 ① 为例） N(BC)= 10x40x30=12000 ； N((BC)D)= 10x30x5=1500； N(A((BC)D))= 50x10x5=2500 N⑴ = 12000 + 1500 + 2500 = 16000 …… 计算次数：16000 计算次数：10500 计算次数：36000 计算次数：87500 计算次数：34500
矩阵连乘问题 3 问题描述 给定n个矩阵：{A1,A2,,An},其中A与A+1可乘 ⊕ 求解这n个矩阵的连乘积：AA2…An 问题：如何确定计算矩阵连乘积的计算次序 ⊕ 使得依此次序计算矩阵连乘积需要的数乘次数最少？ RR 解决方案1：穷举法 列举出所有可能的计算次序，从中找出数乘次数最少的次序 算法复杂度分析：设n个矩阵连乘积可能的计算次序总数为P() 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1.Ak)(Ak+1An),可以得到关于P(n)的递推式如下 n=l P(n)={ ∑P)Pn-k) P(n)=2(4"/n32) n>1
矩阵连乘问题 问题描述 给定n个矩阵：{A1 , A2 , ……, An }，其中Ai与Ai+1可乘 求解这n个矩阵的连乘积： A1A2…… An 问题：如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少？ 解决方案1：穷举法 列举出所有可能的计算次序，从中找出数乘次数最少的次序 算法复杂度分析：设n个矩阵连乘积可能的计算次序总数为P(n) 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1 ...Ak )(Ak+1…An )，可以得到关于P(n)的递推式如下 3/2 1 1 1 1 ( ) ( ) (4 / ) ( ) ( ) 1 n n k n P n P n n P k P n k n − = = = = −
卡特兰数 Φ 卡特兰数(Catalan number),是组合数学中一个常出现在各 种计数问题中的数列。 Φ其前几项为： 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012, 742900,2674440,9694845,35357670,129644790,477638700, 1767263190,6564120420,24466267020,91482563640, 343059613650,1289904147324,4861946401452,. 卡特兰数h(n)满足以下递推关系： h(n)=h(0)h(n-1)+h(1)h(n-2)+.+h(n-1)h(0) (n≥2，h=1,h=1) 通项：h(n)=C(2n,n)/(n+1)=C(2n,n)-C(2n,n-1) (n=0,1,2,.…)
卡特兰数（Catalan number），是组合数学中一个常出现在各 种计数问题中的数列。 其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ... 卡特兰数 h(n) 满足以下递推关系： 卡特兰数 0 1 ( ) (0) ( 1) (1) ( 2) ( 1) (0) ( 2, 1, 1) = − + − + + − = = h n h h n h h n h n h n h h ( ) (2 , ) ( 1)= (2 , ) - (2 , 1) (n=0,1,2, ) 通项： h n C n n n C n n C n n = + −
矩阵连乘问题 R 解决方案2：动态规划法 应用动态规划，首先应分析问题的最优解结构特征 $将矩阵连乘积(AA+1A)简记为A[ij] Φ考察计算A[1:n]的最优计算次序： 设最优计算次序在Ak和Ak+1之间将矩阵链断开（1≤k<n) 则相应的完全加括号方式为：(A1…Ak)(Ak+1.An) 总计算量为如下三部分计算量之和： 求解A[1:k]的计算量 求解A[k+1:n]的计算量 求解A[1:k]和A[k+1:n]相乘的计算量
矩阵连乘问题 解决方案2：动态规划法 应用动态规划，首先应分析问题的最优解结构特征 将矩阵连乘积 (Ai Ai+1 … Aj) 简记为A[i:j] 考察计算A[1:n]的最优计算次序： • 设最优计算次序在Ak和Ak+1之间将矩阵链断开（1≤k<n） • 则相应的完全加括号方式为： (A1 … Ak ) (Ak+1 … An ) • 总计算量为如下三部分计算量之和： – 求解A[1:k]的计算量 – 求解A[k+1:n]的计算量 – 求解A[1:k]和A[k+1:n]相乘的计算量