Изворни код странице Множење ланаца матрица

'''Множење ланаца матрица''' је проблем оптимизације који може бити решен коришћењем [[Динамичко програмирање|динамичког програмирања]]. Желимо наћи најефикаснији начин да помножимо низ матрица. Проблем не лежи у ''извођењу'' ''множења'', већ у самом редоследу којим бисмо множење вршили. 

Постоји много опција зато што је множење матрица [[Асоцијативност|асоцијативно]]. Другим речима, без обзира на групацију производа резултат ће бити исти. На пример, ако имамо четири матрице A, B, C, D онда имамо 

(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = .... 

Ипак, начин на који групишемо производе утиче на број једноставних аритметичких операција које су потребне да би се производ израчунао. То се зове ''ефикасност''. На пример: Нека је A матрица 10×30, B је 30×5 и C је 5×60. Онда је: 

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 операција
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 операција.

Јасно је да је први метод ефикаснији. Сада када смо идентификовали проблем, питање је како да одредимо оптималну групацију производа ''n'' матрица? Можемо да прођемо кроз сваку могућу групацију (груба сила), али би ово захтевало експоненцијално време у ондосу на број матрица, што је изузетно споро и непрактично за велико ''n'' (број матрица). Решење, као што ћемо да видимо, јесте да раставимо проблем на неколико повезаних потпроблема. Решавањем потпроблема једанпут и коришћењем тог решења више пута драстично можемо да смањимо потребно време. Ово је познато као [[динамичко програмирање]].

== Алгоритам динамичког програмирања ==

За почетак, хајде да претпоставимо да је све што желимо да знамо колика је минимална цена, односно минимални број аритметичких операција, потребан за множење матрица. Ако множимо само две матрице, постоји само један начин да их помножимо, тако да је минимална цена - цена тог множења. Генерално, можемо наћи минималне трошкове помоћу следећег [[Рекурзија|рекурзивног алгоритма]]:
* Узмите низ матрица и раздвојте их на два подниза.
* Пронађите минималне трошкове множења за сваки подниз.
* Саберите те трошкове и додајте цену множења две матрице резултата.
* Урадите ово за сваку могућу позицију на којој се низ матрица може поделити, и узмите најмању.

На пример, ако имамо четири матрице ''A, B, C'' i ''D'', можемо израчунати трошкове потребне да пронађемо сваку од ''(A)(BCD)'', ''(AB)(CD)'', и ''(ABC)(D)'', правећи рекурзивне позиве како бисмо нашли минималну цену израчунавања ''ABC, AB, CD,'' и ''BCD''. Затим изаберемо најбољу. Још боље, ово доприноси не само минималној цени, већ и показује најбољи начин за извођење множења: Груписати на начин који подразумева најнижу укупну цену, и радити исто за сваки фактор.

Нажалост, ако се примени овај алгоритам откривамо да је то једнако споро као и наивни начин покушавања свих пермутација. Шта је пошло наопако? Одговор лежи у томе да је урађено доста сувишног посла. На пример, горе смо направили рекурзивни позив да пронађе најбоље цене за израчунавање како ''ABC'' тако и ''AB''. Али, проналажење најбољих трошкова за израчунавање ''ABC'' захтева проналажење најбољих трошкова за ''AB''. Како рекурзија расте у дубину, све је више непотребних понављања овог типа.

Једно једноставно решење се зове [[мемоизација]]: сваки пут када израчунамо минималну цену која је потребна да се помноже два одређена подниза, ми је запамтимо. Ако се од нас икада тражи да израчунамо поново ми једноставно вратимо већ запамћен одговор и не вршимо поновно рачунање. Пошто постоји око ''n''<sup>2</sup>/2 различитих поднизова, где је n број матрица, простор за извршење овог задатка је разумно велики. Може се показати да овај једноставан трик смањује време извршавања на O(''n''<sup>3</sup>) са O(2<sup>''n''</sup>), што је више него довољно ефикасно за реалне апликације. Ово је динамичко програмирање [[Top-down and bottom-up design|одозго надоле]].

Псеудокод<ref name="Cormen">{{Cite book|last=Cormen| first = Thomas H.
| others = Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
| title = Introduction to Algorithms
| volume = Second Edition
| chapter = 15.2: Matrix-chain multiplication
|pages=331–338
| publisher = MIT Press and McGraw-Hill|year=2001|isbn=978-0-262-03293-3}} Cormen et. al 2001</ref> без мемоизације:
<pre>
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
Matrix-Chain-Order(int p[])
{
    // length[p] = n + 1
    n = p.length - 1;
    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    // cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++) 
       m[i,i] = 0;

    for (L=2; L<=n; L++) { // L is chain length
        for (i=1; i<=n-L+1; i++) {
            j = i+L-1;
            m[i,j] = MAXINT;
            for (k=i; k<=j-1; k++) {
                // q = cost/scalar multiplications
                q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];
                if (q < m[i,j]) {
                    m[i,j] = q;
                    // s[i,j] = Second auxiliary table that stores k
                    // k      = Index that achieved optimal cost
                    s[i,j] = k;
                }
            }
        }
    }
}
</pre>
* Напомена: први индекс за ''p'' је 0 и први индекс за ''m'' и ''s'' је 1.
Још једно решење је да предвидимо која ће нам цена требати и израчунамо је унапред. 
То функционише на следећи начин:
* За свако ''k'' од 2 до ''n'', број матрица:
** Израчунати минималну цену за сваки подниз дужине ''k'' користећи већ израчунате цене.
Код у Јави који користи индексе низова засноване на нули заједно са методом за штампање решеног редоследа операција:
<pre>
public class MatrixOrderOptimization {
    protected int[][]m;
    protected int[][]s;
    public void matrixChainOrder(int[] p) {
        int n = p.length - 1;
        m = new int[n][n];
        s = new int[n][n];
        for (int i = 0; i < n; i++) {
            m[i] = new int[n];
            m[i][i] = 0;
            s[i] = new int[n];
        }
        for (int ii = 1; ii < n; ii++) {
            for (int i = 0; i < n - ii; i++) {
                int j = i + ii;
                m[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
    }
    public void printOptimalParenthesizations() {
        boolean[] inAResult = new boolean[s.length];
        printOptimalParenthesizations(s, 0, s.length - 1, inAResult);
    }
    void printOptimalParenthesizations(int[][]s, int i, int j,  /* for pretty printing: */ boolean[] inAResult) {
        if (i != j) {
            printOptimalParenthesizations(s, i, s[i][j], inAResult);
            printOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);
            String istr = inAResult[i] ? "_result " : " ";
            String jstr = inAResult[j] ? "_result " : " ";
            System.out.println(" A_" + i + istr + "* A_" + j + jstr);
            inAResult[i] = true;
            inAResult[j] = true;
        }
    }
}
</pre>
Када смо то завршили имамо најмању могућу цену за цео низ. Иако је за то потребно O(''n''<sup>3</sup>) времена такође, овај приступ има практичне предности због тога што не захтева рекурзију, као ни тестирање да ли је нека вредност већ била израчуната, и можемо да сачувамо простор тако што ћемо одбацивати неке подрезултате који више нису потребни. Ово је динамичко програмирање одоздо нагоре - други начин на који овај проблем може бити решен.

== Још ефикаснији алгоритам ==
Алгоритам објављен 1984. године од стране Хуа и Шинга постиже <math>n \log n</math> сложеност. Они су показали како проблем множења ланаца матрица може бити трансформисан или [[оксидо-редукција|редукован]] у проблем партиционисања конвексног многоугла у не пресецајуће троуглове. 
<ref>{{cite journal|last      = Hu|first     = T C.
|others = M T. Shing|title     = Computation of matrix chain products. Part II
|journal   = SIAM Journal on Computing
|volume    = 13
|issue     = 2|pages     = 228–251|publisher = Springer-Verlag
|location  = Univ. of California at San Diego
|year      = 1984|url       = ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf
|issn      = 0097-5397
|doi       = 10.1137/0213017
}}{{Мртва веза|date=10. 2018. |bot=InternetArchiveBot |fix-attempted=yes}}</ref>

Ова слика илуструје могуће триангулације шестоугла:
[[Датотека:Catalan-Hexagons-example.svg|400п|center]]
Такође, развили су алгоритам који налази оптимално решење за проблем партиционисања временске сложености <math>O(n \log n)</math>.

== Генерализација ==
Иако се овај алгоритам не примењује добро на множење ланаца матрица он се може генерализовати за решавање апстрактнијег проблема:
За дати линеарни низ обеката, асоцијативну бинарну операцију на тим објектима и начин за израчунавање цене извођења те операције над било која два дата објекта (као и све парцијалне резултате) наћи начин, са минималном ценом груписања објеката, за примену операције над низом.<ref>G. Baumgartner, D. Bernholdt, D. Cociorva, R. Harrison, M. Nooijen, J. Ramanujam and P. Sadayappan. A Performance Optimization Framework for Compilation of Tensor Contraction Expressions into Parallel Programs. 7th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS '02). Fort Lauderdale, Florida. 2002 available at http://citeseer.ist.psu.edu/610463.html</ref>

Чест специјални случај овога је [[String concatenation|надовезивање ниски]]. Дата нам је листа ниски у програмском језику [[C (програмски језик)|C]], на пример, цена надовезивања две ниске дужина ''m'' и ''n'' коришћењем ''strcat'' је O(''m''&nbsp;+&nbsp;''n''), због тога што нам је потребно O(''m'') времена да нађемо крај прве ниске и O(''n'') времена да копирамо другу ниску на крај прве. Коришћењем ове функције цене можемо написати алгоритам за динамичко програмирање како бисмо нашли најбржи начин да надовежемо низ ниски (иако је ово прилично бескорисно, јер их можемо надовезати све за време пропорционално суми њихових дужина). Сличан проблем постоји за [[Списак (структура података)|једноструко повезане листе]]. 

Још једна генерализација је решавање проблема када нам је омогућено више паралелних процесора. У овом случају уместо додавања цена израчунавања сваког подниза, само узимамо ''максимум'', због тога што оба можемо урадити истовремено. Ово драстично може утицати и на минималну цену као и на крајње оптимално груписање; "балансиранија" груписања која одржавају све процесоре заузетим су пожељнија. Хејо Ли et al. описује још префињеније приступе.

== Имплементације ==
* [[JavaScript|Javascript]] имплементација је доступна на [https://web.archive.org/web/20061216113204/http://alexle.net/stuff/dynamic-programming-matrix-multiplication/ Alex Le's Blog]
* Javascript имплементација је доступна на [https://web.archive.org/web/20130917225601/http://www.ateji.com/px/whitepapers.html Ateji PX]
* Javascript имплементација која показује крајње ''m'' и ''s'' табеле и њихова међусобна израчунавања од стране [https://web.archive.org/web/20130607045941/http://modoogle.com/matrixchainorder/ Mikhail Simin]
* [[Java (програмски језик)|Java]] имплементација доступна на [https://web.archive.org/web/20081119144233/http://www.brian-borowski.com/Matrix/ Brian's Project Gallery]
* [[MATLAB]] имплементација доступна на [http://www.mathworks.com/matlabcentral/fileexchange/27950 MATLAB Central] {{Wayback|url=http://www.mathworks.com/matlabcentral/fileexchange/27950 |date=20120406104516 }}

== Референце ==
{{reflist}}

== Литература ==
{{Литература|30em}}
* {{Cite book|last=Cormen| first = Thomas H. |others = Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein | title = Introduction to Algorithms | volume = Second Edition | chapter = 15.2: Matrix-chain multiplication | publisher = MIT Press and McGraw-Hill |year=2001|isbn=978-0-262-03293-3|pages=331–338}}
* Viv. [http://citeseer.ist.psu.edu/268391.html Dynamic Programming]. A 1995 introductory article on dynamic programming.
* Heejo Lee, Jong Kim, Sungje Hong, and Sunggu Lee. [https://web.archive.org/web/20110722132611/http://ccs.korea.ac.kr/pds/tpds03.pdf Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems]. ''IEEE Trans. on Parallel and Distributed Systems,''. {{cite journal|title=Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems|date=April 2003|url=|volume=14|issue=4|pages=394–407}}
{{Литература крај}}

{{нормативна контрола}}

[[Категорија:Оптимизациони алгоритми и методи]]
[[Категорија:Матрице]]
[[Категорија:Динамичко програмирање]]