Matrix Chain Multiplication

Q: Wie hoch ist die Zeitkomplexität der Matrixkettenmultiplikation?

Die Tabelle hat etwa n²/2 Teilbereiche, und für jeden werden bis zu n Teilungen ausprobiert. Daher benötigt die dynamische Programmierung O(n³) Zeit und O(n²) Speicher. Eine einfache Rekursion ohne Memoisierung führt bei n Matrizen zu 3^(n-1) Aufrufen.

Q: Warum ist die Reihenfolge der Matrixmultiplikation wichtig?

Die Matrixmultiplikation ist assoziativ, daher ergeben (AB)C und A(BC) dieselbe Matrix, aber die Zwischenmatrizen unterscheiden sich in ihrer Größe. Im ersten Beispiel erstellt (AB)C eine 4 × 3-Matrix und kostet 264, während A(BC) eine 10 × 12-Matrix erstellt und 840 kostet.

Q: Wie findet man die optimale Klammerung selbst?

Speichere die gewinnende Aufteilung neben best[left][right] in choice[left][right] . Zum Ausgeben wird bei einer einzelnen Matrix ihr Name ausgegeben; ein längerer Abschnitt gibt eine öffnende Klammer, den Teil bis choice[left][right] , den Teil danach und eine schließende Klammer aus. Das benötigt O(n²) Speicher.

SchwerDynamische Programmierung

+10

Eine Matrixkette wird durch dims beschrieben: Matrix i hat dims[i] Zeilen und dims[i+1] Spalten, sodass jede Matrix zur nächsten passt. Die Multiplikation einer p × q-Matrix mit einer q × r-Matrix benötigt p × q × r skalare Multiplikationen und ergibt eine p × r-Matrix. Jede Klammerung ergibt dasselbe Endprodukt, aber nicht mit denselben Kosten. Gib die geringstmögliche Anzahl skalarer Multiplikationen zurück, die zum Multiplizieren der gesamten Kette benötigt wird.

Funktion

matrixChainOrder(dims: integer-array) → integer

dimsinteger-array: Die Größen entlang der Kette: Matrix i hat die Dimensionen dims[i] × dims[i+1]
Gibt zurückinteger: die geringstmögliche Anzahl an Skalarmultiplikationen, um die gesamte Kette zu multiplizieren

Einschränkungen

2 ≤ dims.length ≤ 100, somit umfasst die Kette zwischen 1 und 99 Matrizen.
1 ≤ dims[i] ≤ 100
Die Antwort beträgt höchstens 98 × 10⁶ und liegt damit deutlich innerhalb des Bereichs einer vorzeichenbehafteten 32-Bit-Ganzzahl.

Beispiele

Eingabe: dims = [4, 10, 3, 12]
Ausgabe: 264
Erklärung: Die Multiplikation der ersten beiden kostet 4 × 10 × 3 = 120 und ergibt eine 4 × 3-Matrix. Die Multiplikation mit der 3 × 12-Matrix kostet zusätzlich 144: insgesamt 264. Die andere Reihenfolge kostet 360 + 480 = 840.

Weiterführende Frage

Kannst du auch zählen, wie viele verschiedene Klammerungen die minimalen Kosten erreichen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Reihenfolge verändert die Kosten: 264 gegenüber 840 im ersten Beispiel. Sieh dir die letzte Multiplikation an. Sie verbindet die Produkte eines linken und eines rechten Teils der Kette, und jeder Teil ist dasselbe Problem für eine kürzere Kette. Eine Tabelle über die Abschnitte der Kette löst jedes Problem einmal, in O(n³) Zeit.

