矩阵连乘问题（动态规划）

矩阵连乘问题（动态规划）

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

#include #include using namespace std;struct SIGN{ int num;//加括号的个数 }l[100+5],r[100+5]; //l为左括号,r为右括号 //矩阵的个数 int n;//矩阵的维数 第i个矩形 的维数为 p[i*2]和p[i*2+1]int p[200+5];//m[i][j]表示当前i到j最少的计算次数 int m[100+5][100+5];//s[i][j]表示当前i到j最少计算次数需要断开的位置s[i][j] int s[100+5][100+5];//x[i]表示第i个矩阵要加括号的个数 void MatrixChain(){ memset(m,0,sizeof(m)); //当前矩阵的长度 for(int r=2;r<=n;r++) { //矩阵的起始位置 for(int i=1;i<=n-r+1;i++) { //矩阵的结束位置（矩阵开始+矩阵长度-1） int j=i+r-1; if(i>n||j>n) continue; //m[i][j]初值 m[i][j]=m[i+1][j]+p[2*i]*p[2*i+1]*p[2*j+1]; //记录当前s[i][j]的最优断开位置 s[i][j]=i; //循环找i,j之间的最优断点k for(int k=i+1;k>n; cout<<"请输入各矩阵的维数，空格分开"<>p[i*2]; cin>>p[i*2+1]; } MatrixChain(); //输出1到n的最优结果 cout<<"最小计算次数为："<

二.问题的描述

（1）变量说明

n     矩阵个数

p[200+5] 矩阵的维数 第i个矩形 的维数为 p[i*2]和p[i*2+1]

m[100+5][100+5] 表示当前矩阵i到矩阵j最少的计算次数

s[100+5][100+5] 表示当前矩阵i到矩阵j最少计算次数需要断开的位置为s[i][j]

l[100+5] l[i].num表示矩阵i需要的左括号为l[i].num个

r[100+5] r[i].num表示矩阵i需要的右括号为r[i].num个

（2）函数说明

MatrixChain 求当前矩阵的最小连乘次数 并记录断点

Traceback 通过递归的方法找到断点 并加括号

dealSign 输出最小连乘次数的计算顺序

（3）程序解释

1.使用cin输入流输入矩阵的个数并分别输入每个矩阵的维数，用p[]数组保存，对于第i个矩阵而言，第i个矩阵的行数为p[2*i],第i个矩阵的列数为p[2*i+1].然后执行MatrixChain函数。

2.在MatrixChain函数中，首先使用memeset函数对m[][]数组进行初始化，然后使用了三重for循环。

第一重for循环的变量r表示当前要执行的矩阵连乘的长度。

第二重for循环的i表示长度为r的矩阵连乘的起始位置，然后使用j=i+r-1得到长度为r的矩阵连乘的结束位置。其中m[i][j]=m[i+1][j]+p[2*i]*p[2*i+1]*p[2*j+1]表示实现为长度为r，起始矩阵为i，结束矩阵为j的矩阵连乘假设一个断点为i。

然后就使用第三重for循环k来循环假设由i到j的断点。如果k断点得到的连乘次数小于当前的m[i][j]，则更新m[i][j],s[i][j]。

执行完以上三重for循环即得到矩阵的最小连乘次数  但是还未得到计算的次数。

3.Traceback(int i,int j)函数使用递归计算最小连乘次数的计算次序。调用Traceback（1，n） 其中1为矩阵的起始位置，n为矩阵连乘的个数。Traceback函数结束的条件为当前i到j得矩阵个数为1，即i=j.如果i到j的矩阵个数大于1，则递归调用Traceback（i，s[i][j]）, Traceback(s[i][j]+1,j).其中s[i][j]表示矩阵i连乘到j的断开点。最后输出结果即可。

4.dealSign方法输出括号和矩阵

三.实验结果

四.对实验结果的分析

当输入矩阵个数6，6个矩阵的行数和列数后

通过程序计算出6个矩阵连乘的最小次数为15125次

执行的次序为：

假设6个矩阵矩阵起始为123456

首先是矩阵2到矩阵2（即矩阵2）和矩阵3到矩阵3（即矩阵3）相乘  1（23）456

然后是矩阵1到矩阵1（即矩阵1）和矩阵2到矩阵3相乘 （1（23））456

然后是矩阵4到矩阵4（即矩阵4）和矩阵5到矩阵5（即矩阵5）相乘 （1（23））（45）6

然后是矩阵4到矩阵5和矩阵6到矩阵6（即矩阵6）相乘 （1（23））（（45）6）

最后是矩阵1到矩阵3和矩阵4到矩阵6相乘 （（1（23））（（45）6））

即最小连乘次数15125次的计算次数为（（1（23））（（45）6））

与运行结果一致。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。