动态规划DP——矩阵连乘的最小计算量

1.问题分析

给定n个矩阵{A1,A2,A3,……,An},其中，Ai和Ai+1（i=1,2,3,……,n-1）是可乘的。矩阵乘法如图所示：

用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。

例如：

A1是M（5×10）的矩阵

A2是M（10×100）的矩阵

A3是M（100×2）的矩阵

那么有两种加括号的方法：

1. （A1A2）A3
2. A1（A2A3） 

第一种加括号方法的计算量：5×10×100+5×100×2=6000。
第二种加括号方法的计算量： 10×100×2+5×10×2=2100。

可以看出，不同加括号的方法，矩阵乘法的运算次数可能有巨大的差别！！！

2.算法设计 

 采用自底向上的方法求最优值。对于每一个小规模的子问题都求最优值，并记录最优策略（加括号的位置）。具体算法设计如下：

 

3.源代码 

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int max_size=111;  //矩阵的大小范围
int p[max_size]; //用来记录行列的数组
int m[max_size][max_size]; //记录子问题最优值的数组
int s[max_size][max_size];  //记录子问题最优策略的数组
int n; //矩阵的个数

void matrixchain()
{
    int i;//循环条件
    int j;//循环条件
    int r;//连乘的规模
    int k;//记录最优策略
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    //清空数组
    for (r=2;r<=n;r++) //r记录规模，从规模为2开始计算，只有一个矩阵的话计算量是0
    {
        for (i=1;i<=n-r+1;i++) //n-r+1 表示对应矩阵个数n的要多少次相乘次数
        {
            j=i+r-1;
            //j=i+1,i+2,i+3,i+4……
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
            //策略k=i的乘法次数
            s[i][j]=i;//子问题的最优策略是i
            for(k=i+1;k<j;k++)//从k到j的所有决策，求最优值，记录最优策略
            {
                int t=m[i][k]+m[k+i][j]+p[i-1]*p[k]*p[j];
                if(m[i][j]>t)
                {
                    m[i][j]=t; //记录最优值。
                    s[i][j]=k;//把最优策略记录。
                }
            }
        }
    }
}

void print(int i,int j)
{
    if(i==j)
    {
        cout << "A["<< i << "]";
        return;
    }
    cout << "(";
    print(i,s[i][j]);
    print(s[i][j]+1,j);
    //递归求解子问题打印括号。
    cout << ")";
}


int main()
{
    cout << "请输入矩阵的个数n："<< endl;
    cin >> n;
    int i;
    int j;
    cout << "请输入每个矩阵的行数和最后一个矩阵的列数："<<endl;
    for (i=0;i<=n;i++)
    {
        cin >>p[i];
    }
    matrixchain();
    print(1,n);
    cout << endl;
    cout << "最小计算量的值为："<<m[1][n]<<endl;
    return 0;
}

 

4.测试结果