Probiere jede Aufteilung mit einfacher Rekursion aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Nummeriere die Grenzen der Kette von 0 bis m-1, wobei m = dims.length gilt: Grenze k hat die Größe dims[k]. Die Matrizen zwischen den Grenzen left und right ergeben bei Multiplikation in beliebiger Reihenfolge eine Matrix der Größe dims[left] × dims[right]. Wenn also der letzte Schritt diesen Abschnitt bei split aufteilt, kostet er dims[left] × dims[split] × dims[right], unabhängig davon, was innerhalb der beiden Blöcke passiert ist. Jeder Block sollte so kostengünstig wie möglich aufgebaut werden. Daher ist cheapest(left, right) die kleinste Summe der Kosten beider Blöcke plus dieses letzten Schritts, betrachtet über alle split-Werte. Jeden möglichen letzten Schritt auszuprobieren, macht den Algorithmus korrekt.

Der Algorithmus löst immer wieder dieselben Abschnitte: Bei n Matrizen gibt es 3^(n-1) Aufrufe, also etwa 1.2 × 10^9 bei 20 Matrizen, obwohl es nur etwa m²/2 verschiedene Abschnitte gibt.

Algorithmus

Schreibe cheapest(left, right) für die Matrizen zwischen den Grenzen left und right.
Wenn right - left < 2, gibt es eine Matrix: Gib 0 zurück.
Addiere für jedes split strikt zwischen ihnen cheapest(left, split), cheapest(split, right) und dims[left] × dims[split] × dims[right].
Gib die kleinste Summe zurück.
Die Antwort ist cheapest(0, m-1).

def matrixChainOrder(dims):
    def cheapest(left, right):
        # The fewest multiplications for the matrices between boundaries left and right
        if right - left < 2:
            return 0  # a single matrix costs nothing
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        return best

    return cheapest(0, len(dims) - 1)

Rekursion mit Memoisierung

Idee

Ein Aufruf hängt nur von left und right ab. Speichere sein Ergebnis in memo[left][right], wobei jede Zelle mit -1 beginnt, einem Wert, den keine tatsächlichen Kosten annehmen können, und spätere Aufrufe lesen die Zelle aus, statt erneut rekursiv aufzurufen. Jedes der etwa m²/2 Paare wird einmal mit weniger als m Teilungen gelöst: O(n³) oder 161.700 Teilungsprüfungen für 99 Matrizen. Die Rekursion ist nie tiefer, als die Kette lang ist, daher passen 100 Grenzen auf jeden Aufrufstapel.

Algorithmus

Initialisiere memo mit m Zeilen und m Spalten, wobei jede Zelle -1 enthält.
In cheapest(left, right) ergibt ein Abschnitt mit einer Matrix den Wert 0, und eine Zelle, die nicht -1 ist, gibt ihre gespeicherten Kosten zurück.
Berechne andernfalls jeden split genau wie bei der einfachen Rekursion und nimm das Minimum.
Schreibe dieses Minimum vor der Rückgabe in memo[left][right].
Das Ergebnis ist cheapest(0, m-1).

def matrixChainOrder(dims):
    m = len(dims)
    # memo[left][right]: the answer for boundaries left and right, -1 while unknown
    memo = [[-1] * m for _ in range(m)]

    def cheapest(left, right):
        if right - left < 2:
            return 0  # a single matrix costs nothing
        if memo[left][right] != -1:
            return memo[left][right]
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        memo[left][right] = best
        return best

    return cheapest(0, m - 1)

Fülle die Tabelle durch Ziehen auf die gewünschte Breite aus

Idee

Jede Zelle hängt nur von kleineren Teilbereichen ab, daher können Schleifen best[left][right] von schmal nach breit ausfüllen. Bei Breite 1 handelt es sich um eine einzelne Matrix, und der Wert bleibt 0; wenn ein breiterer Teilbereich erreicht wird, sind beide Teile jeder Aufteilung bereits berechnet. Mit dims = [6, 2, 7, 3, 5]:

