矩阵连乘问题 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 − =   = =  =   −    