矩阵连乘最小计算次数

问题

$A_{2\times 10}, B_{10 \times 50}, C_{50 \times 20}​$是三个矩阵,下标表示矩阵大小。现计算$A_{2\times 10} * B_{10 \times 50} * C_{50 \times 20}​$。

  • $({\color{red}{AB}})_{2 \times 50}C_{50 \times 20}​$的计算量是${\color{red}{2 *50 *10}}+2 *20 *50=3000​$

  • $A_{2 \times 10}({\color{red}{BC}})_{10 \times 20}​$的计算量是 ${\color{red}{10 *20 *50}}+2 *20 *10=10400​$

可以观察到,不同的计算次序(在不同的地方加括号)有不同的计算量。

推广到一般情形
给定$A=A_0 * A_1* … * A_{n-1}$, 其中$A_i$的大小为: $d_i \times d_{i+1}$。选择计算顺序,使得(乘法)计算次数最小。


代码

1
2
3
4
5
6
7
8
9
10
11
12
def matrix_chain(d):
'''
d is a list: [d[0],d[1],...,d[n-1],d[n]]
return: the total number of scalar of multiplications
'''
n = len(d)-1
N = [[0]*n for _ in range(n)]
for b in range(1,n): # number of products in subchain
for i in range(n-b): # start of subchain
j = i+b
N[i][j] = min([N[i][k]+N[k+1][j]+d[i]*d[k+1]*d[j+1] for k in range(i,j)])
return N[0][n-1]

测试

1
matrix_chain([2,10,50,20])

Out: 3000

计算复杂度分析:$b,j,k$三重循环,所以为 $O(n^3)$


分析

使用动态规划(dynamic programming,DP):确定迭代公式和确定边界条件

迭代公式

设$N_{0,i}$为$A=A_0 * … *A_i$的最小计算次数

计算$A_0 * A_1* … * A_{n-1}$一定会出现这种形式$(A_0 * … A_i) * (A_{i+1} * … * A_{n-1})$。

那么$(A_0 * … A_i) * (A_{i+1} * … * A_{n-1})$的最小计算次数为:

$A$的最最小计算次数为$i$从0到n-2遍历后得到的最小计算量:

其中

  • $N_{0,i}​$的计算类似于$N_{0,n-1}​$, 具体如下:

  • $N_{i+1,n-1}$的计算公式如下:

这样就不断迭代到最基本的情况$N_{i,i}$(计算$A_i$) 和 $N_{i,i+1}$(计算$A_i A_{i+1}$)。

$A_i*A_{i+1} \cdots* A_{j}​$的最优计算次数为


边界条件

  • $N_{i,i}=0$:$A_i$不需要乘法计算
  • $N_{i,i+1}=d_i*d_{i+1}*d_{i+2}​$: 计算$A_i A_{i+1}​$

过程展示

  1. 初始化$N_{i,i}=0, \quad i=0,1,…,n-1$

  2. 计算$N_{i,i+1}\quad i=0,1,…,n-2 $

  3. 计算$N_{i,i+2} \quad i=0,1,…,n-3$

  4. $\cdots$

  5. 计算$N_{0, n}$