矩阵连乘实验报告

矩阵连乘实验报告

————————————————————————————————作者: ————————————————————————————————日期:

?

华北电力大学科技学院

实验报告

实验名称矩阵连乘问题

课程名称计算机算法设计与分析

专业班级：?软件12K１??学生姓名：吴旭

学号：1２1909０２0１２4 成绩:

指导老师: 刘老师?实验日期：2０１４．11.１4

一、实验内容

矩阵连乘问题,给定n个矩阵｛A1，A２,…，A n｝，其中A i与A i+1是可乘的,ｉ=1,2,3…,n-1。考察这n个矩阵的连乘A1,Ａ２,…,A n。

二、主要思想

由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已经完全加括号，则可依此次序反复调用２个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为:

(1)单个矩阵是完全加括号的；

(2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的

矩阵连乘积Ｂ和Ｃ的乘积并加括号，即Ａ=(BC)。

运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行

1、分析最优解的结构

设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为Ａ［i：j］。考察计算Ａ[1：ｎ]的最优计算次序。设这个计算次序矩阵在Aｋ和A k＋１之间将矩阵链断开,1≤k≤n,则其相应的完全加括号方式为((Ａ

…A k)(Ａk+1…A n)）。依此次序，先计算A[１:k]和Ａ[k＋1:ｎ］,然后１

将计算结果相乘得到Ａ[1：n]。

2、建立递归关系

设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j],1≤i≤j≤n，所需的最少数乘次数为m［i］[j],原问题的最优值为ｍ[1]［ｎ]。

当i＝j时,A[ｉ:ｊ]=A i为单一矩阵,无需计算,因此m[i][i]=0，i=１,2,…n。

当i<ｊ时，可利用最优子结构性质来计算m[i][ｊ]。m[i］［j]=m[i][k］＋m［ｋ+1][j］+ｐi-1pｋｐj。由于在计算时并不知道断开点k的位置,所以k还未定。

3、计算最优值

根据计算m[i][ｊ］的递归式，容易写一个递归算法计算ｍ[1][n］。动态规划法解决此问题，可依据递归式以自底向上的方式进行计算，在计算过程中保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下,从而避免大量的重复计算，最终得到多项式时间的算法mａtrixChａｉn。(见实验代码部分)

4、构造最优解

算法mａtrｉxCｈaiｎ只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。S[i][ｊ]中的数表明，计算矩阵链A［i:j]的最佳方式应在矩阵Aｋ和Aｋ+１之间断开，最优加括号方式为(A[i:k］)(A[k+1:j］)。依次构造最优解。(算法见实

验代码部分)

三、实验结果

四、结果验证

对实验结果进行验证，4个矩阵分别是A１［35*１5]，A２［１5*5],A3[5*10],A４[10*20]。依递归式有：

Ｍ［1][4]=ｍin{0+2500+35×15×20=13000 2625+1000+35×5×20=7125 4375+0+35×10×20=11375

=71２５

且k=3。

计算结果正确,证明所编写的程序可正确算出最优解。

五、实验代码

＃iｎclude<ｓtdｉｏ．h>

#deｆinｅN10０／/定义最大连乘的矩阵个数是１00

ｖoid matrixＣhain（inｔp[］，int m［N＋1］[Ｎ+1],int s[N+1］[N+１])／＊用m［i］[j]二维数组来存储Aｉ*．...．Aｊ的最少数乘次数,

用s[i］[ｊ]来存储使Ai.．...Ａｊ获得最少数乘次数对应的断开位置ｋ，需要注意的是此处的N＋1非常关键,虽然只用到的行列下标只从1到N，

但是下标0对应的元素默认也属于该数组,所以数组的长度就应该为N+1*／{

?ｉｎtｎ=Ｎ;／／定义m,s数组的都是n*n的，不用行列下标为0的元素,但包括在该数组中

for(iｎｔi=1;i＜＝n;i++）

m[i]［ｉ］＝0;/*将矩阵ｍ的对角线位置上元素全部置0，此时应是r=１的情况,表示先计算第一层对角线上个元素的值*/

?ｆoｒ(inｔｒ=2;r<=n;r++）／/r表示斜对角线的层数，从2取到n ｛

?for（ｉnt ｉ＝1;i＜＝n-r+1;ｉ++)／/i表示计算第r层斜对角线上第i行元素的值

?{

?int j=i+r-1;／/j表示当斜对角线层数为r,行下标为i时的列下标??m［i]［j］=m［i＋1][j］+p［i-1］*p[i］*ｐ[j];／／计算当断开位置为i时对应的数乘次数

?ｓ[i]［j]=ｉ；//断开位置为i

?ｆｏｒ（int k=i+1;k

??{

??int ｔ=m［i]［k］+ｍ［k＋１][j]+ｐ[i－1]＊ｐ［ｋ］＊p[j];/*计算断开位置ｋ为从i到ｊ(不包括i和j）的所有取值对应的

??(Aｉ*.....*Ak）＊(Ａk+1*...．.Aｊ)的数乘次数＊/

?if(t<ｍ[i][j])

｛

?ｍ[ｉ］[ｊ]＝t；//将Ａi*....Aj的最少数乘次数存入m［i][j] ?s[i][j]=k;//将对应的断开位置ｋ存入ｓ[i][j］

????

??

?｝

?

???}

?}

?

｝

void tｒaceｂacｋ(int ｉ,int j,int s［]［Ｎ+1])／／用递归来实现输出得到最小数乘次数的表达式

{

ｉf(ｉ==ｊ)

?{

priｎtf("Ａ%d",i);

｝

?else

?{

?prｉntf（"("）；

??traceｂack(ｉ，ｓ［ｉ][j］,s）；

tｒaceｂack（ｓ[ｉ]［j]+1,j,s);

??printｆ(＂)＂)；

}

｝

ｖoid maiｎ(）

{

iｎｔn;//用来存储矩阵的个数

ｉnｔq［2*N］；/*用q数组来存储最原始的输入(各矩阵的行和列）,主要目的是为了检验这Ｎ个矩阵是否满足连乘的条件*/

?ｉnt p[N+1],ｆｌaｇ=１；/*用p［ｉ-1],ｐ[i］数组来存储A的阶数,flag用来判断这N个矩阵是否满足连乘＊/

?ｉｎｔm［N+1][N+1];// 用m[i][j]二维数组来存储Aｉ*....．．Aj的最小数乘次数

int s[N＋1][N+１]；//用s[ｉ][ｊ]来存储使Ai...．..Aj获得最小数乘次数对应的断开位置ｋ

?

printf("输入矩阵的个数(注：小于１０0)：＂）；

?scanｆ("％d",&n);

for（inｔi=０;i<=２*n-1；i＋＋)//各矩阵的阶数的输入先存入数组q中接受检验

{

?iｆ(ｉ%2==0)

?{

??printf("————————\ｎ");

?ｐrintf（"＊输入Ａ%ｄ的行:＂，(i／2)＋１）；

?else

{

??prｉnｔf（" ********列：＂);

?｝

scａnf(＂%d",&q[i]）;

?｝

?ｆoｒ（i=1;i<=２*ｎ－2；i++)/／矩阵连乘条件的检验?｛

??ｉf（i%2!=０＆＆q[i］!＝q[i+１])

?{

?fｌaｇ＝0；

??brｅak；

?}

?｝

for（int ｊ=1;j＜＝n-１;j++)

｛

?ｐ[ｊ]=q[2*j];

?}

?if(fｌaｇ!=0）

?{

??p[0]=ｑ[０］;

?ｐ[n］=ｑ［2＊n-１];

?mａtrixCｈain(p,ｍ,s）；

??prｉｎtｆ(＂式子如下：\n")；

?trａceｂack（1,ｎ,s);

ｐriｎtf("＼n＂);

prｉntｆ("最少数乘次数为%d\n＂,ｍ[1］［n]); ?}

?else

?｛

??ｐriｎtf（"这%d个矩阵不能连乘!\n＂,n);

｝

}

六、实验心得

通过本次实验，我较为透彻的理解了动态规划算法的几个基本步骤。完成实验后，我认为建立递归关系是很关键的一步,同时也是整个动态规划算法的精髓。掌握了递归的思想，就可以完成很多不必要的重复计算。

具体到矩阵连乘问题，关键是解决断开点k的位置和最少数乘次数。

总体来说,这次实验不仅让我基本掌握递归的思想，而且进一步提高了自己的自学能力和编程能力，代码运用Ｃ语言写出,可以很好的体会C语言和Ｃ+＋的不同点和相同点。我也体会到,想要理解一个新的算法，必须要通过自己不断的编写程序,不断的思考才能真正的领悟,因此我会不断朝着这个方向努力。