1652286-李辉-作业五算法实现题1
需积分: 0 33 浏览量
2022-08-03
23:44:04
上传
评论
收藏 149KB PDF 举报
动态规划：矩阵连乘求最优解问题
从整体往局部看，求解
ji
A
...
的矩阵连乘问题，可以考虑在某一个位置将这些矩阵分开，
即
di
A
...
和
jd
A
...1
，划分开来后，再求子问题的最优加括弧方法
从 局 部 往 整 体 看 ， 计 算
ji
A
...
的 代 价
=
计 算
di
A
...
的 代 价
+
计 算
jd
A
...1
的 代 价
+
计 算
di
A
...
*
jd
A
...1
的代价
动态规划迭代实现问题求解：
可以先通过迭代方法将计算子问题的代价 B[i...j]和最优切割位置 S[i...j]，计算出来后保存到
备忘录中以便求解过程中直接调用。
矩阵规模存储在一维数组 p[1...n]中
最优代价存储在二维数组
B[i,j]
中
(i,j
∈
[1...n])
，表示
ji
A
...
连乘的最小结果
最优分割点存储在二维数组
S[i,j]
中
(i,j
∈
[1...n])
，表示
ji
A
...
的最优分割点
时间复杂度：三层迭代，时间复杂度为 O(
3
n
)
空间复杂度：O(n)+O(
2
n
)+O(
2
n
)=O(
2
n
)
实验结果截图
评论0
最新资源