算法与分析实验三：动态规划法

【实验目的】 应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验性质】 验证性实验（学时数：2H） 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]，A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 动态规划是一种解决问题的有效方法，尤其在处理具有最优子结构和子问题重叠特性的复杂问题时。本实验的目的是让学生理解和应用动态规划算法解决矩阵连乘的顺序问题，以达到最小化乘法次数的目标。 实验内容是寻找一组矩阵的最优连乘积次序，使得所需的总乘法次数最少。动态规划在这里的应用基于两个关键性质：最优子结构和子问题重叠。最优子结构意味着问题的最优解可以通过其子问题的最优解来构建，而子问题重叠则表示在解决问题的过程中，很多子问题会被重复计算。 在矩阵连乘问题中，用m[i][j]表示矩阵A[i]到A[j]的最优乘积次序所需的乘法次数。当i=j时，m[i][j]=0，因为一个矩阵自乘不需要任何乘法。对于i<j的情况，m[i][j]可以通过比较所有可能的分隔点k（i<k<j）的乘法次数来确定，即取m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]的最小值，其中p[i]表示矩阵A[i]的列数，同时也是A[i+1]的行数。 实验要求包括算法描述、程序代码编写、调试以及结果分析。在给定的程序代码中，`matrix`函数负责计算m[i][j]的值，而`print1`和`print2`函数分别用于打印矩阵信息、最优解和断开点。主函数`main`初始化了矩阵的维数，并调用了这些函数来完成整个过程。 程序中的核心部分是`matrix`函数内的嵌套循环，它首先初始化对角线元素m[i][i]，然后通过外层循环z从2到n逐步处理更复杂的子问题。内层循环则用于比较不同分隔点k的乘法次数，找到使m[i][j]最小的那个k，并更新m[i][j]和对应的断开点s[i][j]。 通过这样的动态规划策略，程序能够找到矩阵连乘的最优次序，从而减少总的乘法运算次数。在给定的测试数据中，矩阵的维数和乘法次数的计算都是已知的，实验结果会显示出最优的矩阵连乘序列以及所需的最少乘法次数。 总结来说，动态规划在解决矩阵连乘问题时，通过分解问题为子问题并存储子问题的解，有效地减少了计算量，实现了高效求解。这个实验不仅让学生掌握了动态规划的基本思想，还锻炼了他们将算法转化为实际程序的能力。