动态规化算法之矩阵连乘

/*
 * Filename: matrix_chain.c
 *
 * Function: 矩阵连乘问题，其断开点的不同，计算次数会不同，找出使计算量最少的断开点。
 *
 * Note:     用动态规化算法实现
 *
 * Version: 1.0
 *
 * Author: WUSW
 * Date:   2009.4.24
 */

#include

#define COL 6

void matrix_chain( const int *p, size_t len, int m[][COL], size_t s[][COL] )
{
  size_t i = 0;
  size_t j = 0;
 
  for (i=0; i    {
      for (j=0; j    {
      m[i][j] = 0;
      s[i][j] = 0;
    }
    }

  size_t span = 0;
  size_t bp = 0;
  int sub_chn = 0;
 
  for (span=2; span<=COL; span++)
    {
      for (i=0; i<=len-span; i++)
    {
      j = i + span -1;

      m[i][j] = m[i+1][j] + p[i]*p[i+1]*p[j+1];
      s[i][j] = i;
     
      for (bp=i+1; bp        {
          sub_chn = m[i][bp] + m[bp+1][j] + p[i]*p[bp+1]*p[j+1];

          if (sub_chn < m[i][j])
        {
          m[i][j] = sub_chn;
          s[i][j] = bp;
        }
         
        }
    }
    }
 
}


int main(int argc, char * argv[])
{
  int p[] = {30, 35, 15, 5, 10, 20, 25} ;
  int m[COL][COL];
  size_t s[COL][COL];
 
  matrix_chain( p, COL, m, s );

  int i,j;
  for (i=0; i    {
      for (j=0; j    {
      printf( "%d ", m[i][j] );
    }
      printf( "\n" );
    }
 
  return 0;
 
}


/*
 * Filename: mem_matrix.c
 *
 * Function: 矩阵连乘问题，其断开点的不同，计算次数会不同，找出使计算量最少的断开点。
 *
 * Note:     用备忘录方法实现
 *
 * Version: 1.0
 *
 * Author: WUSW
 * Date:   2009.4.24
 */
#include

#define COL 6
size_t mem_matrix( const int *p, const int len, size_t i, size_t j,
             int m[][COL], size_t s[][COL] )
{
  if (i == j)
    {
      return 0;
    }
  if (m[i][j] > 0)
    {
      return m[i][j];
    }
 
  m[i][j] = mem_matrix( p, len, i+1, j, m, s ) + p[i]*p[i+1]*p[j+1];
  s[i][j] = i;
 
  size_t bp = 0; // best position
  int tmp_chain = 0;
   
  for (bp=i+1; bp    {
      tmp_chain = mem_matrix( p, len, i, bp, m, s ) +
    mem_matrix( p, len, bp+1, j, m, s ) + p[i]*p[bp+1]*p[j+1];
      if (tmp_chain < m[i][j])
    {
      m[i][j] = tmp_chain;
      s[i][j] = bp;
    }
    }
  return m[i][j];
 
}

int main(int argc, char * argv[])
{
  int p[] = {30, 35, 15, 5, 10, 20, 25} ;
  int m[COL][COL] = {{0}} ;
  size_t s[COL][COL] = {{0}};
 
  mem_matrix( p, COL, 0, 5, m, s );
 
  int i,j;
  for (i=0; i    {
      for (j=0; j    {
      printf( "%d ", m[i][j] );
    }
      printf( "\n" );
    }

  return 0;
 
}