矩阵连乘-白红宇

矩阵AB可乘的条件是矩阵A的列数等于矩阵B的行数

计算时，加括号方式，对计算量的影响很大

穷举搜索法：来搜索可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘最少的计算次序

1 分析最优解的结构

关键特征：计算A[1：n]的最优次序所包含的计算矩阵子链A[1：k]和 A[k+1:n]的次序也是最优的。

2 建立递归关系

当i=j时：m[i][j] = 0;

当i<j时，m[i][j] = m[i][k]+ m[k+1][j]+pi-1pkpj

3 计算最优值

时间复杂度O(n^3) 空间复杂度O(n^2)

4 构造最优解

。。。

代码：

#include
      
       using namespace std;const int MAX = 100; //p用来记录矩阵的行列，main函数中有说明 //m[i][j]用来记录第i个矩阵至第j个矩阵的最优解 //s[][]用来记录从哪里断开的才可得到该最优解int p[MAX+1],m[MAX][MAX],s[MAX][MAX];int n;//矩阵个数 void matrixChain(){     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 = r+i-1;//列的控制             //找m[i][j]的最小值，先初始化一下，令k=i             m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];             s[i][j]=i;             //k从i+1到j-1循环找m[i][j]的最小值             for(int k = i+1;k
       
        >n;     for(int i=0;i<=n;i++)cin>>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}     //输入：6 30 35 15 5 10 20 25     matrixChain();      traceback(1,n);     //最终解值为m[1][n];     cout<
        
         <

测试结果：

本文转自博客园xingoo的博客，原文链接：，如需转载请自行联系原博主。