矩阵链乘法

1.问题

矩阵链乘法问题：
设A1,A2,…An为n个矩阵的序列，其中Ai为Pi-1×Pi阶矩阵，这个矩阵链的输入用向量P=<P0，P1…Pn>给出。给定向量P，确定一种乘法次序，使得基本运算的总次数达到最小。

例如，P=<10,100,5,50>，则A1:10×100，A2:100×5，A3:5×50，有两种结合次序，
1）(A1A2)A3：10×100×5+10×5×50=7500
2）A1(A2A3)：10×100×50+100×5×50=75000
显然第二种优于第一种。

2.解析

2.1 蛮力法

枚举所有可能的乘法次序，针对每种次序计算基本运算的次数，从中找出具有最小运算次数的乘法次序，每一种乘法次序对应了一种在n给项中加n-1对括号。

2.2 动态规划法

2.3 矩阵链乘法的实现步骤

3.设计

3.1 矩阵链乘法递归算法的伪代码：

RecurMatrixChain(P,i,j)
输入：矩阵链Ai..j的输入向量为P=<Pi-1,Pi,...,Pj>，其中1≤i≤j≤n
输出：计算Ai..j所需最小乘法运算次数m[i..j]和最后一次运算的位置s[i..j](s[i..j]=k,(Ai..Ak)(Ak+1..Aj))

1.if i=j then
2.    m[i,j]=0;s[i,j]=i;return m[i,j]
3.m[i,j]=无穷大
4.s[i,j]=i
5.for k=i to j-1 do
6.    q=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+Pi-1PkPj
7.    if q＜m[i,j]
8.        Then m[i,j]=q
9.            s[i,j]=k
10.return m[i,j]

3.2 矩阵链乘法迭代算法的伪代码：

MatriChain(P，n)
输入：矩阵链Ai..j的输入向量为P=<Pi-1,Pi,...,Pj>，其中1≤i≤j≤n
输出：计算Ai..j所需最小乘法运算次数m[i..j]和最后一次运算的位置s[i..j]

1.令所有m[i,j]初值为0，s[i,j]的初值为i，1≤i≤j≤n
2.For r=2 to n do				//r为当前问题规模（长度）
3.    For i=1 to n-r+1 do		//i的起点不断变化，各种r长
4.        j=i+r-1				//不同终点
5.        m[i,j]=m[i+1,j]+Pi-1PkPj	//划分为Ai（Ai+1...Aj）
6.        s[i,j]=i
7.        For k=i+1 to j-1 do
8.            t=m[i,k]+m[k+1,j]+ Pi-1PkPj
9.            if t<m[i,j]
10.           Then m[i,j]=t
11.               s[i,j]=k

4.分析

4.1 矩阵链乘法递归算法时间复杂度

4.2 矩阵链乘法迭代算法时间复杂度

T（n） = O（n3）

5.源码

矩阵链乘法的源码地址：
https://github.com/Ying917/Algorithm-Analysis/blob/master/matrixChain.cpp