动态规划法

动态规划算法矩阵连乘问题[问题描述]设有4个矩阵连乘积ABCD，设它们的维数分别为A:45×8，B:8×40，C:40×25，D:25×10，请求出它们的最优计算次序及对应的最少计算量。算法分析：设A1=A,A2=B,A3=C,A4=Dp0=45,p1=8,p2=40,p3=25,p4=10,用两个二维数组m和s记录中间结果，其中，m[i][j]记录矩阵连乘积A[i:j]的最少计算量，s[i][j]记录A[i:j]的最优断开位置。由动态规划思想，得递归式为：jipppjkmkimjijimjki}],1[],[{min0],[1jki其中，k的取值有j-i种可能：i,i+1,...,j-1.计算过程如下：(1)m[i][i]=0,i=1,2,3,4(2)求m[i][i+1],i=1,2,3m[1][2]=p0×p1×p2=45×8×40=14400s[1][2]=1m[2][3]=p1×p2×p3=8×40×25=8000s[2][3]=2m[3][4]=p2×p3×p4=40×25×10=10000s[3][4]=3(3)求m[i][i+2],i=1,2m[1][3]=min{m[1][1]+m[2][3]+p0×p1×p3,m[1][2]+m[3][3]+p0×p2×p3}=min{8000+45×8×25,14400+45×40×25}=min{17000,59400}=17000s[1][3]=1m[2][4]=min{m[2][2]+m[3][4]+p1×p2×p4,m[2][3]+m[4][4]+p1×p3×p4}=min{10000+8×40×10,8000+8×25×10}=min{13200,10000}=10000s[2][4]=3(4)求m[i][i+3],i=1m[1][4]=min{m[1][1]+m[2][4]+p0×p1×p4,m[1][2]+m[3][4]+p0×p2×p4,m[1][3]+m[4][4]+p0×p3×p4}=min{10000+45×8×10,14400+10000+45×40×10,17000+45×25×10}=min{13600,42400,28250}=13600s[1][4]=1根据以上结果可得数组m,s如下：m12341014400170001360020800010000301000040s12341111223334m[1][4]即A[1:4]的最少计算量，也即ABCD连乘积的最少计算量为13600。以上求出了最少计算量，下面由s数组构造ABCD的最优计算次序：s[1][4]=1,则有(A(BCD))；对于(BCD)，s[2][4]=3,有((BC)D)；对于(BC)，s[2][3]=2,即最优计算次序为(A((BC)D))。