1.分析優化解的結構
兩個記號：
Ai?j=Ai×Ai+1×...×Aj$A_{i-j} = A_i \times A_{i+1} \times ... \times A_j$
cost(Ai?j)$cost(A_{i-j})$=計算Ai?j$A_{i-j}$的代價
（2）優化解的結構
證明：若計算A1?n$A_{1-n}$的優化順序在k處斷開矩陣鏈，那末在計算A1?k$A_{1-k}$時，應當直接使用cost(A1?k)$cost(A_{1-k})$，假定cost(A1?k)$cost(A_{1-k})$不是最優結果，則存在另外一個結果優于它，那末帶入A1?n$A_{1-n}$后解比最優解要好，矛盾。

2.子問題堆疊性： 計算(A1)×(A2×A3×A4)$(A_1) \times (A_2 \times A_3 \times A_4)$和(A1×A2)×(A3×A4)$(A_1\times A_2) \times (A_3 \times A_4)$都需要計算A3×A4$A_3 \times A_4$。

3.遞歸定義最優解代價
用子問題的最優解遞歸定義原問題的最優解
m[i,j]表示計算矩陣Ai,j所需標量乘法次數的最小值，那末原問題的最優解-計算A1...n$A_{1...n}$所需的最低代價就是m[1,n]。
m[i,j]=0$m[i,j]=0$ if i=j
m[i,j]=min(i<=k<j)m[i,k]+m[k,j]+pi?1pkpj$m[i,j]=min(i<=k<j)m[i,k]+m[k,j]+p_{i-1} p_k p_j$ if i <$\lt$ j
其中pi?1pkpj$p_{i⑴} p_k p_j$為計算Ai～k+Ak+1～j$A_{i \sim k}+A_{k+1\sim j}$所需乘法次數

4.遞歸劃份子問題
1個i×j$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]+pi?1pkpj$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$i=1$ To n$n$ Do
m[i,i]=0$\;\;\;\;m[i,i]=0$
For l=2$l=2$ To n$n$ Do
$\;\;\;\;$For i= 生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