Mátrixszorzási sorrend probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. július 31-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A mátrixszorzás sorrendjének problémája egy klasszikus dinamikus programozási probléma , amelyben mátrixok sorozata adott , és minimálisra kell csökkenteni a skaláris műveletek számát a szorzat kiszámításához. Feltételezzük, hogy a mátrixok kompatibilisek a mátrixszorzás szempontjából (azaz az oszlopok száma megegyezik a mátrix sorainak számával). ${\displaystyle A_{1},A_{2},\dots ,A_{n))$ $A_{i-1}$ $A_{i}$

A probléma részletes leírása

A mátrixszorzat egy asszociatív művelet, amely két k × m és m × n mátrixot vesz fel bemenetként, és kmn szorzási műveletek elköltésével egy k × n mátrixot ad vissza [1] .

Ha a mátrixok az egyik dimenzióban nagyok, a másikban kicsik, a skaláris műveletek száma erősen függhet a mátrixok szorzási sorrendjétől. Tegyük fel, hogy kapunk 3 10x100, 100x5 és 5x50 méretű mátrixot. Kétféleképpen lehet szorozni őket (zárójelbe tenni): és . Az első esetben 10 100 5 + 10 5 50 = 7500 skaláris szorzásra van szükségünk, a második esetben 100 5 50 + 10 100 50 = 75 000 szorzásra - a különbség nyilvánvaló. Ezért előnyösebb lehet egy kis időt eltölteni az előfeldolgozással, annak eldöntésével, hogy melyik sorrendben célszerű szaporítani, nem pedig közvetlenül a homlokon. ${\displaystyle A_{1},A_{2},A_{3))$ $((A_{1}A_{2})A_{3})$ $(A_{1}(A_{2}A_{3}))$

Így n mátrix adott: , , …, . Meg kell határozni, hogy milyen sorrendben szorozzuk őket, hogy a szorzási műveletek száma minimális legyen. $A_{1}:\,p_{0}\times p_{1}$ ${\displaystyle A_{2}:\,p_{1}\times p_{2))$ ${\displaystyle A_{n}:\,p_{n-1}\times p_{n))$

A probléma megoldása

Elemezzünk két megoldási módot a probléma megoldására, hogy megmutassuk, mennyire előnyös ebben az esetben a dinamikus programozás.

A zárójelek elhelyezési lehetőségeinek felsorolása

Becsüljük meg, hány elhelyezési lehetőséget kell rendezni. Jelölje a zárójelek elrendezésének számos módját egy n mátrixból álló sorozatban. Ha csak egy mátrix van, akkor nincs mit elrendezni, csak egy lehetőség van. Ha , akkor a zárójelbe tehető opciók száma az eredményül kapott mátrixot alkotó szorzatokban zárójelbe tehető opciók számának szorzata (vagyis ha , akkor a mátrixba beszerezhető opciók száma egyenlő a mátrix megszerzésének módjainak számának szorzatával . Particionálás mátrixokra, és végrehajtható a k-adik és a (k + 1)-edik mátrixok határán . Megkapjuk az ismétlődési relációt : $P(n)$ $n\geq 2$ $A_{3}=A_{1}*A_{2}$ $A_{3}$ $A_{1}$ $A_{2}$ $A_{1}$ $A_{2}$ $k=1,2,\pontok ,n-1$ $P(n)=\left\{{\begin{array}{ll}1,\ n=1\\\sum _{k=1}^{n-1}P(k)P(nk ),\n>=2\end{tömb}}\jobbra.$

A hasonló ismétlődési reláció megoldása egy katalán számsorozat , amely -vel nő . A függőség exponenciálisnak bizonyul, gyakorlati alkalmazásra alkalmatlan a programokban. Nézzünk egy ígéretesebb módszert. $\Omega \left({\frac {4^{n}}{n^{1.5}}}\jobbra)$

Dinamikus programozás

Feladat redukálása részfeladatokra

Jelölje a mátrixszorzás eredményét -vel , ahol i<=j. Ha i<j, akkor van egy k, amely felosztja a mátrixok és , i<=k<j között. Vagyis a kiszámításhoz először ki kell számítania , majd meg kell szoroznia őket. A k választása analóg a mátrixok közötti zárójelek elhelyezésével. Néhány k kiválasztásával a feladatot két hasonló részfeladatra redukáltuk az és a mátrixokra . ${\displaystyle 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))$

Rekurzív megoldás

Jelölje m[i, j] a skaláris szorzások minimális számát a mátrix kiszámításához . A következő ismétlődési összefüggést kapjuk: ${\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{tömb}}\jobbra.$

Egyszerűen magyarázható: ahhoz, hogy megtaláljuk az i=j mátrixok szorzatát, nem kell semmit tennie – ez maga a mátrix . Egy nem triviális esetben végigmegyünk a mátrix mátrixokra való felosztásának minden pontján, és megkeressük az ezekhez szükséges műveletek számát, majd megszorozzuk, hogy megkapjuk a mátrixot . (Egyenlő lesz az elköltött műveletek számával részfeladatok megoldásáról + a mátrixszorzás költsége ). Feltételezzük, hogy a mátrixok méretei a tömbben vannak megadva, a mátrix mérete pedig a . Szokás szerint a rekurzív módszer nem használható közvetlenül – az átfedő részfeladatok nagy száma miatt exponenciális lesz. ${\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))$ $p$ $A_{i}$ ${\displaystyle p_{i-1}\times p_{i))$

Dinamikus programozás

