矩阵链乘法python

矩阵链乘法是指给定n个矩阵{A1,A2,A3,...,An}，其中Ai与Ai+1是可乘的，i=1,2,3,...,n-1。将它们相乘所需的数乘次数与加法次数有很大关系，因此矩阵链乘法的问题就是如何确定矩阵相乘的顺序，使得计算所需的数乘次数最少。

以下是一个Python实现的矩阵链乘法的例子：

import sys

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * (n + 1) for i in range(n + 1)]
    s = [[0] * (n + 1) for i in range(n + 1)]
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = sys.maxsize
            for k in range(i, j):
                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

def print_optimal_parens(s, i, j):
    if i == j:
        print("A" + str(i), end="")
    else:
        print("(", end="")
        print_optimal_parens(s, i, s[i][j])
        print_optimal_parens(s, s[i][j] + 1, j)
        print(")", end="")

p = [30, 35, 15, 5, 10, 20, 25]
m, s = matrix_chain_order(p)
print_optimal_parens(s, 1, len(p) - 1)

输出结果为：((A1(A2A3))((A4A5)A6))