Problém pořadí násobení matic

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 31. července 2019; kontroly vyžadují 5 úprav .

Problém řádu násobení matic je klasický problém dynamického programování , ve kterém je dána posloupnost matic a pro výpočet jejich součinu je nutné minimalizovat počet skalárních operací. Předpokládá se, že matice jsou kompatibilní s ohledem na násobení matic (to znamená, že počet sloupců je stejný jako počet řádků matice). ${\displaystyle A_{1},A_{2},\dots ,A_{n))$ $A_{i-1}$ ${\displaystyle A_{i))$

Podrobný popis problému

Maticový součin je asociativní operace, která přijímá dvě matice k × ma m × n jako vstup a vrací matici k × n vynaložením operací násobení kmn [1] .

Když jsou matice velké v jedné dimenzi a malé v jiné, počet skalárních operací může silně záviset na pořadí, ve kterém jsou matice násobeny. Řekněme, že máme 3 matice o velikostech 10x100, 100x5 a 5x50. Existují 2 způsoby, jak je vynásobit (umístit závorky): a . V prvním případě potřebujeme 10 100 5 + 10 5 50 = 7500 skalárních násobení a ve druhém případě 100 5 50 + 10 100 50 = 75 000 násobení - rozdíl je zřejmý. Proto může být výhodnější věnovat nějaký čas předzpracování, rozhodování, v jakém pořadí je nejlepší násobit, než množit přímo na čele. ${\displaystyle A_{1},A_{2},A_{3))$ $((A_{1}A_{2})A_{3})$ $(A_{1}(A_{2}A_{3}))$

Je tedy dáno n matic: , , …, . Je nutné určit, v jakém pořadí je násobit, aby počet operací násobení byl minimální. $A_{1}:\,p_{0}\times p_{1}$ $A_{2}:\,p_{1}\times p_{2}$ ${\displaystyle A_{n}:\,p_{n-1}\krát p_{n))$

Řešení problému

Pojďme analyzovat 2 způsoby řešení problému, abychom ukázali, jak přínosné je v tomto případě dynamické programování.

Výčet všech možností pro umístění závorek

Pojďme odhadnout, kolik možností umístění je třeba vyřešit. Označte počtem způsobů, jak uspořádat závorky do sekvence skládající se z n matic. Když je jen jedna matice, tak není co zařizovat, je jen jedna možnost. Jestliže , pak počet možností, které lze vložit do závorek, je součinem počtu možností, které lze vložit do závorek v součinech, které tvoří výslednou matici (tj. jestliže , pak počet možností, kterými můžeme matici získat, je rovná se součinu počtu způsobů, jak získat matici , počtem způsobů, jak získat ). Rozdělení do matic, a může být provedeno na hranici k-té a (k + 1)-té matice pro . Získáme vztah opakování : $P(n)$ $n\geq 2$ $A_{3}=A_{1}*A_{2}$ $A_{3}$ $A_{1}$ $A_{2}$ $A_{1}$ $A_{2}$ $k=1,2,\tečky ,n-1$ $P(n)=\left\{{\begin{array}{ll}1,\ n=1\\\sum _{k=1}^{n-1}P(k)P(nk ),\n>=2\end{array}}\right.$

Řešením podobného vztahu opakování je posloupnost katalánských čísel , která se zvyšuje jako . Závislost se ukazuje jako exponenciální, pro praktickou aplikaci v programech nevhodná. Podívejme se na slibnější způsob. $\Omega \left({\frac {4^{n}}{n^{1.5}}}\right)$

Dynamické programování

Redukce úkolu na dílčí úkoly

Výsledek násobení matice označíme , kde i <=j. Jestliže i<j, pak existuje k, které rozděluje mezi matice a , i<=k<j. To znamená, že pro výpočet musíte nejprve vypočítat , pak a pak je vynásobit. Volba k je analogická k umístění závorek mezi matice. Když jsme vybrali nějaké k, zredukovali jsme problém na dvě podobné dílčí úlohy pro matice a . ${\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))$

Rekurzivní řešení

Označme m[i, j] minimální počet skalárních násobení pro výpočet matice . Dostaneme následující vztah opakování: ${\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.$

Vysvětluje se to jednoduše: abyste našli součin matic pro i=j, nemusíte nic dělat – jde o samotnou matici . V netriviálním případě projdeme všechny body rozdělení matice na matice a vyhledáme počet operací potřebných k jejich získání a poté vynásobíme, abychom získali matici . (Bude se rovnat počtu vynaložených operací na řešení dílčích problémů + náklady na násobení matic ). Předpokládáme, že velikosti matic jsou uvedeny v poli a velikost matice je . Jako obvykle nelze rekurzivní metodu použít přímo – bude exponenciální kvůli velkému množství překrývajících se dílčích úkolů. ${\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))$

Dynamické programování

Výsledky výpočtů pro dílčí úkoly uložíme do dvourozměrného pole m, abychom se vyhnuli přepočtu na již vypočítané dílčí úkoly. Po výpočtech bude odpověď v m[1,n] (Kolik násobení je potřeba pro posloupnost matic od 1 do n - tedy odpověď na úlohu). Složitost algoritmu bude O , protože pro každou možnost máme volby i, j : a dělicí body. Podrobnosti vyplynou z realizace. $\left(n^{3}\right)$ ${n \choose 2}$ $1\leq i\leq j\leq n$ $NA)$

