algorithm - 矩阵链乘算法

Question

我正在阅读 Thoman Cormen 的“算法导论”，但我无法理解下面编写的算法。

        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

现在，我知道算法是如何工作的了。我知道如何继续构建表格等等。换句话说，我知道第 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 上的算法定义那里非常全面。我将尝试向您解释我是如何理解该解决方案的。

问题的症结在于我们基本上是在尝试“括号”，即优先考虑我们如何链接矩阵，以便最有效地相乘，这反射(reflect)在这行代码中:

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当我们尝试所有可能的组合并采用最有效的组合时，这反射(reflect)在循环中。所以对于任何 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 .

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

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