Matrix Kette Multiplikation ist ein Optimierungsproblem, das mit Hilfe der dynamischen Programmierung gelöst werden können. Bei einer Sequenz von Matrizen ist es das Ziel, den effizientesten Weg, diese Matrizen multiplizieren finden. Das Problem ist nicht tatsächlich auf die Multiplikationen, sondern lediglich um die Sequenz von Matrixmultiplikationen beteiligt zu entscheiden.

Wir haben viele Möglichkeiten, weil Matrix-Multiplikation ist assoziativ. Mit anderen Worten, unabhängig davon, wie wir das Produkt klammern, das erhaltene Ergebnis werden die gleichen bleiben. Zum Beispiel, wenn wir vier Matrizen A, B, C und D, müssten wir:

Die Reihenfolge, in der die Ware klammern beeinträchtigt jedoch die Anzahl der einfache arithmetische Operationen erforderlich, um das Produkt oder den Wirkungsgrad zu berechnen. Angenommen, A ist eine 10 × 30-Matrix ist, B ein 30 × 5-Matrix ist und C ein 5 × 60 Matrix. Dann,

Eindeutig die erste Methode ist effizienter. Mit diesen Informationen kann die Problemstellung verfeinert werden, wie bestimmen wir die optimale Klammerung eines Produkts von n Matrizen? Wir konnten durch jede mögliche Klammerung zu gehen, einen Laufzeit, die exponentiell in der Anzahl von Matrizen, die sehr langsam und unpraktisch für große n ist erfordert. Eine schnellere Lösung für dieses Problem kann durch Aufbrechen, das Problem in eine Reihe von verwandten Teilprobleme erreicht werden. Durch Lösen Teilprobleme ein Mal und die Wiederverwendung dieser Lösungen können wir drastisch die zur Laufzeit zu reduzieren. Dieses Konzept ist als dynamische Programmierung bekannt.

A dynamischen Programmieralgorithmus

Um zu beginnen, lassen Sie uns davon ausgehen, dass alles, was wir wirklich wissen wollen, ist die Mindestkosten oder minimale Anzahl von Rechenoperationen, benötigt, um zu multiplizieren sich die Matrizen. Wenn wir nur zwei Matrizen multipliziert werden, gibt es nur einen Weg, um sie zu multiplizieren, so dass die minimalen Kosten sind die Kosten, dies zu tun. In der Regel können wir die minimalen Kosten zu finden, mit dem folgenden rekursiven Algorithmus:

• Nehmen Sie die Reihenfolge der Matrizen und trennen sie in zwei Untersequenzen.
• Hier finden Sie die minimalen Kosten der Multiplizieren Sie jede Teilfolge.
• Fügen Sie diese Kosten zusammen, und fügen Sie in die Kosten für die Multiplikation der beiden Ergebnis Matrizen.
• Dies für jede mögliche Position, bei der die Sequenz der Matrizen aufgeteilt werden kann, und nehmen die Minimum über alle von ihnen.

Zum Beispiel, wenn wir vier Matrizen ABCD, berechnen wir die erforderlich ist, um jede der Kosten zu finden ,, und, was rekursive Aufrufe, um die minimalen Kosten für ABC, AB, CD und BCD berechnen zu finden. Wir wählen dann die beste. Besser noch, ergibt sich nicht nur die minimalen Kosten, sondern zeigt auch die beste Art, dies zu tun die Vermehrung: Gruppe ist die Art und Weise, die die niedrigsten Gesamtbetriebskosten ergibt, und das Gleiche tun für jeden Faktor.

Leider, wenn wir setzen diesen Algorithmus, entdecken wir, dass es nur so langsam wie der naive Art und Weise zu versuchen, alle Permutationen ist! Was schief gelaufen ist? Die Antwort ist, dass wir dabei eine Menge Doppelarbeit. Zum Beispiel oben haben wir einen rekursiven Aufruf, um den besten Preis für die Berechnung sowohl ABC und AB zu finden. Doch die Suche nach das beste Kosten zur Berechnung ABC erfordert auch das Finden der besten Kosten für AB. Als die Rekursion tiefer wächst mehr und mehr von dieser Art von unnötigen Wiederholung auftritt.

