dynamic-programming
Moltiplicazione della catena di matrici

Soluzione ricorsiva

La moltiplicazione della catena della matrice è un problema di ottimizzazione che può essere risolto utilizzando la programmazione dinamica. Data una sequenza di matrici, l'obiettivo è trovare il modo più efficiente per moltiplicare queste matrici. Il problema non è in realtà quello di eseguire le moltiplicazioni, ma semplicemente di decidere la sequenza delle moltiplicazioni di matrice coinvolte.

Diciamo che abbiamo due matrici A ₁ e A ₂ di dimensione m * n e p * q . Dalle regole della moltiplicazione della matrice, sappiamo che,

1. Possiamo moltiplicare A ₁ e A ₂ se e solo se n = p . Ciò significa che il numero di colonne di A ₁ deve essere uguale al numero di righe di A ₂ .
2. Se la prima condizione è soddisfatta e moltiplichiamo A ₁ e A ₂ , otterremo una nuova matrice, chiamiamola A ₃ di dimensione m * q .
3. Per moltiplicare A ₁ e A ₂ , dobbiamo fare alcune moltiplicazioni degli scalers. Il numero totale di moltiplicatori dello scaler, che dobbiamo eseguire è ( m * n * q ) o ( m * p * q ).
4. A ₁ * A ₂ non è uguale a A ₂ * A ₁ .

Se abbiamo tre matrici A ₁ , A ₂ e A ₃ aventi rispettivamente dimensione m * n , n * p e p * q , allora A ₄ = A ₁ * A ₂ * A ₃ avrà dimensione di m * q . Ora possiamo eseguire questa moltiplicazione di matrice in due modi:

• Per prima cosa moltiplichiamo A ₁ e A ₂ , quindi con il risultato moltiplichiamo A ₃ . Cioè: ( A ₁ * A ₂ ) * A ₃ .
• Per prima cosa moltiplichiamo A ₂ e A ₃ , quindi con il risultato moltiplichiamo A ₁ . Cioè: A ₁ * ( A ₂ * A ₃ ).

È possibile notare che l'ordine della moltiplicazione rimane lo stesso, ovvero non moltiplichiamo ( A ₁ * A ₃ ) * A ₂ perché potrebbe non essere valido. Modifichiamo solo la parentesi per moltiplicare un set prima di moltiplicarlo con il rimanente. Come poniamo queste parentesi sono importanti. Perché? Diciamo che la dimensione di 3 matrici A ₁ , A ₂ e A ₃ sono 10 * 100 , 100 * 5 , 5 * 50 . Poi,

1. Per ( A ₁ * A ₂ ) * A ₃ , il numero totale di moltiplicatori dello scaler è: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 volte.
2. Per A ₁ * ( A ₂ * A ₃ ), il numero totale di moltiplicatori dello scaler è: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 volte.

Per il 2 ° tipo il numero della moltiplicazione dello scaler è 10 volte il numero del 1 ° tipo! Quindi, se è possibile escogitare un modo per scoprire l'orientamento corretto delle parentesi necessarie per minimizzare la moltiplicazione dello scaler totale, ridurrebbe sia il tempo che la memoria necessari per la moltiplicazione della matrice. È qui che la moltiplicazione della catena di matrici è utile. Qui, non ci occuperemo della moltiplicazione effettiva delle matrici, scopriremo solo l'ordine di parentesi corretto in modo che il numero di moltiplicazione dello scaler sia ridotto al minimo. Avremo matrici A ₁ , A ₂ , A ₃ ........ A _n e scopriremo il numero minimo di moltiplicatori di scaler necessari per moltiplicarli. Assumiamo che le dimensioni date siano valide, ovvero soddisfa il nostro primo requisito per la moltiplicazione della matrice.

Useremo il metodo divide et impera per risolvere questo problema. La programmazione dinamica è necessaria a causa di sottoproblemi comuni. Ad esempio: per n = 5 , abbiamo 5 matrici A ₁ , A ₂ , A ₃ , A ₄ e A ₅ . Vogliamo scoprire il numero minimo di moltiplicazione necessario per eseguire questa moltiplicazione di matrice A ₁ * A ₂ * A ₃ * A ₄ * A ₅ . Tra i molti modi, concentriamoci su uno: ( A ₁ * A ₂ ) * ( A ₃ * A ₄ * A ₅ ).

Per questo, scopriremo A _left = A ₁ * A ₂ . A _destra = A ₃ * A ₄ * A ₅ . Quindi scopriremo una _risposta = A _sinistra * A _destra . Il numero totale di moltiplicatori dello scaler necessario per trovare una _risposta : = Il numero totale di moltiplicatori dello scaler necessarie per determinare A _sinistra + Il numero totale di moltiplicatori dello scaler necessarie per determinare A _destra + Il numero totale di moltiplicatori dello scaler necessarie per determinare A _sinistra * Un _diritto

L'ultimo termine, Il numero totale di moltiplicatori dello scaler necessarie per determinare A _sinistra * A _destra può essere scritto come: Il numero di righe in A _sinistra * il numero di colonne in A _sinistra * il numero di colonne in A _destra . (Secondo la seconda regola della moltiplicazione delle matrici)

Ma potremmo impostare la parentesi anche in altri modi. Per esempio:

• A ₁ * ( A ₂ * A ₃ * A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ ) * ( A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ * A ₄ ) * A ₅ ecc.

Per ogni caso possibile, determineremo il numero di moltiplicazione dello scalatore necessario per scoprire A _sinistra e A _destra , quindi A _sinistra * A _destra . Se hai un'idea generale sulla ricorsione, hai già capito come eseguire questa attività. Il nostro algoritmo sarà:

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

Perché questo è un problema di programmazione dinamica? Per determinare ( A ₁ * A ₂ * A ₃ ), se hai già calcolato ( A ₁ * A ₂ ), sarà utile in questo caso.

Per determinare lo stato di questa ricorsione, possiamo vedere che per risolvere per ogni caso, avremo bisogno di conoscere l'intervallo di matrici con cui stiamo lavorando. Quindi avremo bisogno di un inizio e di una fine . Dato che stiamo usando divide e conquista, il nostro caso base avrà meno di 2 matrici ( inizio > = fine ), dove non è necessario moltiplicare del tutto. Avremo 2 array: riga e colonna . la riga [i] e la colonna [i] memorizzeranno il numero di righe e colonne per la matrice A _i . Avremo una matrice dp [n] [n] per memorizzare i valori già calcolati e inizializzarla con -1 , dove -1 rappresenta il valore non ancora calcolato. dp [i] [j] rappresenta il numero di moltiplicatori dello scaler necessari per moltiplicare A _i , A _{i + 1} , ....., A _j inclusive. Lo pseudo-codice sarà simile a:

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

Complessità:

Il valore di inizio e fine può variare da 1 a n . Esistono n ² stati diversi. Per ogni stato, il ciclo interno verrà eseguito n volte. Complessità temporale totale: O(n³) e complessità della memoria: O(n²) .