矩阵连乘问题

问题建模

设维度数组 P=⟨p0,p1,…,pn⟩P=\langle p_0,p_1,\dots,p_n\rangle ，其中AiA_i的尺寸为 pi−1×pip_{i-1}\times p_i​。

状态定义

m[i][j]m[i][j]：把子链Ai⋯AjA_i\cdots A_j 相乘所需的最少标量乘法次数（记为“备忘录/最优值表”）。
s[i][j]s[i][j]：达到最优时的分割位置 kk（记为“标记函数/决策表”）。

边界
m[i][i]=0m[i][i]=0（单个矩阵无需乘法）。

状态转移方程

当i<ji<j 时，在所有断点 k∈[i, j−1]k\in[i,\,j-1] 里取最好：

m[i][j]=min⁡i≤k<j(m[i][k]+m[k+1][j]+pi−1 pk pj)m[i][j]=\min_{i\le k<j}\Big(m[i][k]+m[k+1][j]+p_{i-1}\,p_k\,p_j\Big)

并记录取得最小值的 kk 到 s[i][j]s[i][j]。

伪代码

MatrixChainOrder(p[0..n]):
    for i = 1..n:
        m[i][i] = 0
    for L = 2..n:                       // 子链长度
        for i = 1..n-L+1:
            j = i + L - 1
            m[i][j] = +∞
            for k = i..j-1:
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s

复杂度

时间复杂度： O(n3)\mathcal{O}(n^3)

空间复杂度： O(n2)\mathcal{O}(n^2)

带入实例构造表格

给定 P=⟨50,10,40,30,5,20,15⟩，n=6P=\langle 50,10,40,30,5,20,15\rangle，n=6
各矩阵尺寸：

A1:50×10, A2:10×40, A3:40×30, A4:30×5, A5:5×20, A6:20×15A1:50×10, A2:10×40, A3:40×30, A4:30×5, A5:5×20, A6:20×15

最优值表M

i\j

1

2

3

4

5

6

1

0

20000

27000

10500

15500

15750

2

0

12000

8000

9000

10250

3

0

6000

10000

10500

4

0

3000

3750

5

0

1500

6

0

分割表S（记录最优值k）

i\j

1

2

3

4

5

6

1

-

1

1

1

4

4

2

-

2

2

4

4

3

-

3

4

4

4

-

4

4

5

-

5

6

-

