矩阵链乘法

    给定有n个要相乘的矩阵构成的序列（链）<A1,A2,A3,.......,An>，要计算乘积A1A2.....An。一组矩阵是加全部括号的。矩阵链加括号对运算的性能有很大影响。
      仅当两个矩阵A和B相容（即A的列数等于B的行数），才可以进行相乘运算。如果A是一个p×q矩阵，B是q×r矩阵，结果C是p×r的矩阵。计算C的时间由乘法运算次数决定的，次数为p×q×r。
      矩阵链乘法问题可表述为：给定n个矩阵构成的一个链<A1，A2，A3.......，An>，其中i=1,2,3,4.....,n，矩阵Ai的维数为Pi-1 ×Pi，对乘积A1A2A3.....An，以一种最小标量乘法次数的方式进行加全部括号。
      对AiAi+1.......Aj的任何家全部括号形式都将乘积在Ak和Ak+1之间分开，即计算矩阵Ai...k和Ak+1.....Aj，然后将他们相乘得到最终的乘积Ai.......j.加全括号的代价是Ai...k和Ak+1...j的代价之和，再加上两者相乘的代价。
      加全部括号最小代价的递归定义：
             m[i,j]=min{m[i,k] + m[k+1,j] + Pi-1 * Pk *Pj} ；i<j;            m[i,j]=0; i==j;
    计算最优代价时，使用辅助表m[n][n]来保存m[i][j]，使用s[n][n]来记录计算m[i][j]时取得的最优代价处的k值，即每一个表项s[i][j]都记录了对乘积AiAi+1......Aj在Ak和Ak+1之间进行分裂取得的最优加全部括号时的k值。
    全部代码如下：
[cpp] 
//计算矩阵链乘积所需的最有标量乘法次数 
void MATRIX_CHAIN_ORDER(int PArray[], int m[][PArrayLength], int s[][PArrayLength], int Length) 
{ 
    int n=Length-1;//表示有n个矩阵相乘 
    int temp=0;//临时变量 
    for (int i=1; i<Length; i++) 
    { 
        m[i][i]=0;//先将代价初始化为0；长度为1的链最小代价为0 
    } 
    for (int l=2; l<=n; l++)//从第二个链开始分别计算长度为2、3、。。n的链的最小代价 
    { 
        for (int i=1; i<=n-l+1; i++) 
        { 
            int j=i+l-1; 
            m[i][j]=0x7fffffff; 
            for(int k=i; k<j; k++)//逐个检验K值，找到最小代价的k值 
            { 
                temp=m[i][k]+m[k+1][j]+PArray[i-1]*PArray[k]*PArray[j]; 
                if (temp<m[i][j]) 
                { 
                    m[i][j]=temp; 
                    s[i][j]=k; 
                } 
            } 
        } 
    } 
} 
//构造一个最优解 
void PRINT_OPTIMAL_PARENS(int s[][PArrayLength], int i, int j) 
{ 
    if (i==j) 
    { 
        cout<<"A"<<i; 
    }  
    else 
    { 
        cout<<"("; 
        PRINT_OPTIMAL_PARENS(s, i, s[i][j]); 
        PRINT_OPTIMAL_PARENS(s, s[i][j]+1, j); 
        cout<<")"; 
    } 
} 
结果：

补充：软件开发 , C++ ,