***************************************转载请注明出处：http://blog.csdn.net/lttree********************************************

第二章：动态规划

矩阵连乘问题

算法描述：

给定n个矩阵{A1,A2,...,An},其中Ai 与 Ai+1 是可乘的，i=1,2, ... ,n-1。考察这n个矩阵的连乘积 A1A2, ... ,An。

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

完全加括号的矩阵连乘积可递归定义为：

<1> 单个矩阵是完全加括号的

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

例如：矩阵连乘积A1A2A3A4可以有以下5种不同的完全加括号方式：

①(A1(A2(A3A4)))②(A1((A2A3)A4))③((A1A2)(A3A4))④((A1(A2A3))A4)⑤(((A1A2)A3)A4)

每一种加括号方式对应一种矩阵连乘积的计算次序，最重要的是  该次序与计算量 有密切的关系。

算法分析：

>必要性：

先来看一下标准矩阵乘法的程序：

<span style="font-family:Comic Sans MS;">// 矩阵乘法 ra,ca为矩阵a的行列，rb,cb为矩阵b的行列
void matrixMultiply(int** a,int** b,int** c,int ra,int ca,int rb,int cb)
{
    // 检测两个矩阵是否可以相乘
    if( ca != rb )  return;
    
    for( int i = 0 ; i < ra ; ++i ) {
        for( int j = 0 ; j < cb ; ++j ) {
            int sum = a[i][0] * b[0][j];
            for( int k = 1 ; k < ca ; ++k )
                sum += a[i][k] * b[k][j];
            c[i][j] = sum;
        }
    }
}</span>

由此可以看出矩阵连乘积问题的必要性。它将会大大减少计算量。

>穷举法

穷举搜索法是最容易想到用来计算矩阵连乘问题的算法。也就是列出所有可能的计算次序，并计算出每一种次序需要的乘法次数，从中找出最小的计算次序。但这样做计算量太大。

对于n个矩阵连乘积，设有不同的计算次序P(n)。由于可以现在第k个和第k+1个矩阵之间将原矩阵序列分为两个子矩阵序列，然后分别对这两个子矩阵序列加括号，得到原矩阵序列的一种完全加括号方式。由此，可以得到关于P(n)的递归式如下：

解这个方程，可以得到P(n)实际上是 Catalan数，也就是说P(n)是随n的增长呈指数增长的。因此，穷举搜素法不是一个有效的算法。

>动态规划算法

①第一步：刻画问题的最优解的结构特征。（为节省起见，矩阵连乘积AiAi+1...Aj 简记为 A[i:j]）。因为计算A[1:n]的最优计算次序时，将它从中间分开，A[1:k]和A[k+1:n]（1≤k≤n），两组的次序各自也是最优的。因此，矩阵连乘积计算次序问题的最优解包含子问题的最优解。（这种性质称为最优子结构性质，问题的最优子结构性质也是该问题是否能用动态规划求解的显著特征）

②第二步：建立递归关系，总结为以下递归式：

③第三步：计算最优值

根据上面递归式，很容易写出算法来计算m[1][n]，详细见代码部分

④第四步：构造最优解

不仅仅要算出最优的乘了多少次，还要显示出来，哪些先开始计算，哪些需要后算。详细依旧看算法部分。

算法代码：

<span style="font-family:Comic Sans MS;">void MatrixChain( int p[],int n,int m[][7],int s[][7])
{
    int i,j,k,r,t;
    for( i = 1 ; i <= n ; ++i ) m[i][i]=0;
    for( r = 2 ; r <= n ; ++r ) {
        for( i = 1 ; i <= n-r+1 ; ++i ) {
            j = i+r-1;
            m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
            s[i][j] = i;

            // 和所有结合的情况比较，取最小的存入m[i][j]
            for( k = i+1 ; k < j ; ++k )    {
                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[][7] )
{
    if( i == j )    return;
    Traceback(i,s[i][j],s);
    Traceback(s[i][j]+1,j,s);
    cout<<"Mul A"<<i<<","<<s[i][j];
    cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
}

// 矩阵乘法 ra,ca为矩阵a的行列，rb,cb为矩阵b的行列
void matrixMultiply(int** a,int** b,int** c,int ra,int ca,int rb,int cb)
{
    // 检测两个矩阵是否可以相乘
    if( ca != rb )  return;

    for( int i = 0 ; i < ra ; ++i ) {
        for( int j = 0 ; j < cb ; ++j ) {
            int sum = a[i][0] * b[0][j];
            for( int k = 1 ; k < ca ; ++k )
                sum += a[i][k] * b[k][j];
            c[i][j] = sum;
        }
    }
}</span>

***************************************转载请注明出处：http://blog.csdn.net/lttree********************************************

算法重拾之路——矩阵连乘问题