python矩阵连乘_python动态规划解决矩阵连乘
时间: 2023-07-13 11:39:39 浏览: 147
abc.rar_ABC_multiplicative_site:www.pudn.com
矩阵连乘问题就是给定一系列矩阵,求它们相乘的最少次数。这个问题可以使用动态规划来解决。
我们可以定义一个二维数组m[i][j]来表示矩阵Ai到Aj的最少次数,其中i<=j。对于任意的i和j,m[i][j]的值可以通过以下递推式计算出来:
m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]},其中i<=k<j,p[i-1]表示第i个矩阵的行数,p[j]表示第j个矩阵的列数。
这个递推式的意思是,我们把矩阵Ai到Aj分成两部分,即Ai到Ak和Ak+1到Aj,然后对它们分别进行矩阵乘法,最终得到整个矩阵链的乘积。我们需要遍历所有可能的k,选择乘积最小的那个。
最终的答案就是m[1][n-1],其中n表示矩阵的个数。
下面是Python代码实现:
```python
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), 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(m[0][len(p)-2])
print_optimal_parens(s, 0, len(p)-2)
```
这个代码的输出结果是:
```python
15125
((A1(A2A3))((A4A5)A6))
```
其中15125表示最少的矩阵乘法次数,((A1(A2A3))((A4A5)A6))表示矩阵相乘的最优顺序。
阅读全文