矩阵连乘问题

问题】:矩阵链乘问题:给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i=1,2...,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
解题】:这里我采用的是动态划分算法:
设计动态规划算法的步骤。
(1)找出最优解的性质,并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息,构造最优解(由子结构的最优解得到原先大问题的最优解)。
解题关键】:将一系列相乘的矩阵(Ai....Aj)划分为两部分;即(AiAi+1...Ak)(Ak+1Ak+2....Aj),k的位置要保证左边括号和右边括号相乘的消耗最小。
思路】:这里我采用两种方法来实现:
(1)用三重for循环来实现:根据主对角线的方向及其右边与之平行的对角线方向,由上至下,从左到右分别求出C[i][j]的值,后面要求的值都可以根据前面所求的的值来求。
C[i][j]代表矩阵链Ai..Aj相乘的最小消耗。其中:c[i][i]=0,i=1,2,....n
求解的顺序如下:C[1][2],C[2][3],C[2][3],...,C[N-1][N],C[1][3],C[2][4]....C[N-2][N]..........C[N][N]
最后得到的C[N][N]的值就是我们所求的。
(2)备忘录方法(即递归算法):将整个矩阵链分成两部分,然后在分别对两边的子矩阵链递归调用算法。
程序代码】:两种方法都在其中:
#include<iostream.h>
#include<stdlib.h>
#include<limits.h>
#include<time.h>
#define MAX_VALUE 100
#define N 201 //连乘矩阵的个数(n-1)
#define random() rand()%MAX_VALUE   //控制矩阵的行和列的大小
int c[N][N], s[N][N], p[N];
int matrixchain(int n)    //3个for循环实现
{    for(int k=1;k<=n;k++)
        c[k][k]=0;
    for(int d=1;d<n;d++)
        for(int i=1;i<=n-d;i++)
        {    int j=i+d;
            c[i][j]=INT_MAX;
            for(int m=i;m<j;m++)
            {    int t=c[i][m]+c[m+1][j]+p[i-1]*p[m]*p[j];
                if(t<c[i][j])
                {
                    c[i][j]=t;
                    s[i][j]=m;
                }
            }
        }
    return c[1][n];
}
void Print(int s[][N],int i,int j) //  输出矩阵连乘积的计算次序
{    if(i==j)
        cout<<"A"<<i;
    else
    {
        cout<<"(";
        Print(s,i,s[i][j]);  // 左半部子矩阵连乘
        Print(s,s[i][j]+1,j);  //左半部子矩阵连乘
        cout<<")";
    }
}
int lookupchain(int i,int j)  //备忘录方法
{
    if(c[i][j]>0)
        return c[i][j];
    if(i==j)
        return 0;
    int u=lookupchain(i,i)+lookupchain(i+1,j)+p[i-1]*p[i]*p[j];
    s[i][j]=i;
    for(int k=i+1;k<j;k++)
    {
        int t=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j];
        if(t<u)
        {
            u=t;
            s[i][j]=k;
        }
    }
    c[i][j]=u;
    return u;
}
void main()
{
    srand((int)time(NULL));
    for(int i=0;i<N;i++)  //  随机生成数组p[],各个元素的值的范围:1~MAX_VALUE
        p[i]=random()+1;
    clock_t start,end;  
    double elapsed;
    start=clock();
    //cout<<"Count: "<<matrixchain(N-1)<<endl;   //3重for循环实现
    cout<<"Count: "<<lookupchain(1,N-1)<<endl;   //备忘录方法
    end=clock();
    elapsed=((double)(end-start));///CLOCKS_PER_SEC;
    cout<<"Time: "<<elapsed<<endl;
    Print(s,1,N-1);  //输出矩阵连乘积的计算次序
    cout<<endl;
}
总结】:两种算法的时间复杂度均为o(n3),,随着数据量的增多,备忘录方法消耗的时间越长;我觉得是由于递归算法,随着数据量增大,调用函数的次数也增大,语句被执行的时间也越多,因此调用函数消耗的时间也增多。

留言

Your email address will not be published. Required fields are marked *