矩阵链乘算法

Question

我正在阅读 Thoman Cormen 的 "Introduction to Algorithms"，但我在理解下面编写的算法时遇到问题。

        Matrix-Chain-Order(p)
        1 n ← length[p] − 1
        2 for i ← 1 to n
        3     do m[i, i] ← 0
        4     for l ← 2 to n                     //l is the chain length.
        5         do for i ← 1 to n − l + 1      // what is this?
        6                do j ← i + l − 1        // what is this?
        7                   m[i, j] ← ∞
        8                   for k ← i to j − 1
        9                       do q ← m[i, k] + m[k + 1, j] + pi−1pkpj
       10                          if q < m[i, j]
       11                            then m[i, j] ← q
       12                                s[i, j] ← k
       13 return m and s

现在，我知道算法是如何工作的了。我知道如何继续构建 table 等等。换句话说，我知道第 4 行之前发生了什么，我也知道 9 到 13 是关于什么的。不过，我在理解 "for" 循环的微妙之处时遇到了问题。第 4 到 8 行很难理解。在第 5 行中，为什么 i 上升到 n-l+1，为什么第 6 行中的 j 设置为 i+l-1。在第 7 行中，m[i, j] 被初始化以用于第 10 行中的比较，但随后第 8 行又是一个谜。

Answer 1

我刚刚浏览了 wikipedia 上的算法定义，它非常全面。我将尝试向您解释我是如何理解该解决方案的。

问题的症结在于我们基本上是在尝试 'parenthesise' 即优先考虑我们如何链接矩阵，以便最有效地相乘，这反映在这行代码中：

q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];

为了理解上述立场，首先让我们确定 i 和 j 在这里是固定的，即我们正在尝试计算 m[i,j] 或乘以矩阵的最有效方法 A[i..j] 和 k 是变量。

如果 i=1 和 j=3 矩阵是：

(A*B)*C //We are trying to establish where the outer most parenthesis should be

我们不知道它应该在哪里，因此我们尝试了所有的可能性并选择了 m[i,j] 最小化的组合。所以我们尝试：

i=1 and j=3
A*(B*C) //k=1
(A*B)*C //k=2

很明显 k 应该在 i 到 j-1 之间变化，这反映在循环中，因为我们尝试所有可能的组合并采用最有效的组合。所以对于任何 k 我们将有两个分区：A[i..k] 和 A[k+1...j]

因此 k 的这个分区的 A[i..j] 的乘法成本是：

 m[i,k]  //Minimum cost of multiplication of A[i..k]

 m[k+1,j] //Minimum cost of multiplication of A[k+1..j]

 p[i-1]*p[k]*p[j]; //Final cost of multiplying the two partitions i.e. A[i..k] and A[k+1..j], where p contains the dimensions of the matrices.

A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then, p[] = [10,30,5,60] i.e. Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

这就是动态规划的意义所在。所以我们尝试 k 的所有组合并计算 m[i,j] 但为此我们还需要计算 m[i,k] 和 m[k+1,j] 即我们将问题分解为更小的子问题，其中的概念链长进来。

因此，对于所有矩阵 A[i..n]，我们计算乘以长度为 l.

的较小矩阵链的最有效方法

l 的最小值显然是 2，最大的是 n，这是我们在像我解释的那样解决较小的子问题后得到的。

让我们来看看您难以理解的代码：

 for l ← 2 to n                     //l is the chain length.
  do for i ← 1 to n − l + 1      
  do j ← i + l − 1        
  m[i, j] ← ∞

现在让我们再次考虑一个包含 4 个矩阵的较小示例 H,I,J,K，您正在查看的第一个链长度为 2。因此在遍历矩阵数组时。

 A[1..4] = H,I,J,K //where A[1] = H and A[4] = K
 For l = 2
 Our loop should go from i=1 to i=3, as for every i we are looking at the chain of length 2.

 So when i = 1, we would compute
 m[1,2] i.e. minimum cost to multiply chain (H,I)

 and when i = 3, we would compute
 m[3,4] i.e. minimum cost to multiply chain (J,K)

当链长为 3 时，我们将有：

  For i=1, j=3
  m[i,j] -> m[1,3] i.e. minimum cost to multiply chain (H,I,J)

  For i=2, j=4
  m[i,j] -> m[2,4] i.e. minimum cost to multiply chain (I,J,K)

因此，当我们定义 i 不超过 n-l+1 和 j=i+l-1 时，我们确保我们覆盖了数组的所有元素并且不超过边界条件，即n 和 j 的数组大小定义了链的末端，从 i 开始，长度为 l.

所以问题归结为为某些 i 和 j 计算 m[i,j] ，正如我之前解释的那样，通过采用分区 k 并尝试所有k 的可能值，然后将 m[i,j] 重新定义为最小值，这就是它被初始化为 ∞.

的原因

我希望我的回答不会太长，它可以让您清楚地了解算法的流程，并帮助您理解动态规划的庞大性。

矩阵链乘算法

Matrix chain multiplication algorithm

algorithm

matrix

matrix-multiplication