实验四 利用动态规划算法实现矩阵连乘问题
一、实验目的:通过上机实验,要求掌握动态规划算法的问题描述、算法设计思想、程序设
计和算法复杂性分析等。
二、实验环境
1、微机一台;
2、VC6.0;或 JAVA 编译环境、EditPlus 集成开发环境;
3、实验室内部局域网络、Internet 互联网络。
三、实验内容
问题 1:用动态规划方法实现矩阵乘法的程序。
(1)问题的描述
给定 n 个矩阵{A1,A2....An},其中 Ai 与 Ai+1 是可以相乘的,判断这 n 个矩阵通过
加括号的方式相乘,使得相乘的次数最少!
以矩阵链 ABCD 为例,按照矩阵链长度递增计算最优值
矩阵链长度为 1 时,分别计算出矩阵链 A、B、C、D 的最优值
矩阵链长度为 2 时,分别计算出矩阵链 AB、BC、CD 的最优值
矩阵链长度为 3 时,分别计算出矩阵链 ABC、BCD 的最优值
矩阵链长度为 4 时,计算出矩阵链 ABCD 的最优值
(2)算法设计思想
k 为矩阵链断开的位置;d 数组存放矩阵链计算的最优值,d[i][j]是以第 i 个矩阵为首,
第 j 个矩阵为尾的矩阵链的最优值,i > 0; m 数组内存放矩阵链的行列信息,m[i-1]和 m[i]
分别为第 i 个矩阵的行和列(i = 1、2、3...)
(3)程序设计
评论0