A részfeladatok számítási eredményeit m kétdimenziós tömbben tároljuk, hogy elkerüljük a már kiszámított részfeladatok újraszámítását. Számítások után a válasz m[1,n]-ben lesz (Hány szorzás szükséges egy 1-től n-ig terjedő mátrixsorozathoz - vagyis a feladat válasza) Az algoritmus bonyolultsága O lesz , hiszen van i, j : és osztott pontunk mindegyik opcióhoz. A részletek a megvalósításból derülnek ki. $\left(n^{3}\right)$ ${n \choose 2}$ $1\leq i\leq j\leq n$ $TOVÁBB)$

Megvalósítás

Jáva

A fő módszerben - egy példa a cikk elejéről. Ha lefut, a várt módon 7500-at ad ki.

public class MatrixChain { /* * Megadja a választ az optimális mátrixszorzási feladatra a * dinamikus programozás használatával. * A megoldás aszimptotikája az O(N^3) idő és az O(N^2) memória. * * @param p mátrixméretek tömbje, lásd a cikket * @return a probléma megoldásához szükséges skaláris szorzások minimális száma */ public static int multiplyOrder ( int [] p ) { int n = p . hossza - 1 ; int [][] dp = új int [ n ][ n ] ; for ( 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 ] = Egész szám . MAX_VALUE ; for ( 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 ] ); } } } return dp [ 0 ][ n - 1 ] ; } public static void main ( String [] args ) { int [] teszt = { 10 , 100 , 5 , 50 }; Rendszer . ki . println ( MatrixChain . multiplyOrder ( teszt )); } }

Csak azokat a módszereket adjuk meg, amelyek közvetlenül elvégzik a szükséges számításokat.

dataStore - osztály objektum, amely az összes adatot tárolja

Attribútumai a következők:

public Lista < Lista < int >> m ; //mátrix m public List < List < int >> s ; //mátrix public List < List < int >> eredmény ; //minden szorzás eredménye public List < List < List < int >>> source ; //2-dimenziós mátrixok (A0,A1,...,An) tömbje szorozandó public List < int > sizes = new List < int >(); //mátrixok méretei (így írva - 12,10,7,4 => 3 12x10,10x7,7x4 méretű mátrixot jelent) public string order = new string ( 'a' , 0 ); //a zárójelek helyes elhelyezése

A kód funkcionális részei:

//© Paulskit 2010.03.27 //módszer, amely megkeresi az m és s mátrixot (memória van lefoglalva nekik ott) private void matrixChainOrder (){ int n = dataStore . méretek . Szám - 1 ; //memória lefoglalása az m és s dataStore mátrixokhoz . m = új Lista < Lista < int >>(); dataStore . s = new Lista < Lista < int >>(); for ( int i = 0 ; i < n ; i ++){ dataStore . m . Add ( new List < int >()); dataStore . s . Add ( new List < int >()); //kitöltés nulla elemekkel for ( int a = 0 ; a < n ; a ++) { dataStore . m [ i ]. add ( 0 ); dataStore . s [ i ]. add ( 0 ); } } //az iteratív algoritmus végrehajtása int j ; for ( int l = 1 ; l < n ; l ++) { for ( 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 = adattár . m [ i ][ k ] + dataStore . m [ k + 1 ][ j ] + dataStore . méretek [ i ] * dataStore . méretek [ k + 1 ] * dataStore . méretek [ j + 1 ]; if ( q < dataStore . m [ i ][ j ]) { dataStore . m [ i ] [ j ] = q ; dataStore . s [ i ] [ j ] = k ; } } } } } //módszer - 2 mátrix egyszerű szorzása private List < List < int >> matrixMultiply ( Lista < Lista < int >> A , Lista < Lista < int >> B ) { int rowsA = A . gróf ; int oszlopokB = B [ 0 ]. gróf ; //A oszlopok száma == sorok száma B int oszlopokA = B . gróf ; //memóriafoglalás a "c"-hez Lista < Lista < int >> c = new Lista < Lista < int >>(); for ( int i = 0 ; i < sorokA ; i ++ ) { c . Add ( new List < int >()); for ( int a = 0 ; a < oszlopokB ; a ++) { c [ i ]. add ( 0 ); } } //végezzen szorzást for ( int i = 0 ; i < sorokA ; i ++) { for ( int j = 0 ; j < oszlopokB ; j ++) { for ( int k = 0 ; k < oszlopokA ; k ++ ) { c [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } } } //visszatérési érték return c ; } //módszer, amely közvetlenül a megfelelő sorrendben hajtja végre a szorzást //kezdetben így hívták //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 ]); Lista < Lista < int >> y = mátrixChainMultiply ( dataStore . s [ i ][ j ] + 1 , j ); return matrixMultiply ( x , y ); } else return dataStore . forrás [ i ]; } //metódus, amely kiír egy karakterláncot a zárójelek megfelelő elhelyezésével private 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 ); rendelés += ")" ; } }

Jegyzetek

Ez a probléma az RNS molekula szabad energiájának optimalizálásának problémájára redukálódik a bioinformatikában (itt az RNS monomerek sorában egy zárójelpár határozza meg a párosításukat). Hasonló dinamikus programozást valósítanak meg a Nussinov vagy Zucker algoritmusok .

↑ Vannak olyan algoritmusok is a kitöltött mátrixok szorzására, amelyek gyorsabbak, mint kmn , de rendkívül ritkán használják őket - a sebességnövekedés csak a 100 × 100 és nagyobb mátrixokon figyelhető meg. A ritka mátrixokat speciális, a mátrix egyik vagy másik formájára optimalizált algoritmusok szorozzák.

Irodalom

Thomas H. Kormen et al. Algoritmusok: konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Algoritmusok = Algoritmusok. - 1. kiadás - McGraw-Hill Science / Engineering / Math, 2006. - P. 336. - ISBN 0073523402 .