dynamic-programming
Matrixkettenmultiplikation

Rekursive Lösung

Matrixkettenmultiplikation ist ein Optimierungsproblem, das durch dynamische Programmierung gelöst werden kann. Mit einer Folge von Matrizen ist es das Ziel, den effizientesten Weg zu finden, diese Matrizen zu multiplizieren. Das Problem besteht nicht darin, die Multiplikationen tatsächlich durchzuführen, sondern lediglich die Reihenfolge der beteiligten Matrixmultiplikationen zu bestimmen.

Nehmen wir an, wir haben zwei Matrizen A ₁ und A ₂ der Dimension m * n und p * q . Aus den Regeln der Matrixmultiplikation wissen wir, dass

1. Wir können A ₁ und A ₂ nur dann multiplizieren, wenn n = p . Das heißt, die Anzahl der Spalten von A ₁ muss der Anzahl der Zeilen von A _{2 entsprechen} .
2. Wenn die erste Bedingung erfüllt ist und wir A ₁ und A ₂ multiplizieren, erhalten wir eine neue Matrix, nennen wir sie A ₃ der Dimension m * q .
3. Um A ₁ und A ₂ zu multiplizieren, müssen wir einige Skalierer-Multiplikationen durchführen. Die Gesamtzahl der Skalierer-Multiplikationen, die wir durchführen müssen, ist ( m * n * q ) oder ( m * p * q ).
4. A ₁ * A ₂ ist nicht gleich A ₂ * A ₁ .

Wenn wir drei Matrizen A ₁ , A ₂ und A ₃ mit der Dimension m * n , n * p und p * q haben, dann hat A ₄ = A ₁ * A ₂ * A ₃ die Dimension m * q . Jetzt können wir diese Matrixmultiplikation auf zwei Arten durchführen:

• Zuerst multiplizieren wir A ₁ und A ₂ , dann multiplizieren wir A ₃ mit dem Ergebnis. Das heißt: ( A ₁ * A ₂ ) * A ₃ .
• Zuerst multiplizieren wir A ₂ und A ₃ , dann multiplizieren wir A ₁ mit dem Ergebnis. Das heißt: A ₁ * ( A ₂ * A ₃ ).

Sie können feststellen, dass die Reihenfolge der Multiplikation gleich bleibt, dh ( A ₁ * A ₃ ) * A _{2 wird} nicht multipliziert, da sie möglicherweise nicht gültig ist. Wir ändern nur die Klammern , um einen Satz zu multiplizieren, bevor er mit dem Rest multipliziert wird. Wie wir diese Klammern platzieren, ist wichtig. Warum? Nehmen wir an, die Dimension der 3 Matrizen A ₁ , A ₂ und A ₃ beträgt 10 * 100 , 100 * 5 , 5 * 50 . Dann,

1. Für ( A ₁ * A ₂ ) * A ₃ ist die Gesamtzahl der Skalierer-Multiplikationen: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 mal.
2. Für A ₁ * ( A ₂ * A ₃ ) beträgt die Gesamtzahl der Skalierer-Multiplikationen: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 mal.

Für die zweite Art der Anzahl der Scaler Multiplikation ist 10 - mal die Anzahl der ersten Art! Wenn Sie also einen Weg finden können, um die korrekte Ausrichtung der Klammern herauszufinden, die zur Minimierung der Gesamt-Skalierer-Multiplikation erforderlich ist, würde dies sowohl den Zeit- als auch den Speicherplatz für die Matrix-Multiplikation reduzieren. Hier bietet sich die Matrixkettenmultiplikation an. Hier werden wir uns nicht mit der tatsächlichen Multiplikation von Matrizen beschäftigen, wir werden nur die korrekte Klammerreihenfolge herausfinden, so dass die Anzahl der Skalierervervielfachungen minimiert wird. Wir haben die Matrizen A ₁ , A ₂ , A ₃ ........ A _n und wir ermitteln die minimale Anzahl von Scaler-Multiplikationen, die erforderlich sind, um diese zu multiplizieren. Wir gehen davon aus, dass die angegebenen Dimensionen gültig sind, dh sie erfüllen unsere erste Anforderung an die Matrixmultiplikation.

