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

Question

我几乎可以肯定维基百科页面 Matrix Chain Multiplication 上 matrixChainOrder 的 Java 实现是不正确的。我会改变它，但我不是一个合格的数学家，并且在没有首先审查我的观察的情况下做出改变是不舒服的。我想我要问的是——我的说法是否正确？ 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]定义为"index that achieved optimal cost"。这就是它在伪代码中的名称，也是 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]的意思并不是最优指标加1。简直就是最佳指数.

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

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

I think the Java Matrix Chain Multiplication algorithm on Wikipedia is incorrect

java

algorithm

wikipedia

matrix-multiplication

编辑