欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-03 14:29:23
...

1.问题分析

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

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

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

例如:

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。

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

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

2.算法设计 

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

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

 

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

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.测试结果 

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

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