9

我无法让分而治之的矩阵乘法工作。据我了解，您将大小为 nxn 的矩阵拆分为象限（每个象限为 n/2），然后执行以下操作： 

C11 = A11⋅ B11 + A12 ⋅ B21   
C12 = A11⋅ B12 + A12 ⋅ B22  
C21 = A21 ⋅ B11 + A22 ⋅ B21  
C22 = A21 ⋅ B12 + A22 ⋅ B22

我的分而治之的输出非常大，我无法解决问题，因为我对递归不是很好。

示例输出：

原始矩阵 A： 

4 0 4 3   
5 4 0 4   
4 0 4 0  
4 1 1 1

一个×一个

古典： 

44 3 35 15  
56 20 24 35  
32 0 32 12  
29 5 21 17

分而治之： 

992 24 632 408  
1600 272 720 1232   
512 0 512 384  
460 17 405 497

有人可以告诉我我在分而治之方面做错了什么吗？我所有的矩阵都是int[][]，经典方法是传统的 3 for 循环矩阵乘法

4

4 回答 4

5

您divideAndConquer以错误的方式递归调用。您的函数所做的是对矩阵进行平方。为了使分治矩阵乘法起作用，它需要能够将两个可能不同的矩阵相乘。

它应该看起来像这样：

private static int[][] divideAndConquer(int[][] matrixA, int[][] matrixB){
    if (matrixA.length == 2){
         //calculate and return base case
    }
    else {
        //make a11, b11, a12, b12 etc. by dividing a and b into quarters      
        int[][] c11 = addMatrix(divideAndConquer(a11,b11),divideAndConquer(a12,b21));
        int[][] c12 = addMatrix(divideAndConquer(a11,b12),divideAndConquer(a12,b22));
        int[][] c21 = addMatrix(divideAndConquer(a21,b11),divideAndConquer(a22,b21));
        int[][] c22 = addMatrix(divideAndConquer(a21,b12),divideAndConquer(a22,b22));
        //combine result quarters into one result matrix and return
    }
}
于 2011-01-31T16:10:51.530 回答
2

Could someone tell me what I am doing wrong for divide and conquer?

Yes:

   int[][] a = divideAndConquer(topLeft);
   int[][] b = divideAndConquer(topRight);
   int[][] c = divideAndConquer(bottomLeft);
   int[][] d = divideAndConquer(bottomRight);

   int[][] c11 = addMatrix(classical(a,a),classical(b,c));
   int[][] c12 = addMatrix(classical(a,b),classical(b,d));
   int[][] c21 = addMatrix(classical(c,a),classical(d,c));
   int[][] c22 = addMatrix(classical(c,b),classical(d,d));

You are going through an extra multiplication step here: you shouldn't be calling both divideAndConquer() and classical().

What you are effectively doing is:

C11 = (A11^2)⋅(B11^2) + (A12^2)⋅(B21^2)
C12 = (A11^2)⋅(B12^2) + (A12^2)⋅(B22^2)
C21 = (A21^2)⋅(B11^2) + (A22^2)⋅(B21^2)
C22 = (A21^2)⋅(B12^2) + (A22^2)⋅(B22^2)

which is not correct.

  1. First, remove the divideAndConquer() calls, and replace a/b/c/d by topLeft/topRight/etc. See if it gives you the proper results.

  2. Your divideAndConquer() method needs a pair of input parameters, so you can use A*B. Once you get that working, get rid of the calls to classical(), and use divideAndConquer() instead. (or save them for matrices that are not a multiple of 2 in length.)

于 2011-01-31T13:34:56.193 回答
2

一些调试方法可以尝试：

  • 尝试一些非常简单的测试矩阵作为输入（例如全零，一个或几个战略矩阵）。您可能会在“失败”中看到一种模式，该模式会告诉您错误在哪里。

  • 确保你的“经典”方法给你正确的答案。对于小矩阵，您可以使用 Woflram Alpha 在线测试答案： http ://www.wolframalpha.com/examples/Matrices.html

  • 调试递归：printf()在函数的入口和出口处添加语句，包括调用参数。运行测试矩阵，将输出写入日志文件，然后使用文本编辑器打开日志文件。逐步检查每个案例，在编辑器中写下你的笔记，确保它在每个步骤中都能正常工作。添加更多printf()语句并在需要时再次运行。

祝家庭作业好运！

于 2011-01-31T02:42:18.703 回答
1

您可能会发现有关Strassen 算法的 Wiki 文章很有帮助。

于 2011-01-31T01:44:32.760 回答