前往顾页
以后地位: 主页 > 收集编程 > .Net实例教程 >

C#矩阵连乘问题实当代码

时候:2013-08-16 00:17来源:知行网www.zhixing123.cn 编辑:麦田守望者

问题】:矩阵链乘问题:给定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),,跟着数据量的增加,备忘录体例耗损的时候越长;我感觉是因为递归算法,跟着数据量增年夜,调用函数的次数也增年夜,语句被履行的时候也越多,是以调用函数耗损的时候也增加。

------分开线----------------------------
标签(Tag):C# C#实例教程 c#根本教程 C#源代码 c#技能
------分开线----------------------------
保举内容
猜你感兴趣