dynamic-programming
Multiplikation av matriskedja

Rekursiv lösning

Multiplikation av matriskedjor är ett optimeringsproblem som kan lösas med dynamisk programmering. Med tanke på en sekvens av matriser är målet att hitta det mest effektiva sättet att multiplicera dessa matriser. Problemet är faktiskt inte att utföra multiplikationerna, utan bara att bestämma sekvensen för de involverade matrismultiplikationerna.

Låt oss säga att vi har två matriser A ₁ och A ₂ med dimensionen m * n och p * q . Från reglerna för matrismultiplikation vet vi att

1. Vi kan multiplicera A ₁ och A ₂ om och bara om n = p . Att organ antalet kolumner i A ₁ måste vara lika med antalet rader av A _2.
2. Om det första villkoret är uppfyllt och vi multiplicerar A ₁ och A ₂ , får vi en ny matris, låt oss kalla det A ₃ med dimensionen m * q .
3. För att multiplicera A ₁ och A ₂ , måste vi göra några skalförökningar. Det totala antalet skalmultiplikationer som vi behöver utföra är ( m * n * q ) eller ( m * p * q ).
4. A ₁ * A ₂ är inte lika med A ₂ * A ₁ .

Om vi har tre matriser A ₁ , A ₂ och A ₃ med dimensionen m * n , n * p respektive p * q , kommer A ₄ = A ₁ * A ₂ * A ₃ att ha dimensionen m * q . Nu kan vi utföra denna matrismultiplikation på två sätt:

• Först multiplicerar vi A ₁ och A ₂ , sedan med resultatet multiplicerar vi A ₃ . Det är: ( A ₁ * A ₂ ) * A ₃ .
• Först vi multiplicera A ₂ och A _3, sedan med det resultat som vi multiplicera A _1. Det vill säga: A ₁ * ( A ₂ * A ₃ ).

Du kan märka att multiplikationens ordning förblir densamma, dvs. vi multiplicerar inte ( A ₁ * A ₃ ) * A ₂ eftersom det kanske inte är giltigt. Vi ändrar endast parentes för att multiplicera en uppsättning innan vi multiplicerar den med de återstående. Hur vi placerar dessa parenteser är viktiga. Varför? Låt oss säga, dimensionen av 3 matriser A ₁ , A ₂ och A ₃ är 10 * 100 , 100 * 5 , 5 * 50 . Sedan,

1. För ( A ₁ * A ₂ ) * A ₃ är det totala antalet skalmultiplikationer: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 gånger.
2. För A ₁ * ( A ₂ * A ₃ ) är det totala antalet skalmultiplikationer: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 gånger.

För den andra typen är antalet skalmultiplikationer 10 gånger antalet första typ! Så om du kan utforma ett sätt att ta reda på den korrekta orienteringen av parenteser som behövs för att minimera den totala skalan multiplikationen, skulle det minska både tid och minne som behövs för matrismultiplikation. Det är här matrixkedjeförstärkning är praktiskt. Här kommer vi inte att vara upptagen med den faktiska multiplikationen av matriser, vi kommer bara att ta reda på rätt parentesordning så att antalet skalmultiplikationer minimeras. Vi har matriser A ₁ , A ₂ , A ₃ ........ A _n och vi ska ta reda på det minsta antalet skalmultiplikationer som behövs för att multiplicera dessa. Vi antar att de givna dimensionerna är giltiga, dvs att det uppfyller vårt första krav på matrismultiplikation.

Vi använder divide-and-conquer-metoden för att lösa detta problem. Dynamisk programmering behövs på grund av vanliga delproblem. Till exempel: för n = 5, har vi 5 matriser A _1, A _2, A _3, A ₄ och A _5. Vi vill ta reda på det minsta antalet multiplikation som krävs för att utföra denna matrismultiplikation A ₁ * A ₂ * A ₃ * A ₄ * A ₅ . Låt oss koncentrera oss på ett av de många sätten: ( A ₁ * A ₂ ) * ( A ₃ * A ₄ * A ₅ ).

För detta hittar vi A _vänster = A ₁ * A ₂ . En _höger = A ₃ * A ₄ * A ₅ . Då får vi reda på ett _svar = A _vänster * A _höger . Det totala antalet skalmultiplikationer som behövs för att ta reda på ett _svar : = Det totala antalet skalmultiplikationer som behövs för att bestämma A _vänster + Det totala antalet skalmultiplikationer som behövs för att bestämma A _höger + Det totala antalet skalmultiplikationer som behövs för att bestämma A _vänster * En _rättighet .

Den sista termen, Det totala antalet skalmultiplikationer som behövs för att bestämma A _vänster * En _höger kan skrivas som: Antalet rader i A _vänster * antalet kolumner i A _vänster * antalet kolumner i A _höger . (Enligt den andra regeln om matrismultiplikation)

Men vi kan också ställa in parentesen på andra sätt. Till exempel:

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

För varje möjliga fall bestämmer vi antalet skalförstärkningar som behövs för att ta reda på A _vänster och A _höger , sedan för A _vänster * A _höger . Om du har en allmän idé om rekursion har du redan förstått hur du utför denna uppgift. Vår algoritm kommer att vara:

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

Varför är detta dynamiskt programmeringsproblem? För att bestämma ( A ₁ * A ₂ * A ₃ ), om du redan har beräknat ( A ₁ * A ₂ ), kommer det att vara till hjälp i det här fallet.

För att bestämma tillståndet för denna rekursion kan vi se att för att lösa för varje fall måste vi känna till matriserna vi arbetar med. Så vi behöver ett början och slut . När vi använder klyftan och erövra kommer vårt basfall att ha mindre än 2 matriser ( börja > = slut ), där vi inte behöver multiplicera alls. Vi har två matriser: rad och kolumn . rad [i] och kolumn [i] lagrar antalet rader och kolumner för matris A _i . Vi har en dp [n] [n] matris för att lagra de redan beräknade värdena och initialisera det med -1 , där -1 representerar att värdet inte har beräknats ännu. dp [i] [j] representerar antalet skalmultiplikationer som behövs för att multiplicera _Ai , A _{i + 1} , ....., A _j inklusive. Pseudokoden kommer att se ut:

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]

Komplexitet:

Värdet på början och slut kan variera från 1 till n . Det finns n ² olika tillstånd. För varje tillstånd kör slingan in n gånger. Total tidskomplexitet: O(n³) och minneskomplexitet: O(n²) .