Divide e Conquista moltiplicazione matrice

Question

Ho difficoltà a ottenere dividere e conquistare la moltiplicazione della matrice per funzionare. Da quello che ho capito, si dividono le matrici di dimensioni nxn in quadranti (ciascun quadrante è n/2) e poi si fa:

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

mia uscita per il divide et impera è davvero grande e sto avendo difficoltà a capire fuori il problema perché non sono molto bravo con la ricorsione.

output di esempio:

originale matrice A:

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

A X A

classica:

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

divide et impera:

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

Qualcuno potrebbe dirmi che cosa sto facendo male per dividere e conquistare? Tutte le mie matrici sono int[][] e il metodo classico è il tradizionale 3 per la moltiplicazione della matrice di loop

Answer 1

Stai ricorsivamente chiamando divideAndConquer nel modo sbagliato. Ciò che fa la tua funzione è una matrice quadrata. Affinché la moltiplicazione della matrice divide e conquisti funzioni, deve essere in grado di moltiplicare insieme due matrici potenzialmente differenti.

Dovrebbe essere qualcosa di simile:

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

Answer 2

È possibile trovare utile l'articolo Wiki su Strassen's algorithm.

Answer 3

Alcuni approcci debug provare:

• provare alcuni molto semplici matrici test come input (ad esempio tutti zeri, con uno o pochi quelli strategici). Potresti vedere uno schema nei "guasti" che ti mostreranno dove si trovano i tuoi errori.

• Assicurati che il tuo approccio "classico" ti dia risposte corrette. Per le piccole matrici, è possibile utilizzare Woflram Alpha on-line per verificare le risposte: http://www.wolframalpha.com/examples/Matrices.html

• Per eseguire il debug ricorsione: aggiungere printf() dichiarazioni all'entrata e all'uscita della funzione, tra gli argomenti di invocazione. Esegui la tua matrice di test, scrivi l'output in un file di registro e apri il file di registro con un editor di testo. Passa attraverso ogni caso, scrivendo le note insieme nell'editor assicurandosi che funzioni correttamente ad ogni passaggio. Aggiungere ulteriori informazioni printf() ed eseguire di nuovo se necessario.

Buona fortuna con i compiti!

Answer 4

Qualcuno potrebbe dirmi che cosa sto facendo male per dividere e conquistare?

Sì:

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

State attraversando una fase di moltiplicazione in più qui: non si dovrebbe essere chiamando sia divideAndConquer() e classical().

cosa si sta effettivamente facendo è:

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) 

che non è corretto.

1. primo luogo, rimuovere i divideAndConquer() chiamate, e sostituire a/b/c/d per topLeft/topRight/etc. Guarda se ti dà i risultati corretti.

2. Il metodo divideAndConquer() richiede una coppia di parametri di input, quindi è possibile utilizzare A * B. Una volta che hai funzionato, sbarazzati delle chiamate a classical() e usa invece divideAndConquer(). (O salvarli per le matrici che non sono un multiplo di 2 di lunghezza.)