Breite 2: best[0][2] = 84, best[1][3] = 42, best[2][4] = 105.
Breite 3: best[0][3] ist 78 (Aufteilung 1: 0 + 42 + 36), best[1][4] ist 72 (Aufteilung 3: 42 + 0 + 30).
Breite 4: Die Aufteilungen 1, 2 und 3 ergeben 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 und 78 + 0 + 90 = 168, also best[0][4] = 132.

Die oberste Aufteilung an Grenze 1 bedeutet, dass die Matrix 6 × 2 zuletzt verbunden wird, wie im zweiten Beispiel. Laufzeit und Speicherbedarf entsprechen der Memo-Version, jedoch ohne Rekursion.

Algorithmus

Setze m = dims.length und lege eine m × m-Tabelle best mit Nullen an.
Durchlaufe width von 2 bis m-1. Durchlaufe darin left aufsteigend ab 0, solange right = left + width noch eine Grenze ist.
Berechne für diesen Abschnitt für jedes split von left+1 bis right-1 den Wert best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right] und speichere das Minimum in best[left][right].
Die Antwort steht in best[0][m-1].

def matrixChainOrder(dims):
    m = len(dims)
    # best[left][right]: the fewest multiplications for the matrices
    # between boundary left and boundary right (0 for a single matrix)
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            low = None
            for split in range(left + 1, right):
                # the last product joins a dims[left] x dims[split] block
                # with a dims[split] x dims[right] block
                cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
                if low is None or cost < low:
                    low = cost
            best[left][right] = low
    return best[0][m - 1]

Stolperfallen und Grenzfälle

Zuerst das günstigste Paar multiplizieren. Bei [10, 10, 1, 9] ist das letzte Paar am günstigsten (90), aber der anschließende Schritt kostet 900, also insgesamt 990. Multipliziert man zuerst das erste Paar, kostet es 190.
Das Ergebnis aus der falschen Zelle ablesen. dims hat einen Eintrag mehr als es Matrizen gibt, daher lautet das Ergebnis best[0][m-1] und nicht best[0][m].
In der äußeren Schleife left aufsteigend durchlaufen. Die Zeile left liest dann best[split][right] aus einer späteren Zeile, die noch den Wert 0 hat. Verwende die Breite in der äußeren Schleife oder zähle left abwärts.
Die einzelne Matrix übersehen. [3, 7] muss 0 zurückgeben, und in R wird die Schleife 2:(m-1) zu 2:1 und läuft rückwärts, also musst du sie absichern.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Matrixkettenmultiplikation?

Die Tabelle hat etwa n²/2 Teilbereiche, und für jeden werden bis zu n Teilungen ausprobiert. Daher benötigt die dynamische Programmierung O(n³) Zeit und O(n²) Speicher. Eine einfache Rekursion ohne Memoisierung führt bei n Matrizen zu 3^(n-1) Aufrufen.

Warum ist die Reihenfolge der Matrixmultiplikation wichtig?

Die Matrixmultiplikation ist assoziativ, daher ergeben (AB)C und A(BC) dieselbe Matrix, aber die Zwischenmatrizen unterscheiden sich in ihrer Größe. Im ersten Beispiel erstellt (AB)C eine 4 × 3-Matrix und kostet 264, während A(BC) eine 10 × 12-Matrix erstellt und 840 kostet.

Wie findet man die optimale Klammerung selbst?

Speichere die gewinnende Aufteilung neben best[left][right] in choice[left][right]. Zum Ausgeben wird bei einer einzelnen Matrix ihr Name ausgegeben; ein längerer Abschnitt gibt eine öffnende Klammer, den Teil bis choice[left][right], den Teil danach und eine schließende Klammer aus. Das benötigt O(n²) Speicher.

def matrixChainOrder(dims):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

dims = [4, 10, 3, 12]

Erwartete Ausgabe

Matrix Chain Multiplication

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Aufteilung mit einfacher Rekursion aus

Rekursion mit Memoisierung

Fülle die Tabelle durch Ziehen auf die gewünschte Breite aus

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben