首页 > 代码库 > 矩阵连乘

矩阵连乘

动态规划——矩阵连乘的问题

《问题的引出》

看下面一个例子,计算三个矩阵连乘{A1,A2,A3};维数分别为10*100 , 100*5 , 5*50

按此顺序计算需要的次数((A1*A2)*A3):10X100X5+10X5X50=7500次

按此顺序计算需要的次数(A1*(A2*A3)):10X5X50+10X100X50=75000次

所以问题是:如何确定运算顺序,可以使计算量达到最小化。

枚举显然不可,如果枚举的话,相当于一个“完全加括号问题”,次数为卡特兰数,卡特兰数指数增长,必然不行。

《建立递归关系》

子问题状态的建模(很关键):令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。

显然如果i=j,则m[i][j]这段中就一个矩阵,需要计算的次数为0;

     如果i>j,则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j之间游荡,所以i<=k<j ;

代码实现时需要注意的问题:计算顺序!!!

因为你要保证在计算m[i][j]查找m[i][k]和m[k+1][j]的时候,m[i][k]和m[k+1][j]已经计算出来了。

观察坐标的关系如图:技术分享技术分享

算法实现:

#include<iostream>
#define MAX 100
#define min(a,b) (a<b)?a:b //定义一个取小值的函数
using namespace std;

int main()
{
    int n,i,r,j,k;
    int a[MAX],times[MAX][MAX];
    int temp_val;
    cin>>n;           //n为输入矩阵个数
    for(i=0;i<=n;i++)
        cin>>a[i];    //a[]为输入的矩阵
    for(i=0;i<=n;i++)
        times[i][i]=0; //为正对角线赋初值
    
    for(r=2;r<=n;r++)  //r为矩阵连乘的个数,进行对角线循环
    {        
            k=n-r+1;
        for(i=1;i<=k;i++) //i是二维数组中的行 ,行循环
        {
            j=r+i-1;         //j为二维数组中的列 ,列循环
            times[i][j]=times[i+1][j]+a[i-1]*a[i]*a[j];// 计算从i~j的相乘次数
            for(k=i+1;t<j;t++)   
            {
                temp_val=times[i][k]+times[k+1][j]+a[i-1]*a[k]*a[j];//从i~j中找到断点
                times[i][j]=min(times[i][j],temp_val); //比较并找出最优解
             }
        }
    }
    cout<<times[1][n];  //输出最优解
    return 0;
}

//我还在写怎么完整输出,想到了就更新一下。

技术分享

 

矩阵连乘