链矩阵乘法：乘法算法不起作用

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 < x[0].length; k++) { 

到

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

应该解决这个问题。

Answer 2

此：

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

看起来应该通过调用B的结果乘以调用的结果，但在一般情况下，它没有。

x不是本地的，调用B通常会覆盖它，除非调用B立即遇到基本情况。

当你将数据传递给“侧面”而不是函数参数或函数返回值时，这种事情往往会发生。避免这种数据流往往是不合理的，但您应该避免这种情况，特别是因为它甚至不是您想要的。