文档介绍：该【算法分析与设计矩阵连乘问题 】是由【54156456】上传分享，文档一共【41】页，该文档可以免费在线阅读，需要了解更多关于【算法分析与设计矩阵连乘问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。本章主要知识点：
矩阵连乘问题
动态规划算法的基本要素
最长公共子序列
0-1背包问题
202X
第3章 动态规划
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
算法总体思想
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
算法总体思想
01
找出最优解的性质，并刻划其结构特征。
02
递归地定义最优值。
03
以自底向上的方式计算出最优值。
04
根据计算最优值时得到的信息，构造最优解。
动态规划基本步骤
给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
3
2
1
矩阵连乘问题
完全加括号的矩阵连乘积
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积 是完全加括号的，则 可
表示为2个完全加括号的矩阵连乘积 和
的乘积并加括号，即
完全加括号的矩阵连乘积可递归地定义为：
每一种完全加括号对应于一个矩阵连乘积得计算次序，
而矩阵连乘积的计算次序与其计算量有密切的关系。
下面是计算两个矩阵乘积的标准算法：
完全加括号的矩阵连乘积
public static void matrixMultiply(double a[][], double b[][], double c[][],
int ra, int ca, int rb, int cb)
{
if(ca!=rb)
throw new IllegalArgumentException(“矩阵不可乘”);
for( int i=0;i<ra;i++)
for(int j=0;j<cb;j++)
{
int sum=a[i][0]*b[0][j];
for(int k=1;k<ca;k++)
sum=sum+a[i][k]*b[k][j];
c[i][j]=sum;
}
}
设有四个矩阵 ，它们的维数分别是：
16000, 10500, 36000, 87500, 34500
通过矩阵乘积标准算法可知：若矩阵A是 矩阵，B是
矩阵，则乘积C=AB是 矩阵，总共需要
次数乘得到。
这样可以计算每一种完全加括号方式的计算量，如
总共有五中完全加括号的方式
矩阵连乘问题
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
算法复杂度分析：
对于n个矩阵的连乘积，设其不同的计算次序为P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：
P(n)是随n的增长呈指数增长。