[置顶] 矩阵链乘 动态规划

1.分析优化解的结构
两个记号：
$A_{i-j} = A_i \times A_{i+1} \times ... \times A_j$
$cost(A_{i-j})$=计算$A_{i-j}$的代价
（2）优化解的结构
证明：若计算$A_{1-n}$的优化顺序在k处断开矩阵链，那末在计算$A_{1-k}$时，应当直接使用$cost(A_{1-k})$，假定$cost(A_{1-k})$不是最优结果，则存在另外一个结果优于它，那末带入$A_{1-n}$后解比最优解要好，矛盾。

2.子问题堆叠性： 计算$(A_1) \times (A_2 \times A_3 \times A_4)$和$(A_1\times A_2) \times (A_3 \times A_4)$都需要计算$A_3 \times A_4$。

3.递归定义最优解代价
用子问题的最优解递归定义原问题的最优解
m[i,j]表示计算矩阵Ai,j所需标量乘法次数的最小值，那末原问题的最优解-计算$A_{1...n}$所需的最低代价就是m[1,n]。
$m[i,j]=0$ if i=j
$m[i,j]=min(i<=k<j)m[i,k]+m[k,j]+p_{i-1} p_k p_j$ if i $\lt$ j
其中$p_{i⑴} p_k p_j$为计算$A_{i \sim k}+A_{k+1\sim j}$所需乘法次数

4.递归划份子问题
1个$i \times j$行矩阵，想要计算m[i,j]的递归方程，需要先计算出第i行的m[i,i],m[i,i+1]…m[i,j⑴]和第j列的m[j,j],m[j⑴,j]…m[i+1,j]

5.自底向上计算优化解的代价
以m[1,5]为例：

m[1,1] m[1,2] m[1,3] m[1,4] m[1,5]
       m[2,2] m[2,3] m[2,4] m[2,5]
              m[3,3] m[3,4] m[3,5]
                     m[4,4] m[4,5]
                            m[5,5]

想要计算m[1,5]，需要计算m[1,1] m[1,2] m[1,3] m[1,4]和m[2,5]，m[3,5]， m[4,5]，m[5,5]。
要计算m[1,4]，需要计算m[1,1] m[1,2] m[1,3]和[2,4]，m[3,4]， m[4,4]
要计算m[2,5]，需要计算m[2,2] m[2,3] m[2,4]和m[3,5]， m[4,5]，m[5,5]
……..

所以最需要先计算的是对角线的上元素m[1,1],m[2,2],m[3,3],m[4,4],m[5,5],它们的结果都是0
接下来就能够计算m[1,2],m[2,3],m[3,4],m[4,5]了
以后计算m[1,3],m[2,4],m[3,5]
……
最后计算出m[1,5]

每次均计算出对角线上的1组元素，且是自底向上的

6.算法思想
1.先对第1层对角线值给初值0(m[i,i]=0)
2.对有n个矩阵的输入来讲，为计算m[1,n],需要n⑴个对角线（第1层对角线已计算过了）
3.对自底向上的第i层对角线来讲，共需要计算i个不同的m值
4.对每个m值，通过$m[i,j]=min(i<=k<j)m[i,k]+m[k,j]+p_{i-1} p_k p_j$ if i $\lt$ j计算,s[i,j]记录断开位置

所以总共需要3层循环。

Matrix-Chain-Order(n)
For $i=1$ To $n$ Do
$\;\;\;\;m[i,i]=0$
For $l=2$ To $n$ Do
$\;\;\;\;$For i= 生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