2022年算法实验动态规划----矩阵连乘文件 .pdf

《2022年算法实验动态规划----矩阵连乘文件 .pdf》由会员分享，可在线阅读，更多相关《2022年算法实验动态规划----矩阵连乘文件 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三：动态规划法【实验目的】深入理解动态规划算法的算法思想，应用动态规划算法解决实际的算法问题。【实验性质】验证性实验。【实验要求】对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为： 一般地，考虑矩阵 A1， A2， ， An 的连乘积，它们的维数分别为d0,d1,dn,即 Ai 的维数为di-1di (1in)。确定这n 个矩阵的乘积结合次序，使所需的总乘法次数最少。 对应于乘法次数最少的乘积结合次序为这n 个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6 个矩阵连乘积A=A1 A2A3A4A5A6，各矩阵的维数分别为：A

2、1：10 20，A2：20 25，A3：25 15，A4：15 5，A5：5 10，A6：10 25。完成测试。【算法思想及处理过程】Main ( ) 函数: 定义 二维数组 m 用来存放最优解 ; 定义 二维数组 s 用来存放最优解的断开点 ; 定义 一维数组 p 用来存放矩阵维数 . MatrixChain函数: 首先通过for循环, 给二维数组 M 和 S 的对角线赋值为0 (表示只有一个矩阵 , 没有相乘的 ). 然后通过 for循环, 求出最优解 ( 这只是假定的最优解 ) 和 断开点( 这只是假定的最完美的断开点 ), 再通过双重 for 循环在后面找到了一个最优解,判断后一个最优

3、解是不是比前一个最优解小 ( 也就是更优 ,更好), 如果小 , 则将前最优解改为后一个的最优解, 并且将前断开点改为后一个的断开点, 然后重复此操作 .名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 【程序代码】# include void MatrixChain (int p, int m6, int s6, int n); / 求最优解和断开点void print1 (int m6, int s6,int p); / 打印

4、矩阵 ,最优解 ,断开点void print2(int i, int n, int s6); / 打印加括号的断开矩阵int main () int p7 = 10,20,25,15,5,10,25; int m66, s66; MatrixChain (p, m, s, 6); print1 (m, s, p); printf (nn 矩阵连乘次数的最优值为:n); printf (-n); print2 (0, 6-1, s); printf (n-nn); return 0; void MatrixChain (int p, int m6, int s6, int n) int i, j

5、, k, z, t; for (i=0; in; i+) mii = 0; sii = 0; for (z=2; z=n; z+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - for (i=0; i=n-z; i+) j = i + z - 1; mij = mi+1j + pi * pi+1 * pj+1; sij = i; for (k = i+1; kj; k+) t = mik + mk+1j + pi * pk+1

6、 * pj+1; if (t mij) mij = t; sij = k; void print1 (int m6, int s6,int p) int i, j; printf (nn 程序所给矩阵如下 :n); printf (-n); for (i=0; i6; i+) printf (A%d 矩阵: %2d X %-2d n,i+1,pi, pi+1); printf (nn-n); printf( 矩阵的最少计算次数为：%dn, m05); printf (-n); printf (nn 数乘次数 : n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

7、- - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - printf (-n); for (i=0; i6; i+) for (j=0; ji; j+) printf ( ); for (j=i; j6; j+) printf (%-7d, mij); printf (n); printf (-n); printf (nn 中间断点 : n); printf (-n); for (i=0; i6; i+) for (j=0; ji; j+) printf ( ); for (j=i; j6; j+) prin

8、tf (%-7d, sij); printf (n); printf (-n); void print2(int i, int n, int s6) if (i = n) printf ( A%d , i); else if (i+1 = n) printf ( A%d A%d ), i, n); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - printf ( ( ); print2 (i, sin, s); pri

9、nt2 (sin+1, n, s); printf ( ) ); 【运行结果】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 【算法分析】函数 MatrixChain( ) 包含三重循环 ,循环体内的计算量为O(1) , 所以算法的时间复杂度为O(n3) ,算法的空间时间复杂度为O(n3) . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 【实验总结】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -