西电软件学院算法实验报告模板2份32页.doc

第二次试验一、问题：Matrix-chain product分析：本题是矩阵链乘问题，需要求出最优括号化方案。即在矩阵的乘法链上添加括号来改变运算顺序以使矩阵链乘法的代价降低。可以分析该链乘的一个子段总结一些结论。假设mi,j表示Ai*Aj的链成需要进行的乘法次数（假设j-i足够大），我们可以将Ai*Aj分为两段进行计算：（Ai*Ak）*（Ak+1*Aj）可以得出mi,j的递推公式可以得出，当i=j的时候，mi,j=0。当ij的时候。k的取值范围是i到j-1，对于k的每一个取值都可以得到一个mi,j的值，取出最小值即时mi,j的最优化方案。递推公式如下：可以根据上式得到一个递归算法。本题即是求m1,n的值。用二维数组m存储mi,j的值，用二维数组s来储存应当分割的位置。以本题中第一个矩阵a)为例，可以得出如下矩阵：通过m数组可以得出最少的乘法次数，通过s数组可以输出最优方案。