矩阵连乘问题(动态规划).doc

《矩阵连乘问题(动态规划).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、矩阵连乘问题（动态规划）一、实验目的与要求1、明确矩阵连乘的概念。2、利用动态规划解决矩阵连乘问题。二、实验题：问题描述：给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。三、实验代码#includeusingnamespacestd;constintMAX=100;//p用来

2、记录矩阵的行列，main函数中有说明//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解//s[][]用来记录从哪里断开的才可得到该最优解intp[MAX+1],m[MAX][MAX],s[MAX][MAX];intn;//矩阵个数intmatrixChain(){for(inti=0;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//对角线循环for(inti=0;i<=n-r;i++){//行循环intj=r+i-1;//列的控制//找m[i][j]的最小值，

3、先初始化一下，令k=im[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j+1];s[i][j]=i;//k从i+1到j-1循环找m[i][j]的最小值for(intk=i+1;k

4、//根据s[][]记录的各个子段的最优解，将其输出voidtraceback(inti,intj){if(i==j){cout<<'A'<

5、back(0,n-1);cout<<')';cout<>n;cout<<"输入矩阵（形如a*b,中间用空格隔开）:"<>p[i];//测试数据可以设为六个矩阵分别为//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]//则p[0-6]={30,35,15,5,10,20,25}cout<

6、<"输出结果如下："<