算法分析与设计-作业8 矩阵链的乘法

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. 解析

动态规划法
Ai…j:表示矩阵链相乘的子问题AiAi+1…Aj;
m[i…j]:表示得到乘积Ai…j所用的最少基本运算次数；
假定，最后一次相乘发生在矩阵链Ai…k和Ak+1…j之间，即
AiAi+1…Aj=(AiAi+1…Ak)×(Ak+1Ak+2…Aj) k=I,i+1,…,j-1
e.g. Ai(Ai+1…Aj);(AiAi+1)(Ai+2…Aj);…;(AiAi+1Ai+2…)(Aj-1Aj);(AiAi+1Ai+2…Aj-1)Aj
0 i=j
m[i…j]={
min{m[I,k]+m[k+1,j]+Pi=1PkPj}(i<=k<j) i<j
其中Ai=Pi-1×Pi,Ak=Pk-1×Pk,Aj=Pj-1×Pj
AiAi+1…Aj=(AiAi+1…Ak)(Ak+1Ak+2…Aj)
→(Pi-1Pk)(PkPj)
→Pi-1PkPj
命题m[i…j]= min{m[I,k]+m[k+1,j]+Pi=1PkPj}(i<=k<j) 满足优化原则，即m[i…j]最小值时，m[i,k]和m[k+1,j]也是最小的。

3.设计

MatrixChain(P,n)
输入：矩阵链A1..n的输入为向量P=<P0,P1,...,Pn>
输出：计算Ai..j的所需最小乘法运算此时m[i,j]和最后一次运算的位置s[i,j],1≤i≤j≤n
令所有的m[i,j]初值为0，s[i,j]初值为i,1≤i≤j≤n
for r=2 to n do　　　　//r为当前问题规模（长度）
    for i=1 to n-r+1 do　　　　//i的起点不断变化，各种r长
        j=i+r-1　　　　　//不同终点
        m[i,j]=m[i+1,j]+Pi-1*Pi*Pj　　//划分为Ai(Ai+1···Aj)
        s[i][j]=i　 
        for k=i+1 to j-1 do//不同的划分位置
            t=m[i,k]+m[k+1,j]+Pi-1*Pk*Pj　 
            if t＜m[i,j]　　　　  
            then m[i,j]=t
                    s[i,j]=k

示例
P=<35,40,15,5,50,20>,n=5
A1:35×40
A2:40×15
A3:15×5
A4:5×50
A5:50×20
(1) r=1
m[1,1]=0;
m[2,2]=0;
m[3,3]=0;
m[4,4]=0;
m[5,5]=0;
(2) r=2,i=1,2,3,4;j=2,3,4,5
m[1,2]=35×40×15=21000;
m[2,3]=40×15×5=3000;
m[3,4]=15×5×50=3750;
m[4,5]=5×50×20=5000;
(3) r=3,i=1,2,3;j=3,4,5;
m[1,3]=min{m[1,2]+m[3,3]+(A1A2)A3,m[1,1]+m[2,3]+A1(A2A3)};s[1,3]=1
m[2,4]=min{m[2,3]+m[4,4]+(A2A3)A4,m[2,2]+m[3,4]+A2(A3A4)};s[2,4]=3
m[3,5]=min{m[3,4]+m[5,5]+(A3A4)A5,m[3,3]+m[4,5]+A3(A4A5)};s[3,5]=3
(4) r=4,i=1,2;j=4,5
m[1,4]=min{m[1,1]+m[2,4]+A1(A2A3A4),m[1,2]+m[3,4]+(A1A2)(A3A4),m[1,3]+m[4,4]+(A1A2A3)A4};s[1,4]=3
m[2,5]=min{m[2,2]+m[3,5]+A2(A3A4A5),m[2,3]+m[4,5]+(A2A3)(A4A5),m[2,4]+m[5,5]+(A2A3A4)A5};s[2,5]=3
(5) r=5,i=1;j=5
m[1,5]=min{m[1,1]+m[2,5]+A1(A2A3A4A5),m[1,2]+m[3,5]+(A1A2)(A3A4A5),m[1,3]+m[4,5]+(A1A2A3)(A4A5),m[1,4]+m[5,5]+(A1A2A3A4)A5}; s[1,5]=3
s[1,5]=3 (A1A2A3)(A4A5)
s[1,3]=1 A1(A2A3);
(A1(A2A3))(A4A5)

4.分析

T(n)=O(n^3)

5.源码

https://github.com/samfsrhv920/algorithm-analysis