我认为维基百科上的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   

通过不向k添加1(因为零索引移位),您得到矩阵链的错误位置.对于初学者,您不能将矩阵括在0.s的正确输出应该是:

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

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

就是这样 - 最优的成本计算.

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 实现处理它的方式。

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

如果您通过添加 1 来修改索引，则会放弃程序的其余部分。这样想：不要更改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);

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

在这两种情况下，该值都会变得不正确并且程序崩溃。这是因为 的含义s[i][j]不是最优索引加一。简直就是最优指标。

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