矩阵乘法最优算法下载_Word模板_4

矩阵乘法最优算法动态规划实现动态规划算法实现姓名:赵成兵学号:20062353 班级:软件工程2班 1. 问题描述多个矩阵做乘法时最多的操作是做乘法运算，矩阵乘法是满足结合律的，不同的结合方式乘法运算次数相差非常大，在矩阵的阶较大和矩阵数目很大时，这成为制约程序效率的关键，穷举找出最优结合方式显然是无效的，结合方式非常的多。所以利用动态规划解决此问题，给出最少的乘法次数。 2(算法设计思想及描述动态规划思想类似于分治，总是把规模较大的问题分解成小的问题加以求解，原问题的解依赖于子问题的解，还有一个显著特征就是原问题最优解的条件就是子问题的最优。不同的地方就是子问题树中的子问题大量重复出现。为减少运算，总是在第一次遇到时计算并保存计算结果，以后遇到直接使用即可。动态规划求解算法，通常按以下几个步骤进行。 (1) 分析最优解性质，刻画其结构特征 (2) 递归定义最优值 (3) 自底向上的方式计算最优解 (4) 根据计算最优值得到的信息，构造一个最优解本问题是最小乘次数，定义最优结构 0,,mij[][], ,mikkjppp{[][]m[1][]}，，，ikj,1min,ikj,,, 说明:当i等于j时～取m[i][j]为0～否则取另外一个值～这时递归算最优乘次基础。 3 算法分析动态规划算法可以解决的问题有一个特点，就是问题本身的最优是在子问题的最优方案基础上的。这个算法只是给出了给定矩阵序列乘积所要计算的最少次数，并没有给出给出如何最终的每次计算结合方式，但是在每次构造最优解时，数组result[][]保存了截断点的位置，即每次计算时结合断开的下标k，通过递归到最后只剩2个数组时所有的矩阵相乘的结合方式就确定下来。即间接给出了如何计算的方案。可用动态规划算法求解的问题还具备另外一个要素就是子问题的重叠性质，在递归算法自顶向下求解问题时，每次产生的子问题不是新问题，有些子问题被反复计算多次。正是这样，只是在第一次遇到问题时计算并保存结果，以后直接使用，这个算法只需多项式的事件，效率较高。 1 动态规划实现矩阵乘法最优算法代码。(最终版) #include "stdio.h" #define N 50 #define M 50 #define O 50 #define MAX 65535//为保持一定兼容性，相乘次数不应超过整数的表示范围 void main() { int a[N],mm[N][M],result[N][M];//mm[i][j]数组保存的是最少相乘次数,其中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

                    本文档为【矩阵乘法最优算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

矩阵乘法最优算法

你可能还喜欢