Množenje lanaca matrica

Množenje lanaca matrica je problem optimizacije koji može biti rešen korišćenjem dinamičkog programiranja. Želimo naći najefikasniji način da pomnožimo niz matrica. Problem ne leži u izvođenju množenja, već u samom redosledu kojim bismo množenje vršili.

Postoji mnogo opcija zato što je množenje matrica asocijativno. Drugim rečima, bez obzira na grupaciju proizvoda rezultat će biti isti. Na primer, ako imamo četiri matrice A, B, C, D onda imamo

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

Ipak, način na koji grupišemo proizvode utiče na broj jednostavnih aritmetičkih operacija koje su potrebne da bi se proizvod izračunao. To se zove efikasnost. Na primer: Neka je A matrica 10×30, B je 30×5 i C je 5×60. Onda je:

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operacija A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operacija.

Jasno je da je prvi metod efikasniji. Sada kada smo identifikovali problem, pitanje je kako da odredimo optimalnu grupaciju proizvoda n matrica? Možemo da prođemo kroz svaku moguću grupaciju (gruba sila), ali bi ovo zahtevalo eksponencijalno vreme u ondosu na broj matrica, što je izuzetno sporo i nepraktično za veliko n (broj matrica). Rešenje, kao što ćemo da vidimo, jeste da rastavimo problem na nekoliko povezanih potproblema. Rešavanjem potproblema jedanput i korišćenjem tog rešenja više puta drastično možemo da smanjimo potrebno vreme. Ovo je poznato kao dinamičko programiranje.

Algoritam dinamičkog programiranja

Za početak, hajde da pretpostavimo da je sve što želimo da znamo kolika je minimalna cena, odnosno minimalni broj aritmetičkih operacija, potreban za množenje matrica. Ako množimo samo dve matrice, postoji samo jedan način da ih pomnožimo, tako da je minimalna cena - cena tog množenja. Generalno, možemo naći minimalne troškove pomoću sledećeg rekurzivnog algoritma:

• Uzmite niz matrica i razdvojte ih na dva podniza.
• Pronađite minimalne troškove množenja za svaki podniz.
• Saberite te troškove i dodajte cenu množenja dve matrice rezultata.
• Uradite ovo za svaku moguću poziciju na kojoj se niz matrica može podeliti, i uzmite najmanju.

Na primer, ako imamo četiri matrice A, B, C i D, možemo izračunati troškove potrebne da pronađemo svaku od (A)(BCD), (AB)(CD), i (ABC)(D), praveći rekurzivne pozive kako bismo našli minimalnu cenu izračunavanja ABC, AB, CD, i BCD. Zatim izaberemo najbolju. Još bolje, ovo doprinosi ne samo minimalnoj ceni, već i pokazuje najbolji način za izvođenje množenja: Grupisati na način koji podrazumeva najnižu ukupnu cenu, i raditi isto za svaki faktor.

Nažalost, ako se primeni ovaj algoritam otkrivamo da je to jednako sporo kao i naivni način pokušavanja svih permutacija. Šta je pošlo naopako? Odgovor leži u tome da je urađeno dosta suvišnog posla. Na primer, gore smo napravili rekurzivni poziv da pronađe najbolje cene za izračunavanje kako ABC tako i AB. Ali, pronalaženje najboljih troškova za izračunavanje ABC zahteva pronalaženje najboljih troškova za AB. Kako rekurzija raste u dubinu, sve je više nepotrebnih ponavljanja ovog tipa.

Jedno jednostavno rešenje se zove memoizacija: svaki put kada izračunamo minimalnu cenu koja je potrebna da se pomnože dva određena podniza, mi je zapamtimo. Ako se od nas ikada traži da izračunamo ponovo mi jednostavno vratimo već zapamćen odgovor i ne vršimo ponovno računanje. Pošto postoji oko n²/2 različitih podnizova, gde je n broj matrica, prostor za izvršenje ovog zadatka je razumno veliki. Može se pokazati da ovaj jednostavan trik smanjuje vreme izvršavanja na O(n³) sa O(2ⁿ), što je više nego dovoljno efikasno za realne aplikacije. Ovo je dinamičko programiranje odozgo nadole.

Pseudokod bez memoizacije:

