欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划算法之矩阵连乘积问题2

程序员文章站 2022-07-03 14:40:51
...

在上篇文章当中,我们学习了矩阵的连乘积问题,并且得到了它的最少数乘次数矩阵和最佳断开位置矩阵,但是我们现在想直观的看到矩阵的加括号方式,不想在最佳断开位置矩阵里一个一个的对应去找,因此我们需要写一个更加直观的看到加括号方式的函数。

我们简单的分析一下(递归算法):

在s[1][n]的值我们知道A[1][n]最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n]),而此时,k=s[1][n]。同理可得A[1:s[1][n]]的最优加括号方式,此时i=1,j=s[1][n],k=s[i][j]=s[1][s[1][n]],代入有:(A[1:s[1][s[1][n]])(A[s[1][s[1][n]+1:s[1][n]],所以,我们就可以递推下去了。

代码如下:(代码来自于刘伟老师)

// 递归算法构造矩阵连乘积问题的最优解...
void AddMatrixChainBrackets( int i, int j, int **s )
{
  if ( i == j )
    return;
  AddMatrixChainBrackets( i, s[ i ][ j ], s ); // A[ i : k ]
  AddMatrixChainBrackets( s[ i ][ j ] + 1, j, s ); // A[ k + 1 : j ]
  printf("乘积 A%d,%d", i, s[ i ][ j ] );
  printf(" and A%d,%d\n", ( s[ i ][ j ] + 1 ), j );
}

我们用一个例题来演示一下,帮助大家更好的理解

动态规划算法之矩阵连乘积问题2

运行结果如下:

动态规划算法之矩阵连乘积问题2

这时我们就可以很明了的看到矩阵乘积的加括号方式(A(B(CD)))。