清华大学出版社 TSINGHUA UNIVERSITY PRESS 矩阵连乘问题 给定n个矩阵{A1,A2…,An},其中A与A1+1是可乘的 ⅰ=1,2灬…,n-1。如何确定计算矩阵连乖积的计算次序,使得 依此次序计算矩阵连乘积需要的数乘次数最少。 ◆穷举法:列举出所有可能的计算次序,并计算出每一种计 算次序相应需要的数乘次数,从中找出一种数乘次数最少的 计算次序。 算法复杂度分析: 对于n个矩阵的连乘积,设其不同的计算次序为P(n) 由于每种加括号方式都可以分解为两个子矩阵的加括号问题 (A1…Ak)(Ak+1.A1)可以得到关于P(n)的递推式如下: n=1 P(m)=1>P(k)P(n-k)n>1 P(n)=92(4"/n2) k=19 矩阵连乘问题 给定n个矩阵｛A1 ,A2 ,…,An｝，其中Ai与Ai+1是可乘的， i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得 依此次序计算矩阵连乘积需要的数乘次数最少。 ◆穷举法：列举出所有可能的计算次序，并计算出每一种计 算次序相应需要的数乘次数，从中找出一种数乘次数最少的 计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1 ...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： ( ) (4 / ) 1 1 ( ) ( ) 1 ( ) 1 3/ 2 1 P n n n n P k P n k P n n n k  =       = − =  − =