java - 我认为维基百科上的 Java 矩阵链乘法算法不正确

Question

我几乎可以肯定维基百科页面上 matrixChainOrder 的 Java 实现，Matrix Chain Multiplication ， 是不正确的。我会改变它，但我不是一个合格的数学家，并且在没有首先审查我的观察的情况下做出改变是不舒服的。我想我要问的是——我的说法是否正确？ k 应该改为 k + 1，因为这个版本是用基于零的索引编写的，这与在同一页面上首次引入的伪代码版本不同。

protected int[][]m;
protected int[][]s;
public void matrixChainOrder(int[] p) {
    int n = p.length - 1;
    m = new int[n][n];
    s = new int[n][n];

    for (int ii = 1; ii < n; ii++) {
        for (int i = 0; i < n - ii; i++) {
            int j = i + ii;
            m[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k + 1; // <-- this is the necessary change 
                }
            }
        }
    }
}

编辑

我快要回答我自己的问题了，但这里有一个例子可以解释将算法转换为从零开始的索引所产生的问题:

给定数组 = [3,2,4,3,2]，这些是上面生成的成本表:

m:
0   24  42  48  
0   0   24  36  
0   0   0   24  
0   0   0   0   

s:
0   0   0   0   
0   0   1   2   
0   0   0   2   
0   0   0   0   

如果不将 1 加到 k(因为零索引偏移)，您会得到错误的矩阵链接位置。对于初学者，您不能将矩阵括在 0 处。 s 的正确输出应该是:

s:
0   1   1   1   
0   0   2   3   
0   0   0   3   
0   0   0   0

s[0][3] = 1 表示在 A(BCD) 处拆分 ABCD
s[1][3] = 3 表示在 A((BC)D) 处拆分 A(BCD)

就是这样 - 最优成本计算。

Answer 1

不，实现是正确的。将 s[i][j] = k; 更改为 s[i][j] = k + 1; 会破坏程序。

您可以通过将代码复制到一个名为 MatrixOrderOptimization.java 的文件并添加一个 main 函数来对此进行测试:

public static void main(String[] args) {
  MatrixOrderOptimization moo = new MatrixOrderOptimization();
  moo.matrixChainOrder(new int[]{ 3, 2, 4, 3, 2 });
  moo.printOptimalParenthesizations();
}

尝试在有或没有您建议的更改的情况下编译和运行程序。您会看到进行建议的更改会导致无效的索引值。

这是为什么？那么，解决方案值 s[i][j] 被定义为“达到最优成本的指标”。这就是它在伪代码中的名称，也是 Java 实现处理它的方式。

您指出，在伪代码中，索引从 1 开始，而在 Java 实现中，它们从 0 开始。但是，在这两种情况下，s[i][j] 的含义是实现最优成本的索引。

如果您通过添加一个来修改索引，您将放弃程序的其余部分。这样想:不是将 s[i][j] = k; 更改为 s[i][j] = k + 1;，而是更改数组在 printOptimalParenthesizations 中访问。在代码引用 s[i][j] 的每一行中，将其更改为 s[i][j]+1。

换句话说，替换

printOptimalParenthesizations(s, i, s[i][j], inAResult);
printOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);

与

printOptimalParenthesizations(s, i, s[i][j]+1, inAResult);
printOptimalParenthesizations(s, s[i][j]+1 + 1, j, inAResult);

这些更改的效果与您提议的更改完全相同。在这里，当我们将其从数组中拉出时，我们将其添加到最佳索引，而您建议将其插入数组时将其添加到最佳索引。

在这两种情况下，值都会变得不正确并且程序会崩溃。那是因为s[i][j]的意义不是最优索引加一。它只是最佳索引。

Java 程序期望 s 包含最佳索引，因为它理解最佳索引，这意味着它们从零开始。如果通过加一来更改这些值，就会违反索引的含义并破坏程序。