Implementace

Jáva

V hlavní metodě - příklad ze začátku článku. Pokud se spustí, vydá 7500 podle očekávání.

public class MatrixChain { /* * Vrátí odpověď na problém optimálního násobení matic pomocí * dynamického programování. * Asymptotika řešení je O(N^3) čas a O(N^2) paměť. * * @param p pole velikostí matic, viz článek * @return minimální počet skalárních násobení potřebných k vyřešení problému */ public static int multiplyOrder ( int [] p ) { int n = p . délka - 1 ; int [][] dp = new 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 ] = celé číslo . MAX_VALUE ; for ( int k = i ; k < j ; ++ k ) { dp [ i ][ j ] = Matematika . 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 [] test = { 10 , 100 , 5 , 50 }; Systém . ven . println ( MatrixChain . multiplyOrder ( test )); } }

Jsou uvedeny pouze metody, které přímo provádějí potřebné výpočty.

dataStore - objekt třídy, který ukládá všechna data

Jeho atributy jsou:

veřejný seznam < Seznam < int >> m ; //matice m public Seznam < Seznam < int >> s ; //matrix s public List < List < int >> vysledek ; //výsledek všech násobení public Seznam < Seznam < Seznam < int >>> zdroj ; //pole 2-rozměrných matic (A0,A1,...,An) k vynásobení public List < int > size = new List < int >(); //velikosti matic (zapsáno takto - 12,10,7,4 => znamená 3 matice o velikostech 12x10,10x7,7x4) public string order = new string ( 'a' , 0 ); //správné umístění závorek

Funkční části kódu:

//© Paulskit 03/27/2010 //metoda, která najde matici ma s (tam je pro ně alokována paměť) private void matrixChainOrder (){ int n = dataStore . velikosti . Počet - 1 ; //přidělení paměti pro matice ma s dataStore . m = new Seznam < Seznam < int >>(); dataStore . s = new Seznam < Seznam < int >>(); for ( int i = 0 ; i < n ; i ++){ dataStore . m . Add ( new List < int >()); dataStore . s . Add ( new List < int >()); //vyplňte nulovými prvky pro ( int a = 0 ; a < n ; a ++) { dataStore . m [ i ]. přidat ( 0 ); dataStore . s [ i ]. přidat ( 0 ); } } //provedení iteračního algoritmu 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 = dataStore . m [ i ][ k ] + dataStore . m [ k + 1 ][ j ] + dataStore . velikosti [ i ] * dataStore . velikosti [ k + 1 ] * dataStore . velikosti [ j + 1 ]; if ( q < dataStore . m [ i ][ j ]) { dataStore . m [ i ][ j ] = q ; dataStore . s [ i ] [ j ] = k ; } } } } } //metoda - jednoduché násobení 2 matic private List < List < int >> matrixMultiply ( Seznam < Seznam < int >> A , Seznam < Seznam < int >> B ) { int rowsA = A . počítat ; int sloupceB = B [ 0 ]. počítat ; //počet sloupců A == počet řádků B int sloupcůA = B . počítat ; // alokace paměti pro "c" Seznam < Seznam < int >> c = new Seznam < Seznam < int >>(); for ( int i = 0 ; i < rowsA ; i ++) { c . Add ( new List < int >()); for ( int a = 0 ; a < sloupceB ; a ++) { c [ i ]. přidat ( 0 ); } } //proveďte násobení pro ( int i = 0 ; i < rowsA ; i ++) { for ( int j = 0 ; j < columnsB ; j ++) { for ( int k = 0 ; k < columnsA ; k ++ ) { c [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } } } //návratová hodnota return c ; } //metoda, která přímo provádí násobení ve správném pořadí //zpočátku se nazývá takto //dataStore.result = matrixChainMultiply(0, dataStore.sizes.Count - 2); private List < List < int >> matrixChainMultiply ( int i , int j ) { if ( j > i ) { Seznam < Seznam < int >> x = matrixChainMultiply ( i , dataStore . s [ i ][ j ]); Seznam < Seznam < int >> y = matrixChainMultiply ( dataStore . s [ i ][ j ] + 1 , j ); return matrixMultiply ( x , y ); } else return dataStore . zdroj [ i ]; } //metoda, která vytiskne řetězec se správným umístěním závorek 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 ); objednávka += ")" ; } }

Poznámky

Tento problém je redukován na problém optimalizace volné energie molekuly RNA v bioinformatice (zde dvojice závorek v řadě RNA monomerů určuje jejich párování). Podobné dynamické programování je implementováno v Nussinovově nebo Zuckerově algoritmu .

↑ Existují také algoritmy pro násobení vyplněných matic, které jsou rychlejší než kmn , ale používají se extrémně zřídka - nárůst rychlosti je pozorován pouze u matic 100 × 100 a větších. Řídké matice jsou násobeny speciálními algoritmy optimalizovanými pro jednu nebo druhou formu matice.

Literatura

Thomas H. Kormen aj. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Algoritmy = Algoritmy. - 1. vyd. - McGraw-Hill Science / Engineering / Math, 2006. - S. 336. - ISBN 0073523402 .