Mnożenie łańcucha macierzy - Matrix chain multiplication

Mnożenie łańcuchów macierzy (lub problem porządkowania łańcuchów macierzy ) to problem optymalizacyjny dotyczący najefektywniejszego sposobu mnożenia danego ciągu macierzy . Problemem nie jest właściwie wykonanie mnożenia, ale jedynie określenie kolejności zastosowanych mnożeń macierzy. Problem można rozwiązać za pomocą programowania dynamicznego .

Istnieje wiele opcji, ponieważ mnożenie macierzy jest asocjacyjne . Innymi słowy, bez względu na to, jak produkt jest umieszczony w nawiasach , uzyskany wynik pozostanie taki sam. Na przykład dla czterech macierzy A , B , C i D istnieje pięć możliwych opcji:

(( AB ) C ) D =( A ( BC )) D =( AB )( CD )= A (( BC ) D )= A ( B ( CD )).

Chociaż nie ma to wpływu na iloczyn, kolejność, w jakiej terminy są umieszczane w nawiasach, wpływa na liczbę prostych operacji arytmetycznych potrzebnych do obliczenia iloczynu, czyli na złożoność obliczeniową . Na przykład, jeśli A to macierz 10 × 30, B to macierz 30 × 5, a C to macierz 5 × 60, to

obliczenie ( AB ) C wymaga (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operacji, natomiast

obliczenie A ( BC ) wymaga (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operacji.

Oczywiście pierwsza metoda jest bardziej wydajna. Dzięki tym informacjom sformułowanie problemu można uściślić jako „jak określić optymalne nawiasy iloczynu n macierzy?” Sprawdzenie każdego możliwego nawiasów ( brute force ) wymagałoby czasu wykonywania, który jest wykładniczy w liczbie macierzy, co jest bardzo powolne i niepraktyczne dla dużych n . Szybsze rozwiązanie tego problemu można osiągnąć, dzieląc problem na zestaw powiązanych podproblemów.

Dynamiczny algorytm programowania

Na początek załóżmy, że wszystko, co naprawdę chcemy wiedzieć, to minimalny koszt lub minimalna liczba operacji arytmetycznych potrzebnych do pomnożenia macierzy. Jeśli mnożymy tylko dwie macierze, jest tylko jeden sposób ich pomnożenia, więc minimalny koszt to koszt wykonania tego. Ogólnie rzecz biorąc, minimalny koszt możemy znaleźć za pomocą następującego algorytmu rekurencyjnego :

• Weź sekwencję macierzy i podziel ją na dwie podciągi.
• Znajdź minimalny koszt pomnożenia każdego podciągu.
• Dodaj te koszty razem i dodaj koszt pomnożenia dwóch macierzy wyników.
• Zrób to dla każdej możliwej pozycji, w której sekwencja macierzy może zostać podzielona, ​​i weź minimum nad nimi wszystkimi.

Na przykład, jeśli mamy cztery macierze ABCD , obliczamy koszt wymagany do znalezienia każdego z ( A )( BCD ), ( AB )( CD ) i ( ABC )( D ), wykonując wywołania rekurencyjne w celu znalezienia minimalnego kosztu obliczyć ABC , AB , CD i BCD . Następnie wybieramy najlepszą. Co więcej, daje to nie tylko minimalny koszt, ale także pokazuje najlepszy sposób wykonania mnożenia: pogrupuj go w sposób, który daje najniższy koszt całkowity, i zrób to samo dla każdego czynnika.

Jednak ten algorytm ma wykładniczą złożoność środowiska wykonawczego, co czyni go równie nieefektywnym, jak naiwne podejście polegające na próbowaniu wszystkich permutacji. Powodem jest to, że algorytm wykonuje dużo zbędnej pracy. Na przykład powyżej wykonaliśmy wywołanie rekurencyjne, aby znaleźć najlepszy koszt obliczania zarówno ABC, jak i AB . Ale znalezienie najlepszego kosztu obliczenia ABC wymaga również znalezienia najlepszego kosztu dla AB . W miarę pogłębiania się rekurencji pojawia się coraz więcej tego rodzaju niepotrzebnych powtórzeń.

Jedno proste rozwiązanie nazywa się zapamiętywaniem : za każdym razem, gdy obliczamy minimalny koszt potrzebny do pomnożenia określonego podciągu, zapisujemy go. Jeśli kiedykolwiek zostaniemy poproszeni o ponowne obliczenie, po prostu dajemy zapisaną odpowiedź i nie przeliczamy jej ponownie. Ponieważ istnieje około n ² /2 różnych podciągów, gdzie n jest liczbą macierzy, przestrzeń wymagana do tego jest rozsądna. Można wykazać, że ta prosta sztuczka sprowadza czas wykonania do O( n ³ ) z O(2 ⁿ ), co jest więcej niż wystarczająco wydajne dla rzeczywistych aplikacji. To jest programowanie dynamiczne zstępujące .

Poniższe podejście oddolne oblicza, dla każdego 2 ≤ k ≤ n, minimalne koszty wszystkich podciągów o długości k przy użyciu już obliczonych kosztów mniejszych podciągów. Ma takie samo asymptotyczne środowisko wykonawcze i nie wymaga rekurencji.

Pseudo kod:

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
MatrixChainOrder(int dims[])
{
    // length[dims] = n + 1
    n = dims.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]
    // The cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++)
        m[i, i] = 0;

    for (len = 2; len <= n; len++) { // Subsequence lengths
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
            m[i, j] = MAXINT;
            for (k = i; k <= j - 1; k++) {
                cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                if (cost < m[i, j]) {
                    m[i, j] = cost;
                    s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                }
            }
        }
    }
}

