知识卡片

普通读书笔记卡 · 3623.d.1.b.1

矩阵链递推枚举所有分割

理解等级:中级

设矩阵 Aᵢ 的维度为 pᵢ₋₁×pᵢ,m[i,j] 表示连乘 Aᵢ…Aⱼ 所需的最少标量乘法数;单个矩阵无需相乘,所以 m[i,i]=0。

若最后一次乘法在 k 处分割,左结果维度为 pᵢ₋₁×pₖ,右结果为 pₖ×pⱼ,合并需 pᵢ₋₁pₖpⱼ 次标量乘法。总成本因此为 m[i,k]+m[k+1,j]+pᵢ₋₁pₖpⱼ,须对所有 i≤k<j 取最小。

只比较两端局部乘法,不能保证全链最优。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.2–14.3 节(`OEBPS/chapter014.xhtml`,文本字符 [30000, 35000);Art_P458)。 - 结论依据:14.2 节给单矩阵 m[i,i]=0;末次在 k 处分割时成本为两侧最优成本加 pᵢ₋₁pₖpⱼ,须枚举所有 i≤k<j 取最小。 - 原始内容:m [ i , j ] = m [ i , k ] + m [ k + 1, j ] + p i −1 p k p j .