// 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;
                }
            }
        }
    }
}

• Napomena: prvi indeks za p je 0 i prvi indeks za m i s je 1.

Još jedno rešenje je da predvidimo koja će nam cena trebati i izračunamo je unapred. To funkcioniše na sledeći način:

• Za svako k od 2 do n, broj matrica:
  • Izračunati minimalnu cenu za svaki podniz dužine k koristeći već izračunate cene.

Kod u Javi koji koristi indekse nizova zasnovane na nuli zajedno sa metodom za štampanje rešenog redosleda operacija:

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;
        }
    }
}

Kada smo to završili imamo najmanju moguću cenu za ceo niz. Iako je za to potrebno O(n³) vremena takođe, ovaj pristup ima praktične prednosti zbog toga što ne zahteva rekurziju, kao ni testiranje da li je neka vrednost već bila izračunata, i možemo da sačuvamo prostor tako što ćemo odbacivati neke podrezultate koji više nisu potrebni. Ovo je dinamičko programiranje odozdo nagore - drugi način na koji ovaj problem može biti rešen.

Još efikasniji algoritam

Algoritam objavljen 1984. godine od strane Hua i Šinga postiže $n\log n$ složenost. Oni su pokazali kako problem množenja lanaca matrica može biti transformisan ili redukovan u problem particionisanja konveksnog mnogougla u ne presecajuće trouglove.

Ova slika ilustruje moguće triangulacije šestougla:

Takođe, razvili su algoritam koji nalazi optimalno rešenje za problem particionisanja vremenske složenosti $O(n\log n)$.

Generalizacija

Iako se ovaj algoritam ne primenjuje dobro na množenje lanaca matrica on se može generalizovati za rešavanje apstraktnijeg problema: Za dati linearni niz obekata, asocijativnu binarnu operaciju na tim objektima i način za izračunavanje cene izvođenja te operacije nad bilo koja dva data objekta (kao i sve parcijalne rezultate) naći način, sa minimalnom cenom grupisanja objekata, za primenu operacije nad nizom.

Čest specijalni slučaj ovoga je nadovezivanje niski. Data nam je lista niski u programskom jeziku C, na primer, cena nadovezivanja dve niske dužina m i n korišćenjem strcat je O(m + n), zbog toga što nam je potrebno O(m) vremena da nađemo kraj prve niske i O(n) vremena da kopiramo drugu nisku na kraj prve. Korišćenjem ove funkcije cene možemo napisati algoritam za dinamičko programiranje kako bismo našli najbrži način da nadovežemo niz niski (iako je ovo prilično beskorisno, jer ih možemo nadovezati sve za vreme proporcionalno sumi njihovih dužina). Sličan problem postoji za jednostruko povezane liste.

Još jedna generalizacija je rešavanje problema kada nam je omogućeno više paralelnih procesora. U ovom slučaju umesto dodavanja cena izračunavanja svakog podniza, samo uzimamo maksimum, zbog toga što oba možemo uraditi istovremeno. Ovo drastično može uticati i na minimalnu cenu kao i na krajnje optimalno grupisanje; "balansiranija" grupisanja koja održavaju sve procesore zauzetim su poželjnija. Hejo Li et al. opisuje još prefinjenije pristupe.

Implementacije

• Javascript implementacija je dostupna na Alex Le's Blog
• Javascript implementacija je dostupna na Ateji PX
• Javascript implementacija koja pokazuje krajnje m i s tabele i njihova međusobna izračunavanja od strane Mikhail Simin
• Java implementacija dostupna na Brian's Project Gallery
• MATLAB implementacija dostupna na MATLAB Central

Literatura

• Cormen, Thomas H. (2001). „15.2: Matrix-chain multiplication”. Introduction to Algorithms. Second Edition. Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. MIT Press and McGraw-Hill. str. 331—338. ISBN 978-0-262-03293-3. 
• Viv. Dynamic Programming. A 1995 introductory article on dynamic programming.
• Heejo Lee, Jong Kim, Sungje Hong, and Sunggu Lee. Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems. IEEE Trans. on Parallel and Distributed Systems,. „Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems”. 14 (4). april 2003: 394—407. CS1 održavanje: Format datuma (veza)