チェーン行列乗算：乗算アルゴリズムが動作しない

Question

チェーン行列乗算を実装しました。私は正しいチェーンオーダーを取得しますが、実際の乗算をしている間は、与えられた乗算アルゴリズムは正しく動作していません。私のJavaコード：

package algopackage; 
import java.util.ArrayList; 
import java.util.List; 

public class ChainMatrixMultiplication { 

    static int s[][]; 

    static int x[][]; 

    static int y[][]; 

    public ChainMatrixMultiplication() { 
    } 

    static void chainMatrixMultiplication(int[] p) { 
     boolean isFirst = false; 
     int n = p.length-1; 
     int m[][] = new int[n][n]; 
     s = new int[n][n]; 
     for (int c = 0; c < n; c++) 
      m[c][c] = 0; 
     for (int counter = 1; counter < n; counter++) { 
      for (int i = 0;i < n; i++) { 
       isFirst = false; 
       int j = i + counter; 
       for (int k = i; k < j && j < n; k++) { 
        int result = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1]; 
        if (!isFirst) { 
         m[i][j] = result; 
         s[i][j] = k; 
         isFirst = true; 
        } else if (m[i][j] > result) { 
         m[i][j] = result; 
         s[i][j] = k; 
        } 
       } 
      } 
     } 
    } 

    static int[][] matrixMultiply(List<Matrix> matrices, int s[][], int i ,int j) { 
     if (i ==j) return matrices.get(i).getMatrix(); 
     else { 
      int k = s[i][j]; 
      x = matrixMultiply(matrices, s, i, k); 
      y = matrixMultiply(matrices, s, k+1, j); 
      return mult(x,y); 
     } 
    } 

    static int[][] mult(int[][] x, int[][] y) { 
     int [][] result = new int[x.length][y[0].length]; 

     /* Loop through each and get product, then sum up and store the value */ 
     for (int i = 0; i < x.length; i++) { 
      for (int j = 0; j < y[0].length; j++) { 
       for (int k = 0; k < x[0].length; k++) { 
        result[i][j] += x[i][k] * y[k][j]; 
       } 
      } 
     } 

     return result; 
    } 

    public static void main(String[] args) { 
     int p[] = {5,4,6,2}; 
     List<Matrix> matrices = new ArrayList<Matrix>(); 
     Matrix m1 = new Matrix(5,4); 
     int arr[] = {1,2,40,2,3,29,10,21,11,120,23,90,24,12,11,1,11,45,23,21}; 
     m1.addElementsToMatrix(5, 4, arr); 
     Matrix m2 = new Matrix(4,6); 
     int arr1[] = {1,1,1,2,3,12,12,3,10,12,12,29,22,11,22,11,11,11,13,1,2,12,4,2}; 
     m2.addElementsToMatrix(4, 6, arr1); 
     Matrix m3 = new Matrix(6,2); 
     int arr2[] = {1,1,12,3,22,11,13,1,2,12,12,12}; 
     m3.addElementsToMatrix(6, 2, arr2); 
     matrices.add(m1); 
     matrices.add(m2); 
     matrices.add(m3); 
     chainMatrixMultiplication(p); 
     matrixMultiply(matrices,s,0,2); 
    } 

} 

class Matrix { 

     private final int[][] matrix; 

     public Matrix(int rows, int cols) { 
      this.matrix = new int[rows][cols]; 
     } 

     public void addElementsToMatrix(int rows, int cols, int[] arr) { 
      int counter = 0; 
      for (int i = 0; i < rows; i++) { 
       for (int j = 0; j < cols; j++) { 
        matrix[i][j] = arr[counter++]; 
       } 
      } 

     } 

     public int[][] getMatrix() { 
      return matrix; 
     } 
} 

上記のコードmatrixMultiply（）関数は例外をスローしています。行列が期待通りに乗算されないため、例外が発生します。再帰は期待どおりに動作しないため。私はこのコードで何かを見逃しています。どんな助けも高く評価されます。ありがとう！

Answer 1

コードの正確性はわかりませんが、乗算した後に次元a * bとc * dの行列を掛け合わせると、行列の乗算結果を見ると、そこに次元a * dの行列が得られます

for (int k = 0; k < y[0].length; k++) { 

に

for (int k = 0; k < x[0].length; k++) { 

を変更することで問題を解決する必要があります。

Answer 2

この：それはコールBの結果によって、通話Aの結果を掛けなければならない。しかし、一般的に、そうでないよう

x = matrixMultiply(matrices, s, i, k); // call A 
y = matrixMultiply(matrices, s, k+1, j); // call B 
return mult(x,y); 

が見えます。

xはローカルではありません。コールBがすぐにベースケースに当たった場合を除いて、通常はコールBがそれを上書きします。

この種のことは、関数のパラメータまたは関数の戻り値ではなく、「側に」データを渡すときに発生する傾向があります。この種のデータフローを常に避けるのは妥当ではありませんが、ここでは避けるべきです。特に、それがあなたが望むものではないからです。