Wir werden die Divide-and-Conquer-Methode verwenden, um dieses Problem zu lösen. Dynamische Programmierung ist wegen häufiger Teilprobleme erforderlich. Zum Beispiel: für n = 5 haben wir 5 Matrizen A ₁ , A ₂ , A ₃ , A ₄ und A ₅ . Wir möchten herausfinden, wie viele Multiplikationen mindestens erforderlich sind, um diese Matrixmultiplikation A ₁ * A ₂ * A ₃ * A ₄ * A ₅ durchzuführen. Konzentrieren wir uns auf eine der vielen Möglichkeiten: ( A ₁ * A ₂ ) * ( A ₃ * A ₄ * A ₅ ).

Für diesen finden wir A _left = A ₁ * A ₂ . A _rechts = A ₃ * A ₄ * A ₅ . Dann erfahren wir eine _Antwort = A _left * A _right . Die Gesamtzahl der zur Ermittlung von Skalierern erforderlichen Skalierern A _Antwort : = Die Gesamtzahl der zur Bestimmung von A _left erforderlichen Skaliermultiplikationen + Die Gesamtzahl der zur Bestimmung von A _right erforderlichen Skaliermultiplikationen + Die Gesamtzahl der zur Bestimmung von A _left benötigten Skaliervervielfachungen * Ein _recht

Der letzte Ausdruck, Die Gesamtzahl der Skalierer-Multiplikationen, die erforderlich sind, um A _left * A _right zu bestimmen: Die Anzahl der Zeilen in A _left * die Anzahl der Spalten in A _left * die Anzahl der Spalten in A _right . (Nach der zweiten Regel der Matrixmultiplikation)

Aber wir könnten die Klammern auch auf andere Weise setzen. Zum Beispiel:

• A ₁ * ( A ₂ * A ₃ * A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ ) * ( A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ * A ₄ ) * A ₅ usw.

Für jeden möglichen Fall bestimmen wir die Anzahl der Scaler-Multiplikationen, die erforderlich sind, um A _left und A _right herauszufinden, dann für A _left * A _right . Wenn Sie eine allgemeine Vorstellung von Rekursion haben, haben Sie bereits verstanden, wie Sie diese Aufgabe ausführen. Unser Algorithmus wird sein:

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

Warum ist das ein dynamisches Programmierproblem? Wenn Sie ( A ₁ * A ₂ * A ₃ ) bereits berechnet haben ( A ₁ * A ₂ ), ist dies in diesem Fall hilfreich.

Um den Status dieser Rekursion zu bestimmen, können wir sehen, dass wir für jeden Fall die Bandbreite der Matrizen kennen müssen, mit denen wir arbeiten. Also brauchen wir einen Anfang und ein Ende . Bei der Verwendung von "Teilen" und "Erobern" werden in unserem Basisfall weniger als 2 Matrizen ( Anfang > = Ende ) vorhanden sein, bei denen wir uns gar nicht vermehren müssen. Wir haben 2 Arrays: Zeile und Spalte . Zeile [i] und Spalte [i] speichern die Anzahl der Zeilen und Spalten für Matrix A _i . Wir haben ein dp [n] [n] -Array, um die bereits berechneten Werte zu speichern und mit -1 zu initialisieren, wobei -1 für den noch nicht berechneten Wert steht. dp [i] [j] steht für die Anzahl der Skalierer-Multiplikationen, die zum Multiplizieren von A _i , A _{i + 1} , ..., A _j einschließlich erforderlich sind. Der Pseudo-Code sieht folgendermaßen aus:

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

Komplexität:

Der Wert für Anfang und Ende kann zwischen 1 und n liegen . Es gibt n ² verschiedene Zustände. Für jeden Zustand wird die Schleife n mal ausgeführt. Gesamtzeitkomplexität: O(n³) und Speicherkomplexität: O(n²) .