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

第二次试验 一 问题 Matrix-chain product 分析 本题是矩阵链乘问题需要求出最优括号化方案即在矩阵的乘法链上 添加括号来改变运算顺序以使矩阵链乘法的代价降低 可以分析该链乘的一个子段总结一些结论假设 m[i,j] 表示 Ai* *Aj 的链 成需要进行的乘法次数 假设j-i 足够大我们可以将 Ai* *Aj 分为两段进行 计算 A * *A * A * *A 可以得出 m[i