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

A x A

クラシック： 

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[][]あり、古典的な方法は、従来の3forループ行列の乗算です。

4

4 に答える 4

5

divideAndConquer間違った方法で再帰的に呼び出しています。関数が行うことは、行列を二乗することです。分割統治法の行列乗算が機能するためには、2つの潜在的に異なる行列を一緒に乗算できる必要があります。

次のようになります。

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

試すべきいくつかのデバッグアプローチ：

  • 入力としていくつかの非常に単純なテスト行列を試してください（たとえば、1つまたはいくつかの戦略的なものを含むすべてのゼロ）。「失敗」に、エラーがどこにあるかを示すパターンが表示される場合があります。

  • あなたの「古典的な」アプローチがあなたに正しい答えを与えていることを確認してください。小さな行列の場合、オンラインでWoflram Alphaを使用して回答をテストできます：http： //www.wolframalpha.com/examples/Matrices.html

  • 再帰をデバッグするには：printf()呼び出し引数を含め、関数の入口と出口にステートメントを追加します。テストマトリックスを実行し、出力をログファイルに書き込み、テキストエディタでログファイルを開きます。各ケースをステップスルーし、エディターでメモを書き、各ステップで正しく機能することを確認します。printf()さらにステートメントを追加し、必要に応じて再実行します。

宿題で頑張ってください！

于 2011-01-31T02:42:18.703 に答える
2

分割統治法で私が間違っていることを誰かに教えてもらえますか？

はい：

   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));

divideAndConquer()ここでは、追加の乗算ステップを実行しています。との両方を呼び出すべきではありませんclassical()。

あなたが効果的に行っていることは次のとおりです。

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)

これは正しくありません。

  1. まず、divideAndConquer()呼び出しを削除し、a / b / c/dをtopLeft/topRight/etcに置き換えます。適切な結果が得られるかどうかを確認してください。

  2. メソッドdivideAndConquer()には1組の入力パラメーターが必要なので、A*Bを使用できます。それが機能するようになったら、への呼び出しを取り除き、代わりclassical()に使用divideAndConquer()します。（または、長さが2の倍数ではない行列の場合はそれらを保存します。）

于 2011-01-31T13:34:56.193 に答える
1

Strassenのアルゴリズムに関するWikiの記事が役立つかもしれません。

于 2011-01-31T01:44:32.760 に答える