• Uwaga : Pierwszy indeks dla dims to 0, a pierwszy indeks dla m i s to 1.

Java realizacja zerowej indeksy tablic opartych wraz z metodą wygoda dla drukowania rozwiązany kolejność operacji:

public class MatrixOrderOptimization {
    protected int[][]m;
    protected int[][]s;
    public void matrixChainOrder(int[] dims) {
        int n = dims.length - 1;
        m = new int[n][n];
        s = new int[n][n];

        for (int lenMinusOne = 1; lenMinusOne < n; lenMinusOne++) {
            for (int i = 0; i < n - lenMinusOne; i++) {
                int j = i + lenMinusOne;
                m[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
                    if (cost < m[i][j]) {
                        m[i][j] = cost;
                        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;
        }
    }
}

Pod koniec tego programu mamy minimalny koszt pełnej sekwencji.

Wydajniejsze algorytmy

Istnieją algorytmy, które są bardziej wydajne niż algorytm programowania dynamicznego O ( n ³ ), chociaż są one bardziej złożone.

Hu i Szing (1981)

Algorytm opublikowany w 1981 przez Hu i Shing osiąga złożoność obliczeniową O ( n  log  n ) . Wykazały one, w jaki sposób problem mnożenie macierzy łańcuch może być przekształcony (lub zmniejszona ) na problem triangulacji z regularnego wielokąta . Wielokąt jest zorientowany w taki sposób, że istnieje pozioma strona dolna, zwana podstawą, która reprezentuje wynik końcowy. Pozostałe n boków wielokąta, w kierunku zgodnym z ruchem wskazówek zegara, reprezentują macierze. Wierzchołki na każdym końcu boku są wymiarami macierzy reprezentowanej przez ten bok. Przy n macierzach w łańcuchu mnożenia istnieje n -1 operacji binarnych i C _{n -1} sposobów umieszczania nawiasów, gdzie C _{n -1} jest ( n -1)-tą liczbą katalońską . Algorytm wykorzystuje, że istnieją również możliwe triangulacje C _{n -1} wielokąta o n +1 bokach.

Ten obraz ilustruje możliwe triangulacje regularnego sześciokąta . Odpowiadają one różnym sposobom umieszczania nawiasów w celu uporządkowania mnożenia dla iloczynu 5 macierzy.

W poniższym przykładzie są cztery strony: A, B, C i wynik końcowy ABC. A to macierz 10×30, B to macierz 30×5, C to macierz 5×60, a wynik końcowy to macierz 10×60. Wielokąt foremny w tym przykładzie to 4-kąt, czyli kwadrat:

Iloczyn macierzy AB to macierz 10x5, a BC to macierz 30x60. Dwie możliwe triangulacje w tym przykładzie to:

• 

  Wielokątna reprezentacja (AB)C

• 

  Reprezentacja wielokąta A(BC)

Koszt pojedynczego trójkąta pod względem liczby potrzebnych mnożeń jest iloczynem jego wierzchołków. Całkowity koszt określonej triangulacji wielokąta jest sumą kosztów wszystkich jego trójkątów:

( AB ) C : (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 mnożenia

A ( BC ): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 mnożenia

Hu & Shing opracowali algorytm, który znajduje optymalne rozwiązanie problemu podziału o minimalnym koszcie w czasie O ( n  log  n ).

Algorytm przybliżający Chin-Hu-Shing

We wstępie do algorytmu aproksymacyjnego przedstawiono algorytm aproksymacyjny Chin-Hu-Shinga. Chociaż algorytm ten daje przybliżenie optymalnej triangulacji, warto go wyjaśnić, ponieważ ułatwia zrozumienie technik wykorzystywanych przez Hu-Shinga w swojej pracy.

Do każdego wierzchołka V wielokąta przypisana jest waga w . Załóżmy, że mamy trzy kolejne wierzchołki i jest to wierzchołek o minimalnej wadze . Patrzymy na czworokąt z wierzchołkami (w kolejności zgodnej z ruchem wskazówek zegara). Możemy to triangulować na dwa sposoby: ${\ Displaystyle V_ {i-1}, V_ {i}, V_ {i + 1}}$${\displaystyle V_{\min}}$${\displaystyle w_{\min}}$${\ Displaystyle V_ {\ min}, V_ {i-1}, V_ {i}, V_ {i + 1}}$

• ${\ Displaystyle (V_ {\ min}, V_ {i-1}, V_ {i})}$i , z kosztami${\ Displaystyle (V_ {\ min}, V_ {i + 1}, V_ {i})}$${\displaystyle w_{\min}w_{i-1}w_{i}+w_{\min}w_{i+1}w_{i}}$
• ${\ Displaystyle (V_ {\ min}, V_ {i-1}, V_ {i + 1})}$i kosztem .${\ Displaystyle (V_ {i-1}, V_ {i}, V_ {i + 1})}$${\displaystyle w_{\min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}$

Dlatego, jeśli

${\ Displaystyle w_ {\ min} w_ {i-1} w_ {i+1} + w_ {i-1} w_ {i} w_ {i+1} <w_ {\ min} w_ {i-1} w_ {i}+w_{\min }w_{i+1}w_{i}}$

lub równoważnie

${\displaystyle {\frac{1}{w_{i}}}+{\frac{1}{w_{\min}}}<{\frac{1}{w_{i+1}}}+{\ frak {1}{w_{i-1}}}}$

usuwamy wierzchołek z wielokąta i dodajemy bok do triangulacji. Powtarzamy ten proces, dopóki nie spełni powyższego warunku. Dla wszystkich pozostałych wierzchołków dodajemy bok do triangulacji. Daje nam to prawie optymalną triangulację. ${\ Displaystyle V_ {i}}$${\ Displaystyle (V_ {i-1}, V_ {i+1})}$${\ Displaystyle V_ {i}}$${\ Displaystyle V_ {n}}$${\ Displaystyle (V_ {\ min}, V_ {n})}$

Uogólnienia

Problem mnożenia łańcucha macierzy uogólnia rozwiązanie bardziej abstrakcyjnego problemu: przy danej liniowej sekwencji obiektów, operacji binarnej asocjacyjnej na tych obiektach i sposobie obliczenia kosztu wykonania tej operacji na dowolnych dwóch danych obiektach (jak również wszystkich częściowych wyniki), obliczyć minimalny koszt sposobu grupowania obiektów w celu zastosowania operacji na sekwencji. Jednym nieco wymyślonym specjalnym przypadkiem tego jest konkatenacja łańcuchów listy łańcuchów. Na przykład w C , koszt połączenia dwóch ciągów o długości m i n za pomocą strcat wynosi O( m  +  n ), ponieważ potrzebujemy O( m ) czasu, aby znaleźć koniec pierwszego ciągu i O( n ) czasu, aby skopiuj drugi ciąg na jego koniec. Korzystając z tej funkcji kosztu, możemy napisać algorytm programowania dynamicznego, aby znaleźć najszybszy sposób łączenia sekwencji ciągów. Jednak ta optymalizacja jest raczej bezużyteczna, ponieważ możemy w prosty sposób łączyć łańcuchy w czasie proporcjonalnym do sumy ich długości. Podobny problem występuje w przypadku list połączonych pojedynczo .

Innym uogólnieniem jest rozwiązanie problemu, gdy dostępne są procesory równoległe. W tym przypadku zamiast dodawać koszty obliczania każdego czynnika iloczynu macierzowego, bierzemy maksimum, ponieważ możemy je wykonać jednocześnie. Może to drastycznie wpłynąć zarówno na minimalny koszt, jak i na ostateczne optymalne grupowanie; preferowane są bardziej „zrównoważone” grupy, które zajmują wszystkie procesory. Istnieją jeszcze bardziej wyrafinowane podejścia.

Zobacz też

• Associahedron
• Krata Tamari

Bibliografia