Eine einfache Lösung heißt memoization: jedes Mal, berechnen wir die minimalen Kosten benötigt, um zu multiplizieren eine spezifische Teilfolge, die wir sie zu speichern. Wenn wir jemals gefragt, um es wieder zu berechnen, geben wir einfach die gespeicherte Antwort, und nicht neu zu berechnen ist. Da es etwa n / 2 verschiedenen Untersequenzen, wobei n die Anzahl der Matrizen der Raumbedarf zu tun ist vernünftig. Es kann gezeigt werden, dass diese einfachen Trick bringt die Laufzeit bis zu O von O, die mehr als effizient genug für echte Anwendungen. Dies ist von oben nach unten die dynamische Programmierung.

Von Pseudocode:

• Hinweis: Der erste Index p 0 ist und der erste Index für m ist und s 1

Eine andere Lösung ist, um zu antizipieren, welche Kosten werden wir brauchen, und sie vorab berechnen. Das geht so:

• Für jedes k von 2 bis n ist die Anzahl der Matrizen:
  • Berechnen Sie die minimale Kosten jedes Teilfolge der Länge k, mit den bereits berechneten Kosten.

Der Code in Java unter Verwendung von Null-basierten Array-Indizes sowie eine bequeme Methode für das Drucken der gelöst Reihenfolge der Operationen:

Am Ende dieses Programms haben wir die minimalen Kosten für die vollständige Sequenz. Obwohl dieser Algorithmus erfordert O Zeit hat dieser Ansatz praktische Vorteile, dass es keine Rekursion, keine Prüfung, ob ein Wert bereits berechnet erfordert, und wir können Raum durch Wegwerfen einige der subresults, die nicht mehr benötigt werden, zu speichern. Dies ist von unten nach oben dynamischen Programmierung: einen zweiten Weg, auf dem dieses Problem gelöst werden kann.

Noch effizienter Algorithmus

Ein Algorithmus im Jahr 1984 von Hu und Shing veröffentlicht erreicht O Komplexität. Sie zeigten, wie die Matrixmultiplikation Kette Problem kann in das Problem der Polygon Triangulation transformiert werden. Dieses Bild zeigt die möglichen Triangulierungen eines Sechsecks:

Zweitens, einen Algorithmus, eine optimale Lösung für das Problem in der Partition O Zeit findet entwickelten sie.

Mit n + 1 Matrizen in der Multiplikationskette gibt es n binäre Operationen und Cn Möglichkeiten der Platzierung parenthesizes, wobei Cn der n-te katalanischen Nummer.

Verallgemeinerungen

Obwohl dieser Algorithmus gilt auch für das Problem der Matrixkette Multiplikation, wurde festgestellt, daß es verallgemeinert auch zur Lösung eine abstraktere Problem: Bei einer linearen Folge von Objekten, eine assoziative Binäroperation für diese Objekte, und ein Weg, um die Kosten zu berechnen, der Durchführung dieser Operation an zwei bestimmten Objekten, berechnen die Mindest kostengünstige Möglichkeit, gruppieren Sie die Objekte, um den Betrieb über die Sequenz anzuwenden.

Ein gemeinsames Sonderfall ist die String-Verkettung. Sagen wir, wir haben eine Liste von Zeichenketten. In C, zum Beispiel die Kosten für die Verkettung zweier Zeichenfolgen der Länge m und n mit strcat O, da wir O Zeit, um das Ende der ersten Schnur und O-Zeit, um die zweite Zeichenkette an das Ende davon zu kopieren finden. Mit dieser Kostenfunktion, können wir einen dynamischen Programmieralgorithmus zu schreiben, um die schnellste Weg, um eine Folge von Strings verketten finden. Ein ähnliches Problem existiert für einfach verketteten Listen.

Eine weitere Verallgemeinerung besteht darin, das Problem zu lösen, wenn zwei parallele Prozessoren zur Verfügung stehen. In diesem Fall wird anstelle der Zugabe der Kosten für die Berechnung jeder Teilfolge, wir nehmen Sie nur die maximale, denn wir können sie beide gleichzeitig zu tun. Dies kann drastische Auswirkungen auf sowohl die minimalen Kosten und die endgültige optimale Gruppierung; mehr "ausgewogene" Gruppierungen, die alle Prozessoren beschäftigt sind begünstigt. Heejo Lee et al. beschreiben, noch ausgefeiltere Ansätze.

Implementierungen

• Ein JavaScript-Implementierung ist an Alex Le Blog
• Ein JavaScript-Implementierung ist an ateji PX
• Ein JavaScript-Implementierung, die endgültige m und s Tabellen und Zwischenberechnungen von Michail Simin
• Eine Java-Implementierung ist Brians Projekt Galerie verfügbar
• Ein MATLAB Implementierung von MATLAB Central