n个矩阵组成的矩阵链U1.. =< U1,U2,...,U. >矩阵链U1..n对应的维度数分别为po,p1,...,pn,U的维度为pi-1 x pi 输出。找到一种加括号的方式,以确定矩阵链乘法的计算顺序,使得最小化矩阵链标量乘法的次数的代码
时间: 2024-02-25 22:56:36 浏览: 29
以下是使用动态规划算法实现的最小矩阵链乘法次数以及加括号的代码示例:
```python
def matrixChainOrder(p):
n = len(p) - 1
dp = [[float('inf') for _ in range(n)] for _ in range(n)]
s = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[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 = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
if q < dp[i][j]:
dp[i][j] = q
s[i][j] = k
return dp[0][n-1], s
def addParenthesis(s, i, j):
if i == j:
return f'U{i+1}'
else:
k = s[i][j]
left = addParenthesis(s, i, k)
right = addParenthesis(s, k+1, j)
return f'({left} x {right})'
p = [30, 35, 15, 5, 10, 20, 25]
minCost, s = matrixChainOrder(p)
parenthesis = addParenthesis(s, 0, len(p)-2)
print(f'Minimum scalar multiplications: {minCost}')
print(f'Parenthesized matrix chain: {parenthesis}')
```
其中,`matrixChainOrder`函数使用二维数组`dp`来记录最小的标量乘法次数,数组`s`用来记录最优的分割点。`addParenthesis`函数根据`s`数组递归构造出最优的加括号方式。在上面的示例中,最小标量乘法次数为15125,加括号的方式为`((U1 x (U2 x U3)) x ((U4 x U5) x U6))`。