dynamic-programming
Matrixketenvermenigvuldiging
Zoeken…
Recursieve oplossing
Matrixketenvermenigvuldiging is een optimalisatieprobleem dat kan worden opgelost met behulp van dynamisch programmeren. Gegeven een reeks matrices, is het doel om de meest efficiënte manier te vinden om deze matrices te vermenigvuldigen. Het probleem is eigenlijk niet om de vermenigvuldigingen uit te voeren, maar alleen om de volgorde van de betrokken matrixvermenigvuldigingen te bepalen.
Stel dat we twee matrices A1 en A2 dimensie m * n en p * q. Uit de regels van matrixvermenigvuldiging weten we dat,
- We kunnen A 1 en A 2 vermenigvuldigen als en alleen als n = p . Dat betekent dat het aantal kolommen van A 1 gelijk moet zijn aan het aantal rijen van A 2 .
- Als aan de eerste voorwaarde is voldaan en we vermenigvuldigen A 1 en A 2 , krijgen we een nieuwe matrix, laten we het A 3 van dimensie m * q noemen.
- Om A 1 en A 2 te vermenigvuldigen, moeten we enkele schaalvermenigvuldigingen uitvoeren. Het totale aantal schaalvermenigvuldigingen dat we moeten uitvoeren, is ( m * n * q ) of ( m * p * q ).
- A 1 * A 2 is niet gelijk aan A 2 * A 1 .
Als we drie matrices A1, A2 en A3 met dimensie n m *, n * p en p * q heffen, wordt A4 = A1 * A2 * A3 zal dimensie m * q. Nu kunnen we deze matrixvermenigvuldiging op twee manieren uitvoeren:
- Eerst vermenigvuldigen we A 1 en A 2 , daarna vermenigvuldigen we met A 3 . Dat wil zeggen: ( A 1 * A 2 ) * A 3 .
- Eerst vermenigvuldigen we A 2 en A 3 , dan vermenigvuldigen we met het resultaat A 1 . Dat is: A 1 * ( A 2 * A 3 ).
Je ziet dat de volgorde van de vermenigvuldiging hetzelfde blijft, dat wil zeggen dat we niet vermenigvuldigen ( A 1 * A 3 ) * A 2 omdat deze mogelijk niet geldig is. We veranderen alleen de haakjes om een set te vermenigvuldigen voordat we deze vermenigvuldigen met de resterende. Hoe we deze haakjes plaatsen, is belangrijk. Waarom? Laten we zeggen dat de dimensie van 3 matrices A 1 , A 2 en A 3 10 * 100 , 100 * 5 , 5 * 50 zijn . Vervolgens,
- Voor ( A 1 * A 2 ) * A 3 is het totale aantal schaalvermenigvuldigingen: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 keer.
- Voor A 1 * ( A 2 * A 3 ) is het totale aantal schaalvermenigvuldigingen: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 keer.
Voor het 2e type is het aantal scalervermenigvuldiging 10 keer het aantal van het 1e type! Dus als u een manier kunt bedenken om de juiste oriëntatie van haakjes te vinden die nodig is om de totale scaler-vermenigvuldiging te minimaliseren, zou dit zowel de tijd als het geheugen verminderen die nodig zijn voor matrixvermenigvuldiging. Dit is waar matrixketenvermenigvuldiging van pas komt. Hier zullen we ons niet bezighouden met de werkelijke vermenigvuldiging van matrices, we zullen alleen de juiste haakjesvolgorde vinden, zodat het aantal schaalvermenigvuldiging wordt geminimaliseerd. We zullen matrices A 1 , A 2 , A 3 ........ A n hebben en we zullen het minimum aantal scaler-vermenigvuldigingen vinden die nodig zijn om deze te vermenigvuldigen. We nemen aan dat de gegeven dimensies geldig zijn, dat wil zeggen dat deze voldoet aan onze eerste vereiste voor matrixvermenigvuldiging.
We zullen divide-and-conquer-methode gebruiken om dit probleem op te lossen. Dynamische programmering is nodig vanwege veel voorkomende subproblemen. Bijvoorbeeld: voor n = 5 hebben we 5 matrices A 1 , A 2 , A 3 , A 4 en A 5 . We willen het minimale aantal vermenigvuldiging ontdekken dat nodig is om deze matrixvermenigvuldiging uit te voeren A 1 * A 2 * A 3 * A 4 * A 5 . Laten we ons concentreren op een van de vele manieren: ( A 1 * A 2 ) * ( A 3 * A 4 * A 5 ).
Voor deze vinden we A links = A 1 * A 2 . A rechts = A 3 * A 4 * A 5 . Dan komen we erachter Een antwoord = A links * A rechts . Het totale aantal scalervermenigvuldigingen dat nodig is om een antwoord te vinden: = Het totale aantal scalervermenigvuldigingen dat nodig is om A links te bepalen + Het totale aantal scalervermenigvuldigingen dat nodig is om A rechts te bepalen + Het totale aantal scalervermenigvuldigingen dat nodig is om A links te bepalen * Een recht .
De laatste term, het totale aantal scalervermenigvuldigingen dat nodig is om A links te bepalen * A rechts kan worden geschreven als: Het aantal rijen in A links * het aantal kolommen in A links * het aantal kolommen in A rechts . (Volgens de 2e regel van matrixvermenigvuldiging)
Maar we kunnen de haakjes ook op andere manieren instellen. Bijvoorbeeld:
- A 1 * ( A 2 * A 3 * A 4 * A 5 )
- ( A 1 * A 2 * A 3 ) * ( A 4 * A 5 )
- ( A 1 * A 2 * A 3 * A 4 ) * A 5 etc.
Voor elke mogelijke gevallen bepalen we het aantal scaler-vermenigvuldiging dat nodig is om A links en A rechts te vinden , en vervolgens voor A links * A rechts . Als je een algemeen idee hebt over recursie, heb je al begrepen hoe je deze taak moet uitvoeren. Ons algoritme zal zijn:
- 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.
Waarom is dit een dynamisch programmeerprobleem? Om te bepalen ( A 1 * A 2 * A 3 ), als u al hebt berekend ( A 1 * A 2 ), is het in dit geval nuttig.
Om de status van deze recursie te bepalen, kunnen we zien dat we voor elk geval het aantal matrices moeten weten waarmee we samenwerken. Dus we hebben een begin en einde nodig . Omdat we verdeel en heers gebruiken, heeft ons basisscenario minder dan 2 matrices ( begin > = einde ), waar we helemaal niet hoeven te vermenigvuldigen. We hebben 2 arrays: rij en kolom . rij [i] en kolom [i] slaan het aantal rijen en kolommen op voor matrix A i . We hebben een array dp [n] [n] om de al berekende waarden op te slaan en te initialiseren met -1 , waarbij -1 staat voor de waarde die nog niet is berekend. dp [i] [j] staat voor het aantal schaalvermenigvuldigingen dat nodig is om A i , A i + 1 , ....., inclusief A j te vermenigvuldigen. De pseudo-code ziet eruit als:
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]
complexiteit:
De waarde van begin en einde kan variëren van 1 tot n . Er zijn n 2 verschillende toestanden. Voor elke status loopt de lus binnenin n keer. Totale tijdcomplexiteit: O(n³) en geheugencomplexiteit: O(n²) .