华北电力大学科技学院

实 验 报 告

实验名称         矩阵连乘问题                              

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

专业班级：软件12K1                                学生姓名：吴旭

学    号： 121909020124                          成    绩：

指导老师：刘老师                                 实验日期：2014.11.14

一、  实验内容

矩阵连乘问题，给定n个矩阵{A₁,A₂,…,A_n}，其中A_i与A_i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A₁,A₂,…,A_n。

二、  主要思想

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

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

(2) 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。

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

1、         分析最优解的结构

设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A_k和A_k+1之间将矩阵链断开，,则其相应的完全加括号方式为((A₁…A_k)(A_k+1…A_n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计算结果相乘得到A[1:n]。

2、         建立递归关系

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

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

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

3、         计算最优值

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

4、         构造最优解

算法matrixChain只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。S[i][j]中的数表明，计算矩阵链A[i:j]的最佳方式应在矩阵A_k和A_k+1之间断开，最优加括号方式为(A[i:k])(A[k+1:j])。依次构造最优解。(算法见实验代码部分)

三、  实验结果

四、  结果验证

对实验结果进行验证，4个矩阵分别是A₁[35*15]，A₂[15*5]，A₃[5*10]，A₄[10*20]。依递归式有：

M[1][4]=min

=7125     

且k=3。

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

五、  实验代码

#include<stdio.h>

#define N 100//定义最大连乘的矩阵个数是100

void matrixChain(int p[],int m[N+1][N+1],int s[N+1][N+1])/*用m[i][j]二维数组来存储Ai*.....Aj的最少数乘次数，

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

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

{

    int n=N;//定义m,s数组的都是n*n的，不用行列下标为0的元素，但包括在该数组中

    for(int i=1;i<=n;i++)

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

    for(int r=2;r<=n;r++)//r表示斜对角线的层数，从2取到n

    {

           for(int i=1;i<=n-r+1;i++)//i表示计算第r层斜对角线上第i行元素的值

           {

                  int j=i+r-1;//j表示当斜对角线层数为r，行下标为i时的列下标

                  m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//计算当断开位置为i时对应的数乘次数

                  s[i][j]=i;//断开位置为i

                  for (int k=i+1;k<j;k++)

                  {

                         int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];/*计算断开位置k为从i到j（不包括i和j）的所有取值对应的

                         （Ai*.....*Ak）*（Ak+1*.....Aj）的数乘次数*/

                         if(t<m[i][j])

                         {

                                m[i][j]=t;//将Ai*....Aj的最少数乘次数存入m[i][j]

                                s[i][j]=k;//将对应的断开位置k存入s[i][j]

                        

                        

                         }

                 

                  }

          

           }

   

   

    }

}

void traceback(int i,int j,int s[][N+1])//用递归来实现输出得到最小数乘次数的表达式

{

    if(i==j)

    {

           printf("A%d",i);

    }

    else

    {

           printf("(");

           traceback(i,s[i][j],s);

           traceback(s[i][j]+1,j,s);

           printf(")");

    }

}

void main()

{

    int n;//用来存储矩阵的个数

    int q[2*N];/*用q数组来存储最原始的输入（各矩阵的行和列），主要目的是为了检验这N个矩阵是否满足连乘的条件*/

    int p[N+1],flag=1;/*用p[i-1],p[i]数组来存储A的阶数，flag用来判断这N个矩阵是否满足连乘*/

    int m[N+1][N+1];// 用m[i][j]二维数组来存储Ai*......Aj的最小数乘次数

    int s[N+1][N+1];// 用s[i][j]来存储使Ai......Aj获得最小数乘次数对应的断开位置k

   

    printf("输入矩阵的个数(注：小于100)：");

    scanf("%d",&n);

    for(int i=0;i<=2*n-1;i++)//各矩阵的阶数的输入先存入数组q中接受检验

    {

           if(i%2==0)

           {

                  printf("————————\n");

                  printf("*输入A%d的行:",(i/2)+1);

           }

           else

           {

                  printf(" ********列:");

           }

           scanf("%d",&q[i]);

    }

    for(i=1;i<=2*n-2;i++)//矩阵连乘条件的检验

    {

           if(i%2!=0&&q[i]!=q[i+1])

           {

           flag=0;

           break;

           }

    }

    for(int j=1;j<=n-1;j++)

    {

           p[j]=q[2*j];

    }

    if(flag!=0)

    {

           p[0]=q[0];

           p[n]=q[2*n-1];

           matrixChain(p,m,s);

           printf("式子如下:\n");

           traceback(1,n,s);

           printf("\n");

           printf("最少数乘次数为%d\n",m[1][n]);

   

    }

    else

    {

           printf("这%d个矩阵不能连乘!\n",n);

    }

}

六、  实验心得

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

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

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

第二篇：矩阵连乘实验报告

南京信息工程大学  实验（实习）报告

院     计算机与软件学院     专业    软件工程       年级    2013    班次3       姓名   魏开阳      学号     20131344105      

一、 实验内容

矩阵连乘问题，给定n个矩阵{A₁,A₂,…,A_n}，其中A_i与A_i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A₁,A₂,…,A_n。

二、 主要思想

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

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

(2)   矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。

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

1、   分析最优解的结构

设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A_k和A_k+1之间将矩阵链断开，,则其相应的完全加括号方式为((A₁…A_k)(A_k+1…A_n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计算结果相乘得到A[1:n]。

2、   建立递归关系

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

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

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

3、   计算最优值

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

4、   构造最优解

算法matrixChain只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。S[i][j]中的数表明，计算矩阵链A[i:j]的最佳方式应在矩阵A_k和A_k+1之间断开，最优加括号方式为(A[i:k])(A[k+1:j])。依次构造最优解。(算法见实验代码部分)

一、 实验代码

#include<stdio.h>

#define N 100

void matrixChain(int p[],int m[N+1][N+1],int s[N+1][N+1])

/*用m[i][j]二维数组来存储Ai*.....Aj的最少数乘次数，用s[i][j]来存储使Ai.....Aj获得最少数乘次数对应的断开位置k，需要注意的是此处的N+1非常关键，虽然只用到的行列下标只从1到N，

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

{

  int n=N;

  for(int i=1;i<=n;i++)

      m[i][i]=0;

  for(int r=2;r<=n;r++)

  {

      for(int i=1;i<=n-r+1;i++)

      {

         int j=i+r-1;

         m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];

         s[i][j]=i;

         for (int k=i+1;k<j;k++)

         {

             int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

             if(t<m[i][j])

             {

                m[i][j]=t;

                 s[i][j]=k;

            

             }

        

         }

     

      }

 

 

  }

}

void traceback(int i,int j,int s[][N+1])

{

  if(i==j)

  {

      printf("A%d",i);

  }

  else

  {

      printf("(");

      traceback(i,s[i][j],s);

      traceback(s[i][j]+1,j,s);

      printf(")");

  }

}

void main()

{

  int n;

  int q[2*N];   int p[N+1],flag=1;   int m[N+1][N+1];

  int s[N+1][N+1];

 

  printf("输入矩阵的个数(注：小于100)：");

  scanf("%d",&n);

  for(int i=0;i<=2*n-1;i++)

  {

      if(i%2==0)

      {

         printf("————————\n");

         printf("*输入A%d的行:",(i/2)+1);

      }

      else

      {

         printf(" ********列:");

      }

      scanf("%d",&q[i]);

  }

  for(i=1;i<=2*n-2;i++)//矩阵连乘条件的检验

  {

      if(i%2!=0&&q[i]!=q[i+1])

      {

      flag=0;

      break;

      }

  }

  for(int j=1;j<=n-1;j++)

  {

      p[j]=q[2*j];

  }

  if(flag!=0)

  {

      p[0]=q[0];

      p[n]=q[2*n-1];

      matrixChain(p,m,s);

      printf("式子如下:\n");

      traceback(1,n,s);

      printf("\n");

      printf("最少数乘次数为%d\n",m[1][n]);

 

  }

  else

  {

      printf("这%d个矩阵不能连乘!\n",n);

  }

}

二、 实验结果

三、 结果验证

对实验结果进行验证，4个矩阵分别是A₁[35*15]，A₂[15*5]，A₃[5*10]，A₄[10*20]。依递归式有：

M[1][4]=min

=7125     

且k=3。

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

四、 实验心得

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

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

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