动态规划求解矩阵计算的最优顺序.

时间：2025-02-19 08:08:19

摘要:(1)对于N个矩阵A1A2….AN的相乘求解,不同的计算顺序将会对计算的次数造成很大的影响.

基本思路:

[1]假设求解的矩阵是从ALeft到ARight每次选取一个边界矩阵Ai,计算Min(（ALeft*Ai）(Ai+1*ARight))(Left=
[2]同样利用数组记录相应的计算结果,从底向上求解.
[3]注意这里的构造过程,当我们计算A(Left,Right)时,我们需要知道每一个A(Left,Ai）和A(i+1,Right).直观的理解,就是对于某个长度的区间的问题求解,必须知道它所有子区间问题的解.从这个角度,我们可以思考出如何构造正确的循环,那就是在计算大的区间之前,就要将所有小的区间处理好,在处理长度为N的区间之间,一定要将所有长度为1到N-1的区间都求解.
#include ""
#define Infinity 10000000;
#define N 4
long int OptMatrix(int C[],int M[][N+1])
{
    int i,k,Left,Right;
    long int ThisM;
    for (Left = 1;Left<=N;Left++)
        M[Left][Left] = 0;
    for ( k = 1;k<N;k++)
    {
        for(Left = 1;Left<=N-k;Left++)
        {
            Right = Left + k;
            M[Left][Right] = Infinity;
            for(i = Left;i<=Right-1;i++)
            {
                ThisM = M[Left][i] + M[i+1][Right] + C[Left-1]*C[i]*C[Right];
            if (ThisM < M[Left][Right])
                M[Left][Right] = ThisM;
            }
        }

    }

    return M[1][N];
}

int _tmain(int argc, _TCHAR* argv[])
{

    int C[] = {50,10,40,30,5};
    int M[N+1][N+1];
    int min = OptMatrix(C,M);
    return 0;
}

相关文章