Length L=2:m1,2=50⋅10⋅40=20000,m2,3=10⋅40⋅30=12000,m3,4=40⋅30⋅5=6000,m4,5=30⋅5⋅20=3000,m5,6=5⋅20⋅15=1500.\textbf{Length }L=2:\quad \\ \begin{aligned} m_{1,2}&=50\cdot10\cdot40=20000,\\ m_{2,3}&=10\cdot40\cdot30=12000,\\ m_{3,4}&=40\cdot30\cdot5=6000,\\ m_{4,5}&=30\cdot5\cdot20=3000,\\ m_{5,6}&=5\cdot20\cdot15=1500. \end{aligned}
Length L=3:m1,3=min⁡{m1,1+m2,3+p0p1p3,m1,2+m3,3+p0p2p3}=min⁡{0+12000+50⋅10⋅30,20000+0+50⋅40⋅30}=min⁡{27000,80000}=27000,m2,4=min⁡{m2,2+m3,4+p1p2p4,m2,3+m4,4+p1p3p4}=min⁡{0+6000+10⋅40⋅5,12000+0+10⋅30⋅5}=min⁡{8000,13500}=8000,m3,5=min⁡{m3,3+m4,5+p2p3p5,m3,4+m5,5+p2p4p5}=min⁡{0+3000+40⋅30⋅20,6000+0+40⋅5⋅20}=min⁡{27000,10000}=10000,m4,6=min⁡{m4,4+m5,6+p3p4p6,m4,5+m6,6+p3p5p6}=min⁡{0+1500+30⋅5⋅15,3000+0+30⋅20⋅15}=min⁡{3750,12000}=3750.\textbf{Length }L=3:\quad \\ \begin{aligned} m_{1,3}&=\min\left\{ \begin{aligned} & m_{1,1}+m_{2,3}+p_0p_1p_3, && m_{1,2}+m_{3,3}+p_0p_2p_3 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+12000+50\cdot10\cdot30, && 20000+0+50\cdot40\cdot30 \end{aligned}\right\}\\ &=\min\{27000,80000\}=27000,\\[6pt] m_{2,4}&=\min\left\{ \begin{aligned} & m_{2,2}+m_{3,4}+p_1p_2p_4, && m_{2,3}+m_{4,4}+p_1p_3p_4 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+6000+10\cdot40\cdot5, && 12000+0+10\cdot30\cdot5 \end{aligned}\right\}\\ &=\min\{8000,13500\}=8000,\\[6pt] m_{3,5}&=\min\left\{ \begin{aligned} & m_{3,3}+m_{4,5}+p_2p_3p_5, && m_{3,4}+m_{5,5}+p_2p_4p_5 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+3000+40\cdot30\cdot20, && 6000+0+40\cdot5\cdot20 \end{aligned}\right\}\\ &=\min\{27000,10000\}=10000,\\[6pt] m_{4,6}&=\min\left\{ \begin{aligned} & m_{4,4}+m_{5,6}+p_3p_4p_6, && m_{4,5}+m_{6,6}+p_3p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+1500+30\cdot5\cdot15, && 3000+0+30\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{3750,12000\}=3750. \end{aligned}
Length L=4:m1,4=min⁡{m1,1+m2,4+p0p1p4,m1,2+m3,4+p0p2p4,m1,3+m4,4+p0p3p4}=min⁡{0+8000+50⋅10⋅5,20000+6000+50⋅40⋅5,27000+0+50⋅30⋅5}=min⁡{10500,36000,34500}=10500,m2,5=min⁡{m2,2+m3,5+p1p2p5,m2,3+m4,5+p1p3p5,m2,4+m5,5+p1p4p5}=min⁡{0+10000+10⋅40⋅20,12000+3000+10⋅30⋅20,8000+0+10⋅5⋅20}=min⁡{18000,21000,9000}=9000,m3,6=min⁡{m3,3+m4,6+p2p3p6,m3,4+m5,6+p2p4p6,m3,5+m6,6+p2p5p6}=min⁡{0+3750+40⋅30⋅15,6000+1500+40⋅5⋅15,10000+0+40⋅20⋅15}=min⁡{21750,10500,22000}=10500.\textbf{Length }L=4:\quad \\ \begin{aligned} m_{1,4}&=\min\left\{ \begin{aligned} & m_{1,1}+m_{2,4}+p_0p_1p_4, && m_{1,2}+m_{3,4}+p_0p_2p_4,\\ &&& m_{1,3}+m_{4,4}+p_0p_3p_4 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+8000+50\cdot10\cdot5, && 20000+6000+50\cdot40\cdot5,\\ &&& 27000+0+50\cdot30\cdot5 \end{aligned}\right\}\\ &=\min\{10500,36000,34500\}=10500,\\[6pt] m_{2,5}&=\min\left\{ \begin{aligned} & m_{2,2}+m_{3,5}+p_1p_2p_5, && m_{2,3}+m_{4,5}+p_1p_3p_5,\\ &&& m_{2,4}+m_{5,5}+p_1p_4p_5 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+10000+10\cdot40\cdot20, && 12000+3000+10\cdot30\cdot20,\\ &&& 8000+0+10\cdot5\cdot20 \end{aligned}\right\}\\ &=\min\{18000,21000,9000\}=9000,\\[6pt] m_{3,6}&=\min\left\{ \begin{aligned} & m_{3,3}+m_{4,6}+p_2p_3p_6, && m_{3,4}+m_{5,6}+p_2p_4p_6,\\ &&& m_{3,5}+m_{6,6}+p_2p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+3750+40\cdot30\cdot15, && 6000+1500+40\cdot5\cdot15,\\ &&& 10000+0+40\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{21750,10500,22000\}=10500. \end{aligned}
Length L=5:m1,5=min⁡{m1,1+m2,5+p0p1p5,m1,2+m3,5+p0p2p5,m1,3+m4,5+p0p3p5,m1,4+m5,5+p0p4p5}=min⁡{0+9000+50⋅10⋅20,20000+10000+50⋅40⋅20,27000+3000+50⋅30⋅20,10500+0+50⋅5⋅20}=min⁡{19000,70000,60000,15500}=15500,m2,6=min⁡{m2,2+m3,6+p1p2p6,m2,3+m4,6+p1p3p6,m2,4+m5,6+p1p4p6,m2,5+m6,6+p1p5p6}=min⁡{0+10500+10⋅40⋅15,12000+3750+10⋅30⋅15,8000+1500+10⋅5⋅15,9000+0+10⋅20⋅15}=min⁡{16500,20250,10250,12000}=10250.\textbf{Length }L=5:\quad \\ \begin{aligned} m_{1,5}&=\min\left\{ \begin{aligned} &m_{1,1}+m_{2,5}+p_0p_1p_5, && m_{1,2}+m_{3,5}+p_0p_2p_5,\\ &m_{1,3}+m_{4,5}+p_0p_3p_5, && m_{1,4}+m_{5,5}+p_0p_4p_5 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} &0+9000+50\cdot10\cdot20, && 20000+10000+50\cdot40\cdot20,\\ &27000+3000+50\cdot30\cdot20, && 10500+0+50\cdot5\cdot20 \end{aligned}\right\}\\ &=\min\{19000,70000,60000,15500\}=15500,\\[6pt] m_{2,6}&=\min\left\{ \begin{aligned} &m_{2,2}+m_{3,6}+p_1p_2p_6, && m_{2,3}+m_{4,6}+p_1p_3p_6,\\ &m_{2,4}+m_{5,6}+p_1p_4p_6, && m_{2,5}+m_{6,6}+p_1p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} &0+10500+10\cdot40\cdot15, && 12000+3750+10\cdot30\cdot15,\\ &8000+1500+10\cdot5\cdot15, && 9000+0+10\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{16500,20250,10250,12000\}=10250. \end{aligned}
Length L=6:m1,6=min⁡{m1,1+m2,6+p0p1p6,m1,2+m3,6+p0p2p6,m1,3+m4,6+p0p3p6,m1,4+m5,6+p0p4p6,m1,5+m6,6+p0p5p6}=min⁡{0+10250+50⋅10⋅15,20000+10500+50⋅40⋅15,27000+3750+50⋅30⋅15,10500+1500+50⋅5⋅15,15500+0+50⋅20⋅15}=min⁡{17750,60500,53250,15750,30500}=15750.\textbf{Length }L=6:\quad \\ \begin{aligned} m_{1,6}&=\min\left\{ \begin{aligned} &m_{1,1}+m_{2,6}+p_0p_1p_6, && m_{1,2}+m_{3,6}+p_0p_2p_6,\\ &m_{1,3}+m_{4,6}+p_0p_3p_6, && m_{1,4}+m_{5,6}+p_0p_4p_6,\\ &&& m_{1,5}+m_{6,6}+p_0p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} &0+10250+50\cdot10\cdot15, && 20000+10500+50\cdot40\cdot15,\\ &27000+3750+50\cdot30\cdot15, && 10500+1500+50\cdot5\cdot15,\\ &&& 15500+0+50\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{17750,60500,53250,15750,30500\}=15750. \end{aligned}

所以：

m[1][6]=15750m[1][6]=15750

这“15750”就是整条矩阵链 A1A2A3A4A5A6A_1A_2A_3A_4A_5A_6​ 的最小乘法次数。

同时，从上面的比较我们还能读出最优切法是 k=4，也就是先算 (A1A2A3A4)(A_1A_2A_3A_4) 和 (A5A6)(A_5A_6) 各自最优，然后把它们乘起来。继续往下递归会得到括号：

((A1(A2(A3A4)))(A5A6))((A_1 (A_2 (A_3 A_4))) (A_5 A_6))