矩阵连乘最优子结构证明

矩阵连乘问题是指给定n个矩阵A1、A2、...、An，其中Ai与Ai+1是可乘的（1≤i

矩阵连乘问题的最优子结构性质：对于一组序列Ai、Ai+1、…、Aj，从中任选一个k（i≤k

接下来从多个角度证明矩阵连乘问题的最优子结构性质：

第一步，证明一个序列的最优值可以由它的子序列最优值递推得到。假设Ai、…、Aj的最优计算顺序为Ak1、…、Aki和Aki+1、…、Akj，则Ai、…、Aj的标量乘法次数为：

M(Ai…Aj)=M(Ai…Aki)+M(Aki+1…Aj)+pi-1pkpj

其中pi、pk和pj分别是Ai、Ak和Aj的维数。由于Ak1、…、Aki和Aki+1、…、Akj的计算顺序是最优的，因此可以得到：

M(Ak1…Aki)≤M(Ai…Aki)

M(Aki+1…Akj)≤M(Aki+1…Aj)

因此，有：

M(Ai…Aj)≤M(Ai…Aki)+M(Aki+1…Aj)+pi-1pkpj

M(Ai…Aj)≥M(Ak1…Aki)+M(Aki+1…Akj)+pi-1pkpj

这说明Ai、…、Aj的最优计算顺序可以由Ak1、…、Aki和Aki+1、…、Akj的最优计算顺序递推得到。

第二步，证明对于一组序列Ai、Ai+1、…、Aj，从中任选一个k（i≤k

M(Ai…Aj)=M(Ai…Ak)+M(Ak+1…Aj)+pi-1pkpj

M(Ak…Aj)=M(Ak…Ak+i)+M(Ak+i+1…Aj)+pi-1pikpj

其中，pi、pk和pj分别是Ai、Ak和Aj的维数。将两个式子相加可以得到：

M(Ai…Aj)+M(Ak…Aj)=M(Ai…Ak)+M(Ak+1…Aj)+M(Ak…Ak+i)+M(Ak+i+1…Aj)+pi-1pkpj+pi-1pikpj

由于Ai、…、Aj的最优计算顺序是整个矩阵链的最优计算顺序，因此有：

M(Ai…Aj)≤M(Ai…Ak)+M(Ak+1…Aj)+pi-1pkpj

将此式代入上面的式子，可以得到：

M(Ak…Aj)≥M(Ak…Ak+i)+M(Ak+i+1…Aj)+pi-1pikpj

这说明分割出的Ak、…、Ai、Ak+i和Ak+i+1、…、Aj的最优计算顺序也是最优的，因此原序列的最优计算顺序可以由子序列递推得到。

第三步，证明最优子结构性质可以用来设计动态规划算法。对于矩阵连乘问题，设M[i,j]表示计算Ai、…、Aj的最少标量乘法次数。则当i=j时，M[i,j]=0；当i

1、对于每一个M[i,i]，令其为0；

2、对于每一个M[i,i+1]，令其等于pi-1*pi*pi+1；

3、对于每一个M[i,j]，其中i

M[i,j]=min{M[i,k]+M[k+1,j]+pi-1pkpj| i≤k

这个表达式的计算过程可以用动态规划算法实现。

综上所述，矩阵连乘问题具有最优子结构性质，这为设计动态规划算法提供了基础。动态规划算法通过逐步选取最优子问题的解来求解整个问题，递推式的设计和变量的定义有助于提高问题的解决效率。矩阵连乘问题的最优子结构性质为设计动态规划算法提供了一个很好的例子。