【DOC】-矩阵相乘的算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
矩阵相乘的算法设计
课程
实验报告
课
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
矩阵相乘的算法设计
专业班级网工专业1405班
学 号 14144501352
姓 名陈晓露
指导教师陶跃进
目录
一、问题描述
二、问题分析
1、分析最优解的结构
2、建立递归关系
3、递归实现的复杂性
4、算法迭代实现
三、结果输出
四、实验总结
一、问题描述
给定n个矩阵,A1，A2，... ，An,，其中这n个矩阵是可相乘的，i,1，2，...，n-1。算出这n个矩阵的相乘积A1A2 。。。An。
补充:如果两个矩阵A和B是可相乘的，那么A的列数要和B的行数是相同的，否则，这两个矩阵是不可相乘的。它们的相乘结果矩阵C的行数是A的行数，而列数是B的列数。
设A1,A2,…,An为矩阵序列，Ai为Pi-1×Pi阶矩阵，i = 1,2,…,n. 确定乘法顺序使得元素相乘的总次数最少.
输入:向量P =
实例:
P = <10, 100, 5, 50> A1: 10 × 100, A2: 100 × 5, A3: 5 × 50 乘法次序:
(A1 A2)A3: 10 × 100 × 5 + 10 ×5 × 50 = 7500
A1(A2 A3): 10 × 100 × 50 + 100 × 5 × 50 = 75000
搜索空间的规模
先将矩阵链加括号分为两部分，即P=A1*A2*...*An=(A1*A2...*Ak)*(Ak+1*...An)，则有f(n)=f(1)*f(n-1)+f(2)*f(n-2)+...+f(n-1)*f(1)
种方法。
动态
规划
污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文
算法
输入P=< P0, P1, …, Pn>，Ai..j 表示乘积 AiAi+1…Aj 的结果，其最后一次相乘是:
m[i,j] 表示得到Ai..j的最少的相乘次数。
递推方程:
为了确定加括号的次序，设计表s[i,j],记录求得最优时最一位置。
二、问题分析
由于矩阵乘法满足结合律，故连乘积的计算可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序已完全确定，也就是说该连乘积已完全加括号，则我们可以通过反复调用两个矩阵相乘的
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
算法计算出矩阵连乘积。
1.分析最优解的结构
为了方便起见，我们将矩阵连乘AiAi+1 。。。Aj记为A[i:j]。经分析，计算A[1:n]的一个最优次序所包含的计算矩阵子链A[1:k]和A[k:n]的次序也是最优的。因此，矩阵连乘计算次序问题的最优解包含着子问题的最优解。
2.建立递归关系
用矩阵m[n][n]来存放A[i:j]相乘的计算次数，用p[n+1]用来存放矩阵的行数和列数。
const int N=5;
int m[N][N]; //m[i][j]存储Ai到Aj的最小乘法次数
int s[N][N];//s[i][j]存储Ai到Aj之间加括号的位置
int RecurMatrixChain(int P[],int i,int j)
{
m[i][j]=100000;
s[i][j]=i;
if(i==j)
m[i][j]=0;
else{
for(int k=i;k的简单实例，运行上述代码:
四、实验总结
对于此次算法设计:翻阅了大量的资料，通过和同学老师的讨论设计了这次算法，用学过的c++语言写成。一个比较简单的例子做起来超乎想象的复杂，但是这个课程设计帮助我更好地理解了所学知识，让我在以后的生活当中能够更好地从多个方面分析问题。
浙公网安备 33021202002483