Problem med matrismultiplikationsordning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 juli 2019; kontroller kräver 5 redigeringar .

Problemet med matrismultiplikationsordningen är ett klassiskt dynamiskt programmeringsproblem där en sekvens av matriser ges och det krävs för att minimera antalet skalära operationer för att beräkna deras produkt. Matriserna antas vara kompatibla med avseende på matrismultiplikation (det vill säga antalet kolumner är detsamma som antalet rader i matrisen). ${\displaystyle A_{1},A_{2},\dots ,A_{n))$ $A_{i-1}$ ${\displaystyle A_{i))$

Detaljerad beskrivning av problemet

Matrisprodukt är en associativ operation som tar två k × m och m × n matriser som indata och returnerar en k × n matris genom att spendera kmn multiplikationsoperationer [1] .

När matriser är stora i en dimension och små i en annan, kan antalet skalära operationer bero mycket på i vilken ordning matriserna multipliceras. Låt oss säga att vi får 3 matriser med storlekarna 10x100, 100x5 respektive 5x50. Det finns två sätt att multiplicera dem (placera parenteser): och . I det första fallet behöver vi 10 100 5 + 10 5 50 = 7500 skalära multiplikationer, och i det andra fallet 100 5 50 + 10 100 50 = 75000 multiplikationer - skillnaden är uppenbar. Därför kan det vara mer lönsamt att lägga lite tid på att förbearbeta, bestämma i vilken ordning det är bäst att multiplicera, snarare än att multiplicera direkt på pannan. ${\displaystyle A_{1},A_{2},A_{3))$ $((A_{1}A_{2})A_{3})$ $(A_{1}(A_{2}A_{3}))$

Således ges n matriser: , , …, . Det krävs att man avgör i vilken ordning man multiplicerar dem så att antalet multiplikationsoperationer är minimalt. $A_{1}:\,p_{0}\times p_{1}$ ${\displaystyle A_{2}:\,p_{1}\times p_{2))$ ${\displaystyle A_{n}:\,p_{n-1}\ gånger p_{n))$

Lösning på problemet

Låt oss analysera 2 sätt att lösa problemet för att visa hur fördelaktigt dynamisk programmering är i det här fallet.

Räknar upp alla alternativ för att placera parenteser

