I think the Wikipedia Java Matrix chain multiplication algorithm is wrong

Question

I am pretty sure that the implementation of Java matrixChainOrder on the Wikipedia page "Multiplication of the matrix chain" is incorrect. I would change that, but I am not a very qualified mathematician, and I do not like to make changes without first polling my observation. I suppose I ask - am I right in this statement? k must be k + 1 , because this version is written in zero indexes, in contrast to the version of the pseudocode first introduced on the same page.

 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 } } } } } 

change

I almost answer my question, but here is an example that explains the problem that occurs when shifting the algorithm to the index based on zero:

Given an array = [3,2,4,3,2], these are the cost tables generated above:

 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 

Without adding 1 to k (due to a zero index shift), you get the wrong places for the matrix chain. You cannot copy matrices to 0 for starters. The correct output for s should be:

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

s [0] [3] = 1 means the division of ABCD into A (BCD)
s [1] [3] = 3 means the division of A (BCD) into A ((BC) D)

What is it - the calculation of the optimal cost.

Answer 1

No, the implementation is correct as it is. Change s[i][j] = k; to s[i][j] = k + 1; will break the program.

You can test this by copying the code to the MatrixOrderOptimization.java file and adding a main function like this one:

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

Try to compile and run the program with the proposed change and without it. You will see that making the proposed change leads to invalid index values.

Why is this? Well, the value of the solution s[i][j] is defined as "the index that has reached the optimal cost." This is what he called in pseudocode, and how the Java implementation understands it.

You indicate that in the pseudo-code, the indices begin with 1 and in the Java implementation they begin with 0. However, the value of s[i][j] in both cases is the index that has reached the optimal cost .

If you change the indexes by adding one, you drop the rest of the program. Think of it this way: instead of changing s[i][j] = k; on s[i][j] = k + 1; change the access to the array in printOptimalParenthesizations . On each line where the code refers to s[i][j] , change this to s[i][j]+1 .

In other words, replace

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

from

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

The effect of these changes exactly matches your proposed change. Here we add one to the optimal index when we pull it out of the array, while you suggest adding it to the optimal index when you insert it into the array.

In both cases, the value becomes incorrect, and the program crashes. This is because the value of s[i][j] not an optimal index plus one. This is just an optimal index.

The Java program expects s to contain optimal indices, since it understands optimal indices, which means that they start from scratch. If you change these values ​​by adding them, you violate the value of the indices and break the program.