论坛 › 数据结构与算法 › 矩阵连乘的DP，两种方法(自下至上、自顶至下)

andalousie 发表于 2014-3-26 22:41:32

矩阵连乘的DP，两种方法(自下至上、自顶至下)

本帖最后由 andalousie 于 2014-3-26 22:42 编辑

基本上百度一下都可以搜到矩阵连乘的算法。大家写的都差不多是同一个思路(bottom-up DP，自下而上的动态规划)。这里再提供一个速度相仿的自上而下(top-down)的解法。代码属于C++。// See the Cormen book for details of the following algorithm
#include<iostream>
#include<cstdio>
#include<climits>

class MatrixChain
{
      int   n;
      int ** m;
      int ** s;
public:
      MatrixChain(int size)
                :n(size)
      {
                /* For simplicity of the program, one extra row and one extra column are
       allocated in m[][].0th row and 0th column of m[][] are not used */
                m = new int* ;
                s = new int* ;
                for (int t = 0; t <= n; ++t)
                {
                        m = new int;
                        s = new int;
                }
      }
      ~MatrixChain()
      {
                for (int t = 0; t <= n; ++t)
                {
                        delete [] m;
                        delete [] s;
                }
                delete [] s;
                delete [] m;
      }
      int MatrixChainOrder(int p[]);
      int MatrixChainOrderTD(int p[]);
      void traceback(int i, int j);
      int topdown(int p[], int i, int j);
};

// Matrix Ai has dimension p x p for i = 1..n
int MatrixChain::MatrixChainOrder(int p[])
{
    int i, j, k, L, q;

    /* m = Minimum number of scalar multiplications needed to compute
       the matrix AA...A = A where dimention of A is
       p x p */

    // cost is zero when multiplying one matrix.
    for (i = 1; i <= n; i++)
      m = 0;

    // L is chain length.
    for (L=2; L<=n; L++)   
    {
      for (i=1; i<=n-L+1; i++)
      {
            j = i+L-1;
            m = INT_MAX;
            for (k=i; k<=j-1; k++)
            {
                // q = cost/scalar multiplications
                q = m + m + p*p*p;
                if (q < m)
                              {
                  m = q;
                                        s = k;
                              }
            }
      }
    }
    return m;
}

// Matrix Ai has dimension p x p for i = 1..n
int MatrixChain::MatrixChainOrderTD(int p[])
{
    for (int i = 1; i <= n; i++)
      m = 0;
      for (int u = 0; u <= n; ++u)
                for (int v = 0; v <= n; ++v)
                        s = 0;

    int result = topdown(p, 1, n);
    return result;
}

void MatrixChain::traceback(int i, int j)
{
      if(i == j) return;
      traceback(i, s);
      traceback(s+1, j);
      std::cout << "A[" << i << ',' <<s
                << "] * A[" << s+1 << ',' << j
                << "]\n";
}

int MatrixChain::topdown(int p[], int i, int j)
{
      if(i != j)
      {
                if(s) return m;
                m = INT_MAX;
                int q;
                for(int k = i; k < j; ++k)
                {
                        q = topdown(p, i, k) + topdown(p, k + 1, j) + p*p*p;
                        if (q < m)
                        {
                              m = q;
                              s = k;
                        }
                }
      }
      return m;
}

int main()
{
      int arr[] = {3023, 3533, 155, 203, 2573, 3093};
      int size = sizeof(arr)/sizeof(arr) - 1;
      MatrixChain mc(size);
      printf("Minimum number of multiplications is %d \n",
                     mc.MatrixChainOrder(arr));
      printf("Minimum number of multiplications is %d \n",
                     mc.MatrixChainOrderTD(arr));
      mc.traceback(1, size);
      return 0;
}

查看完整版本: 矩阵连乘的DP，两种方法(自下至上、自顶至下)