矩阵乘法最优算法

1、动态规划算法实现姓名：赵成兵学号：20062353班级：软件工程2班1. 问题描述多个矩阵做乘法时最多的操作是做乘法运算，矩阵乘法是满足结合律的，不同的结合方式乘法运算次数相差非常大，在矩阵的阶较大和矩阵数目很大时，这成为制约程序效率的关键，穷举找出最优结合方式显然是无效的，结合方式非常的多。所以利用动态规划解决此问题，给出最少的乘法次数。2算法设计思想及描述动态规划思想类似于分治，总是把规模较大的问题分解成小的问题加以求解，原问题的解依赖于子问题的解，还有一个显著特征就是原问题最优解的条件就是子问题的最优。不同的地方就是子问题树中的子问题大量重复出现。为减少运算，总是在第一次遇到时计算并保存

2、计算结果，以后遇到直接使用即可。动态规划求解算法，通常按以下几个步骤进行。（1） 分析最优解性质，刻画其结构特征（2） 递归定义最优值（3） 自底向上的方式计算最优解（4） 根据计算最优值得到的信息，构造一个最优解本问题是最小乘次数，定义最优结构说明：当i等于j时，取mij为0，否则取另外一个值，这时递归算最优乘次基础。3 算法分析动态规划算法可以解决的问题有一个特点，就是问题本身的最优是在子问题的最优方案基础上的。这个算法只是给出了给定矩阵序列乘积所要计算的最少次数，并没有给出给出如何最终的每次计算结合方式，但是在每次构造最优解时，数组result保存了截断点的位置，即每次计算时结合断开的下

3、标k，通过递归到最后只剩2个数组时所有的矩阵相乘的结合方式就确定下来。即间接给出了如何计算的方案。可用动态规划算法求解的问题还具备另外一个要素就是子问题的重叠性质，在递归 算法自顶向下求解问题时，每次产生的子问题不是新问题，有些子问题被反复计算多次。正是这样，只是在第一次遇到问题时计算并保存结果，以后直接使用，这个算法只需多项式的事件，效率较高。矩阵乘法最优算法代码。（最终版）#include "stdio.h"#define N 50#define M 50#define O 50#define MAX 65535/为保持一定兼容性，相乘次数不应超过整数的表示范围void

4、 main()int aN,mmNM,resultNM;/mmij数组保存的是最少相乘次数,其中i是开始的数组，j是最优的数组，i从1开始有效int i,j,k,t,l,temp,rr;int n;printf("input the number of arrays:n");scanf("%d",&rr);printf("input the right xishu:n");/输入的时候重复的数据只输入一次for(i=0;i<rr+1;i+)scanf("%d",&ai); n=rr;for(i

5、=1;i<=n;i+)mmii=0;/数组本身和自己相乘，最少次数为0次for(l=2;l<=n;l+)for(i=1;i<=n-l+1;i+)j=i+l-1;mmij=MAX;/开始时赋值为最大值，无穷大的意思for(k=i;k<=j-1;k+)temp=mmik+mmk+1j+ai-1*ak*aj;/if(temp<mmij)mmij=temp;/取得最小的次数resultij=k;/保存每次截断的位置，非常重要 printf("the most proper times is:%dn",mm1n);4 运行环境Windows XP系统，VC+6.05 程序结果分析说明，输入的行和列时遇到重复的数只输入一次即可，这就是为什么程序运行例子中8个矩阵相乘，输入的是9的数据的原因了。值得注意的是，编程中使用的数据是int 类型的，所以矩阵个数不能太大，不