问题矩阵连乘问题

《问题矩阵连乘问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、问题：矩阵连乘问题描述：给定n个矩阵｛Al,A2,…,An｝,其中Ai与Ai+1是可乘的，i=l,2...,n・l。考察这n个矩阵的连乘积AlA2...Am矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个pxq矩阵，B是一个q*r•矩阵，则其乘积C=AB是一个p*r矩阵，需婆pqr次数乘。矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵｛Al,A2,・・・,An｝(其中矩阵Ai的维数为pi-1*pi,i=l,2,n),确定计算矩阵连乘积A1A2...An的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数故少。编程任务：对于给定的

2、相继n个矩阵｛Al,A2,An｝及其维数，编程计算矩阵连乘积A1A2...An需要的最少数乘次数。数据输入：由文件input.txt给出输入数据。第1行是给定的正整数n,表示有n个矩阵连乘。第2行是n+1个正整数P0,P1,・・・，Pn，表示矩阵Ai的维数为pi・l*pi,i=l,2,n。结果输出：将计算出的最少数乘次数输出到文件output.txto*/#include#include#include//变量、函数定义开始ofstreammyoutf(noutput.txt");〃输出

3、到文件，全局变量MatrixChain函数定义**萌数名：MatrixChain*返回类型：void无返冋值**参数说明：p[]矩阵的维数**n矩阵连乘的个数**m保存矩阵最少连乘个数的二维数组*功能：输出n个矩阵连乘的最优值*调用示例：MatrixChain(p,nzm);**///变量.函数定义结束II——主函数开始voidmain(){intMatrixNum;〃定义连乘的矩阵数inti/j；int*P；int**m;〃保存最优值数ifstreammyinfC'input.txfjos::nocreate);〃读取文件if(myinf.fail

4、()){cerr«“读入文件吋，出错！“；return;回错误}//if(myinf.fail())〃如果没有输入文件，则返myinf>>MatrixNum;〃读取炬阵个数cout<0)P—newint[MatrixNum+1];〃分配矩阵维数数组空间if(p==NULL){cerr«”数组空间分配不成功，出错！：return;}//if(p!=NULL)for(i=

5、0;i>p[i];cout<

6、维动态数组结束〃调用动态规划矩阵连乘算法i++)delete[]m[i];〃释放二维数组空间〃释放矩阵维数数组空间〃关闭输入文件〃关闭输出文件MatrixChain(p

7、阵链断开，1v二kvn,则完全加括号方式为((Al...Ak)(Ak+l...An))。照此，我们要先计算Al...k和Ak+l...n,然后，将所得的结果相乘才得到Al...no显然其总计算量为计算Al...k的计算量加上计算Ak+l...n的计算量，再加上Al...k与Ak+l...n相乘的计算量。2、建立递归关系对于矩阵连乘积的最优计算次序问题，设计算Ai...jzl

8、j时，可利用最优子结构性质來计算m[izj]o事实上，若计算Ai...j的最优次序在Ak和Ak+lZ间断开,