Python 中矩阵链乘法问题的解决方法

矩阵链乘法问题是指给定n个矩阵A1,A2,……An，代价为乘法次数，如何通过加括号使得矩阵相乘的代价最小

一般解法是动态规划，定义：

M[i,j]为Ai到Aj的子矩阵链的最优乘法次数

那么M[i,i] = 0

当i < j 时，M[i,j] = min{M[i,k] + M[k+1,j] + p(i-1)p(k)p(j)}，其中k∈[i,j-1]，p为矩阵的维数

代码演示：

def matrix_chain_order(p):
n = len(p) - 1
m = [[float('inf')] * n for _ in range(n)]
s = [[0] * n for _ in range(n)]
for i in range(n):
m[i][i] = 0
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
for k in range(i, j):
q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
if q < m[i][j]:
m[i][j] = q
s[i][j] = k
return m, s

def print_optimal_parens(s, i, j):
if i == j:
print('A{}'.format(i + 1), end='')
else:
print('(', end='')
print_optimal_parens(s, i, s[i][j])
print_optimal_parens(s, s[i][j] + 1, j)
print(')', end='')

p = [2, 5, 10, 4, 8]
m, s = matrix_chain_order(p)
print_optimal_parens(s, 0, len(p) - 2) # 输出：((A1(A2A3))((A4A5)A6))