应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想,应用动态规划策略写出算法及相应的程序,求解此题。要读懂读透A[i,j],A[1,n]=A[1,k] ×A[k+1,n],m[i][j],s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义: 0 ( i=j ) m[i][j]= min{m[i][k]+ m[k+1][j]+ni-1nknj ( i<j) 要求完成:⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。
时间: 2023-09-17 07:14:22 浏览: 29
问题描述:
给定一个矩阵链A1A2...An,其中Ai的规模为pi-1 × pi(i=1,2,...,n)。在矩阵链中加入括号,使得计算矩阵的乘积的代价最小。
动态规划算法思想:
动态规划算法的核心思想是将原问题拆分为若干个子问题,通过求解子问题的最优解,从而得到原问题的最优解。对于本题,我们可以将矩阵链A1A2...An分割为Ai...Ak和Ak+1...An两个子链,其中i≤k<j。假设已经知道Ai...Ak和Ak+1...An的最优加括号方案,那么Ai...An的最优加括号方案就是其中代价最小的一个。因此,我们可以采用动态规划算法来求解最优加括号方案。
具体地,我们可以定义m[i][j]表示Ai...Aj的最小代价,s[i][j]表示Ai...Aj的最优加括号方案中第一个加入括号的位置。对于m[i][j]和s[i][j]的计算,我们可以采用自底向上的方法,即先计算出所有长度为1的子链(即i=j时),再计算出所有长度为2的子链(即i<j且j-i=1时),接着计算长度为3的子链,一直计算到长度为n的子链,最终得到m[1][n]即为最小代价,s[1][n]即为最优加括号方案。
表示含义:
A[i,j]:表示从第i个矩阵到第j个矩阵的乘积结果,即Ai×Ai+1×...×Aj。
m[i][j]:表示Ai...Aj的最小代价。
s[i][j]:表示Ai...Aj的最优加括号方案中第一个加入括号的位置。
程序代码:
```python
def matrix_chain_order(p):
n = len(p) - 1
m = [[float('inf')] * (n + 1) for i in range(n + 1)]
s = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):
m[i][i] = 0
for l in range(2, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
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{}'.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='')
if __name__ == '__main__':
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)),最小代价为15125。