Låt oss uppskatta hur många placeringsalternativ som behöver sorteras ut. Beteckna med antalet sätt att ordna parenteser i en sekvens bestående av n matriser. När det bara finns en matris så finns det inget att ordna, det finns bara ett alternativ. Om , då är antalet alternativ som kan placeras inom parentes produkten av antalet alternativ som kan placeras inom parentes i produkterna som utgör den resulterande matrisen (dvs. om , då är antalet alternativ som vi kan få matrisen lika med produkten av antalet sätt att få matrisen med antalet sätt att få ). Uppdelning i matriser, och kan utföras på gränsen för k-th och (k + 1)-th matriser för . Vi får upprepningsrelationen : $P(n)$ $n\geq 2$ $A_{3}=A_{1}*A_{2}$ $A_{3}$ $A_{1}$ $A_{2}$ $A_{1}$ $A_{2}$ $k=1,2,\dots ,n-1$ $P(n)=\left\{{\begin{array}{ll}1,\ n=1\\\summa _{k=1}^{n-1}P(k)P(nk ),\n>=2\end{array}}\right.$

Lösningen på en liknande återkommande relation är en sekvens av katalanska tal som ökar med . Beroendet visar sig vara exponentiellt, olämpligt för praktisk tillämpning i program. Låt oss titta på ett mer lovande sätt. $\Omega \left({\frac {4^{n}}{n^{1.5}}}\right)$

Dynamisk programmering

Reducera en uppgift till deluppgifter

Beteckna resultatet av matrismultiplikation med , där i<=j. Om i<j, så finns det ett k som delar upp mellan matriserna och , i<=k<j. Det vill säga, för att beräkna måste du först beräkna , sedan och sedan multiplicera dem. Valet av k är analogt med att placera parenteser mellan matriser. Genom att välja något k reducerade vi problemet till två liknande deluppgifter för matriserna och . $A_{i}A_{(i+1)}...A_{j}$ ${\displaystyle A_{i..j))$ ${\displaystyle A_{i..j))$ $A_k$ $A_{{k+1}}$ ${\displaystyle A_{i..j))$ ${\displaystyle A_{i..k))$ ${\displaystyle A_{k+1..j))$ ${\displaystyle A_{i..k))$ ${\displaystyle A_{k+1..j))$

Rekursiv lösning

Beteckna med m[i, j] det minsta antalet skalära multiplikationer för att beräkna matrisen . Vi får följande återfallsrelation: ${\displaystyle A_{i..j))$ $m[i,j]=\left\{{\begin{array}{ll}0,&i=j\\\min \limits _{i\leq k<j}\{m[i,k ]+m[k+1,j]+p_{i-1}p_{k}p_{j}\},&i<j\end{array}}\right.$

Det förklaras enkelt: för att hitta produkten av matriser för i=j behöver du inte göra någonting - det här är själva matrisen . I ett icke-trivialt fall går vi igenom alla punkter för att dela upp matrisen i matriser och letar efter antalet operationer som krävs för att få dem och multiplicerar sedan för att få matrisen . (Det kommer att vara lika med antalet operationer som spenderas om att lösa delproblem + kostnaden för matrismultiplikation ). Vi antar att storleken på matriserna anges i arrayen och storleken på matrisen är . Som vanligt kan den rekursiva metoden inte användas direkt - den kommer att vara exponentiell på grund av det stora antalet överlappande deluppgifter. ${\displaystyle A_{i..j))$ $A_{i}$ ${\displaystyle A_{i..j))$ ${\displaystyle A_{i..k))$ ${\displaystyle A_{k+1..j))$ ${\displaystyle A_{i..j))$ ${\displaystyle A_{i..k}A_{k+1..j))$ $sid$ $A_{i}$ ${\displaystyle p_{i-1}\times p_{i))$

Dynamisk programmering

Vi kommer att lagra resultaten av beräkningar för deluppgifter i en tvådimensionell array m för att undvika omräkning för redan beräknade deluppgifter. Efter beräkningar blir svaret i m[1,n] (Hur många multiplikationer krävs för en sekvens av matriser från 1 till n - det vill säga svaret på uppgiften) Algoritmens komplexitet blir O , eftersom vi har val i, j : och delade poäng för varje alternativ. Detaljerna kommer att framgå av implementeringen. $\left(n^{3}\right)$ ${n \choose 2}$ $1\leq i\leq j\leq n$ $PÅ)$

Implementering

Java

I huvudmetoden - ett exempel från början av artikeln. Om den körs kommer den att mata ut 7500 som förväntat.

public class MatrixChain { /* * Returnerar svaret på det optimala matrismultiplikationsproblemet med * dynamisk programmering. * Lösningens asymptotik är O(N^3) tid och O(N^2) minne. * * @param p array av matrisstorlekar, se artikel * @return minsta antal skalära multiplikationer som krävs för att lösa problemet */ public static int multiplyOrder ( int [] p ) { int n = p . längd - 1 ; int [][] dp = ny int [ n ][ n ] ; för ( int i = 0 ; i < n ; ++ i ) { dp [ i ][ i ] = 0 ; } for ( int l = 1 ; l < n ; ++ l ) { for ( int i = 0 ; i < n - l ; ++ i ) { int j = i + l ; dp [ i ][ j ] = Heltal . MAX_VALUE ; för ( int k = i ; k < j ; ++ k ) { dp [ i ][ j ] = Math . min ( dp [ i ][ j ] , dp [ i ][ k ] + dp [ k + 1 ][ j ] + p [ i ] * p [ k + 1 ] * p [ j + 1 ] ); } } } returnera dp [ 0 ][ n - 1 ] ; } public static void main ( String [] args ) { int [] test = { 10 , 100 , 5 , 50 }; System . ut . println ( MatrixChain . multiplyOrder ( test )); } }

Endast metoder som direkt utför nödvändiga beräkningar anges.

dataStore - klassobjekt som lagrar all data

Dess attribut är:

offentlig Lista < Lista < int >> m ; //matrix m public List < List < int >> s ; //matrix s public List < List < int >> resultat ; //resultat av alla multiplikationer offentlig Lista < Lista < Lista < int >>> källa ; //en array av 2-dimensionella matriser (A0,A1,...,An) som ska multipliceras offentlig Lista < int > storlekar = ny Lista < int >(); //storlekar på matriser (skrivet så här - 12,10,7,4 => betyder 3 matriser med storlekarna 12x10,10x7,7x4) offentlig strängordning = ny sträng ( ' a' , 0 ); //korrekt placering av konsoler

Funktionella delar av koden:

//© Paulskit 03/27/2010 //metod som hittar matrisen m och s (minne tilldelas för dem där) private void matrixChainOrder (){ int n = dataStore . storlekar . Räkna - 1 ; //allokera minne för matriserna m och s dataStore . m = ny lista < Lista < int >>(); dataStore . s = ny lista < Lista < int >>(); for ( int i = 0 ; i < n ; i ++){ dataStore . m . Lägg till ( ny lista < int >()); dataStore . s . Lägg till ( ny lista < int >()); //fyll med nollelement för ( int a = 0 ; a < n ; a ++) { dataStore . m [ i ]. lägg till ( 0 ); dataStore . s [ i ]. lägg till ( 0 ); } } //utför den iterativa algoritmen int j ; for ( int l = 1 ; l < n ; l ++) { för ( int i = 0 ; i < n - l ; i ++) { j = i + l ; dataStore . m [ i ][ j ] = int . MaxValue ; for ( int k = i ; k < j ; k ++) { int q = dataStore . m [ i ][ k ] + dataStore . m [ k + 1 ][ j ] + dataStore . storlekar [ i ] * dataStore . storlekar [ k + 1 ] * dataStore . storlekar [ j + 1 ]; if ( q < dataStore . m [ i ][ j ]) { dataStore . m [ i ] [ j ] = q ; dataStore . s [ i ] [ j ] = k ; } } } } } //metod - enkel multiplikation av 2 matriser privat Lista < List < int >> matrixMultiply ( List < List < int >> A , List < List < int >> B ) { int rowsA = A . räkna ; int kolumnerB = B [ 0 ]. räkna ; //kolumnantal av A == raderantal av B int kolumnerA = B . räkna ; //minnestilldelning för "c" List < List < int >> c = new List < List < int >>(); for ( int i = 0 ; i < raderA ; i ++) { c . Lägg till ( ny lista < int >()); för ( int a = 0 ; a < kolumnerB ; a ++) { c [ i ]. lägg till ( 0 ); } } //multiplicera för ( int i = 0 ; i < raderA ; i ++) { för ( int j = 0 ; j < kolumnerB ; j ++) { för ( int k = 0 ; k < kolumnerA ; k ++ ) { c [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } } } //returvärde retur c ; } //metod som direkt utför multiplikationen i rätt ordning //kallades ursprungligen så här //dataStore.result = matrixChainMultiply(0, dataStore.sizes.Count - 2); private List < List < int >> matrixChainMultiply ( int i , int j ) { if ( j > i ) { List < List < int >> x = matrixChainMultiply ( i , dataStore . s [ i ][ j ]); List < List < int >> y = matrixChainMultiply ( dataStore . s [ i ][ j ] + 1 , j ); return matrisMultiply ( x , y ); } annars returnerar dataStore . källa [ i ]; } //metod som skriver ut en sträng med rätt placering av parenteser privat void printOrder ( int i , int j ){ if ( i == j ) { order += "A" + i . ToString (); } else { order += "(" ; printOrder ( i , dataStore . s [ i ][ j ]); order += "*" ; printOrder ( dataStore . s [ i ][ j ] + 1 , j ); order += ")" ; } }

Anteckningar

Detta problem reduceras till problemet med att optimera den fria energin hos RNA- molekylen inom bioinformatik (här bestämmer ett par parenteser i raden av RNA-monomerer deras parning). Liknande dynamisk programmering implementeras i Nussinov- eller Zucker -algoritmerna .

↑ Det finns också algoritmer för multiplikation av fyllda matriser som är snabbare än kmn , men de används extremt sällan - hastighetsökningen observeras endast på matriser 100 × 100 och större. Glesa matriser multipliceras med speciella algoritmer optimerade för en eller annan form av matrisen.

Litteratur

Thomas H. Kormen et al Algoritmer: konstruktion och analys = INTRODUKTION TILL ALGORITHMER. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Algoritmer = Algoritmer. - 1:a uppl. - McGraw-Hill Science / Engineering / Math, 2006. - S. 336. - ISBN 0073523402 .