Множење ланаца матрица

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

Постоји много опција зато што је множење матрица асоцијативно. Другим речима, без обзира на групацију производа резултат ће бити исти. На пример, ако имамо четири матрице 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²/2 различитих поднизова, где је n број матрица, простор за извршење овог задатка је разумно велики. Може се показати да овај једноставан трик смањује време извршавања на O(n³) са O(2ⁿ), што је више него довољно ефикасно за реалне апликације. Ово је динамичко програмирање одозго надоле.

Псеудокод без мемоизације:

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

• Напомена: први индекс за p је 0 и први индекс за m и s је 1.

Још једно решење је да предвидимо која ће нам цена требати и израчунамо је унапред. То функционише на следећи начин:

• За свако k од 2 до n, број матрица:
  • Израчунати минималну цену за сваки подниз дужине k користећи већ израчунате цене.

Код у Јави који користи индексе низова засноване на нули заједно са методом за штампање решеног редоследа операција:

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

Када смо то завршили имамо најмању могућу цену за цео низ. Иако је за то потребно O(n³) времена такође, овај приступ има практичне предности због тога што не захтева рекурзију, као ни тестирање да ли је нека вредност већ била израчуната, и можемо да сачувамо простор тако што ћемо одбацивати неке подрезултате који више нису потребни. Ово је динамичко програмирање одоздо нагоре - други начин на који овај проблем може бити решен.

Још ефикаснији алгоритам

Алгоритам објављен 1984. године од стране Хуа и Шинга постиже $n\log n$ сложеност. Они су показали како проблем множења ланаца матрица може бити трансформисан или редукован у проблем партиционисања конвексног многоугла у не пресецајуће троуглове.

Ова слика илуструје могуће триангулације шестоугла:

Такође, развили су алгоритам који налази оптимално решење за проблем партиционисања временске сложености $O(n\log n)$.

Генерализација

Иако се овај алгоритам не примењује добро на множење ланаца матрица он се може генерализовати за решавање апстрактнијег проблема: За дати линеарни низ обеката, асоцијативну бинарну операцију на тим објектима и начин за израчунавање цене извођења те операције над било која два дата објекта (као и све парцијалне резултате) наћи начин, са минималном ценом груписања објеката, за примену операције над низом.

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

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

Имплементације

• Javascript имплементација је доступна на Alex Le's Blog
• Javascript имплементација је доступна на Ateji PX
• Javascript имплементација која показује крајње m и s табеле и њихова међусобна израчунавања од стране Mikhail Simin
• Java имплементација доступна на Brian's Project Gallery
• MATLAB имплементација доступна на MATLAB Central

Литература

• 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. стр. 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). април 2003: 394—407. CS1 одржавање: Формат датума (веза)