Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


42. Dynamische Programmierung



Das Produkt mehrerer Matrizen

Ein klassischer Anwendungsfall der dynamischen Programmierung ist das Problem der Minimierung des Rechenaufwands, der für die Multiplikation einer Reihe von Matrizen unterschiedlicher Dimension erforderlich ist. Derartige Verfahren müssen bei allen Anwendungen berücksichtigt werden, bei denen viele Matrizenoperationen auftreten.

Nehmen wir an, daß die sechs Matrizen

Formel

miteinander multipliziert werden sollen. Natürlich muß die Anzahl der Spalten in einer Matrix stets mit der Anzahl der Zeilen in der folgenden Matrix übereinstimmen, damit die Multiplikationen ausführbar sind. Doch die Gesamtzahl der erforderlichen Skalar-Multiplikationen hängt von der Reihenfolge ab, in der die Matrizen multipliziert werden. Zum Beispiel könnten wir von links nach rechts vorgehen: Wenn wir A mit B multiplizieren, erhalten wir nach 24 Skalar-Multiplikationen eine Matrix der Dimension 4 x 3. Die Multiplikation dieses Ergebnisses mit C liefert nach weiteren 12 Skalar-Multiplikationen eine Matrix der Dimension 4 x 1. Die Multiplikation dieses Ergebnisses mit D ergibt nach 8 weiteren Skalar-Multiplikationen eine Matrix der Dimension 4 x 2. Wenn wir in dieser Weise fortfahren, erhalten wir nach insgesamt 84 Skalar-Multiplikationen als Ergebnis eine Matrix der Dimension 4 x 3. Wenn wir jedoch stattdessen von rechts nach links vorgehen, erhalten wir als Ergebnis die gleiche Matrix der Dimension 4 x 3 nach nur 69 Skalar-Multiplikationen.

Natürlich sind noch viele andere Reihenfolgen möglich. Die Reihenfolge der Multiplikation kann durch Setzen von Klammern ausgedrückt werden; zum Beispiel entspricht die Reihenfolge von links nach rechts dem Ausdruck (((((A*B*)C)*D)*E)E*F) und die Reihenfolge von rechts nach links dem Ausdruck (A*(B*(C*(D*(E*F))))). Jedes zulässige Setzen von Klammern führt zum richtigen Ergebnis, doch wann ist die Anzahl der Skalar-Multiplikationen am kleinsten?

Wenn große Matrizen auftreten, können beträchtliche Einsparungen erzielt werden: Wenn zum Beispiel die Matrizen B, C und F im obigen Beispiel jeweils eine Dimension 300 anstelle von 3 besitzen, sind bei der Reihenfolge von links nach rechts 6024 Skalar-Multiplikationen erforderlich, bei der Reihenfolge von rechts nach links dagegen ist die astronomische Zahl von 274.200 Multiplikationen auszuführen. (Bei diesen Berechnungen setzen wir voraus, daß das Standardverfahren zur Multiplikation von Matrizen zur Anwendung kommt. Mit dem Verfahren von Strassen oder einer ähnlichen Methode könnte im Prinzip bei großen Matrizen der Aufwand verringert werden, doch hinsichtlich der Reihenfolge der Multiplikationen gelten die gleichen Überlegungen. Demnach ergibt die Multiplikation einer Matrix der Dimension p x q mit einer Matrix der Dimension q x r eine Matrix der Dimension p x r, wobei jedes Element mit Hilfe von q Multiplikationen berechnet wird, so daß insgesamt pqr Multiplikationen ausgeführt werden müssen.)

Nehmen wir für den allgemeinen Fall an, daß N Matrizen miteinander zu multiplizieren sind:

M1M2M3 ... MN,

wobei die Matrizen der Bedingung genügen, daß Mi für 1 <= i <= N ri Zeilen und ri+1 Spalten aufweist. Unsere Aufgabe besteht darin, diejenige Reihenfolge der Multiplikation der Matrizen zu finden, für die die Gesamtzahl der auszuführenden Skalar-Multiplikationen minimal wird. Sicher ist das Ausprobieren aller möglichen Reihenfolgen unpraktisch. (Die Anzahl der Reihenfolgen ist eine gründlich erforschte kombinatorische Funktion, die Katalanische Zahl genannt wird; die Anzahl der Möglichkeiten, N Variablen zu klammern, beträgt ungefähr 4N-1/N Formel.) Doch sicher lohnt es sich, einigen Aufwand zu treiben, um eine gute Lösung zu finden, da N im allgemeinen im Vergleich zur Anzahl der auszuführenden Multiplikationen sehr klein ist.

Wie oben besteht die Lösung dieses Problems mit Hilfe der dynamischen Programmierung darin, »von unten nach oben« vorzugehen und berechnete Lösungen kleiner Teilprobleme zu speichern, um eine wiederholte Berechnung zu vermeiden. Zunächst gibt es jeweils nur eine Möglichkeit, M1 mit M2 zu multiplizieren, M2 mit M3, ..., MN-1 mit MN; wir speichern diese Kosten. Danach berechnen wir unter Ausnutzung aller bisher berechneten Informationen die beste Möglichkeit, um aufeinanderfolgende Tripel zu multiplizieren, unter Ausnutzung aller bisher berechneten Informationen. Um zum Beispiel die beste Möglichkeit zu ermitteln, M1M2M3 zu multiplizieren, entnehmen wir zuerst der gespeicherten Tabelle die Kosten der Berechnung von M1M2 und addieren dann die Kosten der Multiplikation dieses Ergebnisses mit M3 dazu. Diese Summe wird mit den Kosten verglichen, die entstehen, wenn zuerst die Multiplikation M2M3 ausgeführt und dann mit M1 multipliziert wird, was auf gleiche Weise berechnet werden kann. Die kleinere dieser Summen wird gespeichert, und ebenso wird mit allen anderen Tripeln verfahren. Anschließend berechnen wir unter Benutzung aller bisher erhaltenen Informationen die beste Möglichkeit, Quadrupel Matrizen zu multiplizieren. Indem wir in dieser Weise fortfahren, finden wir schließlich die beste Möglichkeit, alle Matrizen miteinander zu multiplizieren.

Dies führt zu dem folgenden Programm:

    for i:=1 to N do
      for j:=i+1 to N do cost[i,j]:=maxint;
    for i:=1 to N do cost[i,i]:=0;
    for j:=1 to N-1 do
      for i:=1 to N-j do
        for k:=i+1 to i+j do
          begin
          t:=cost[i,k-1]+cost[k,i+j]+r[i]*r[k]*r[i+j+1];
          if t<cost[i,i+j] then
            begin cost[i,i+j]:=t; best[i,i+j]:=k end;
          end;

Für 1 <= j <= N - 1 ermitteln wir die minimalen Kosten der Berechnung von

MiMi+1...Mi+j,

indem wir für 1 <= i <= N - j und für jedes k zwischen i und i + j die Kosten der Berechnung von MiMi+1...Mk-1 und von MkMk+1...Mi+j ermitteln und dann die Kosten addieren, die bei der Multiplikation dieser Ergebnisse entstehen. Da wir stets eine Gruppe in zwei kleinere Gruppen zerlegen, brauchen die minimalen Kosten für die beiden Gruppen nur aus einer Tabelle entnommen und nicht neu berechnet zu werden. Hierbei gibt cost[l,r] die minimalen Kosten der Berechnung von MlMl+1...Mr an; die Kosten für die erste oben angegebene Gruppe betragen cost[i,k-1], die Kosten für die zweite Gruppe cost[k,i+j]. Die Kosten der abschließenden Multiplikation lassen sich leicht bestimmen: MiMi+1...Mk-1 ist eine Matrix der Dimension ri x rk, und MkMk+1...Mi+j ist eine Matrix der Dimension rk x ri+j+1, so daß die Kosten der Multiplikation dieser beiden Matrizen rirkri+j+1 betragen. Auf diese Weise berechnet das Programm cost[i,i+j] für 1 <= i <= N - j, wobei j von 1 bis N - 1 wächst. Wenn wir j = N - 1 erreichen (und i = 1), haben wir die gesuchten minimalen Kosten der Berechnung von M1M2...MN gefunden.

Wie oben müssen wir die getroffenen Entscheidungen in einem getrennten Feld best registrieren, um sie später, wenn die tatsächliche Folge der Multiplikationen erzeugt werden soll, wieder bestimmen zu können. Das folgende Programm stellt die Implementation dieses Prozesses der Ermittlung der optimalen Anordnung der Klammern anhand der mit Hilfe des obigen Programms berechneten Felder cost und best dar:

    procedure order(i,j: integer);
      begin
      if i=j then write(name(i)) else
        begin
        write('(');
        order(i,best[i,j]-1); order(best[i,j],j);
        write(')')
        end
      end;

Die Tabelle in Abbildung 42.3 zeigt den Ablauf dieser Programme für das oben angegebene Beispiel. Sie gibt die Gesamtkosten und die optimale »letzte« Multiplikation für jede Teilfolge in der Liste der Matrizen an. Zum Beispiel besagt die Eintragung in der Zeile A und der Spalte F, daß 36 Skalar-Multiplikationen erforderlich sind, um die Matrizen A bis F miteinander zu multiplizieren, und daß dies erreicht werden kann, indem A bis C auf optimale Weise multipliziert werden, dann D bis F auf optimale Weise multipliziert werden und danach die erhaltenen Matrizen miteinander multipliziert werden. Nur D ist wirklich in dem Feld best enthalten; die vollständigen optimalen Zerlegungen sind der Klarheit wegen im Schema angegeben. Um festzustellen, wie A bis C auf optimale Weise zu multiplizieren sind, suchen wir in Zeile A und Spalte C usw. Für unser Beispiel ist die ermittelte Anordnung der Klammern ((A*(B*C))*((D*E)*F)), wofür wie erwähnt nur 36 Skalar-Multiplikationen benötigt werden. Für das weiter oben betrachtete Beispiel, bei dem die Dimensionen 3 in B, C und F in 300 umgeändert wurden, ist die gleiche Anordnung der Klammern optimal, wobei 2412 Skalar-Multiplikationen erforderlich sind.

Abbildung 42.3
Abbildung 42.3 Lösung des Problems der Multiplikation mehrerer Matrizen.

Eigenschaft 42.2 Mit Hilfe der dynamischen Programmierung kann das Problem der Multiplikation mehrerer Matrizen in einer zu N3 proportionalen Zeit und mit einem zu N2 proportionalen Speicheraufwand gelöst werden.

Auch dies folgt unmittelbar aus der Betrachtung des Programms. Insbesondere ist der Speicheraufwand wesentlich größer als beim Rucksack-Problem. Der Aufwand an Zeit und Speicherplatz für die Bestimmung des Optimums dürften jedoch im Vergleich zu den erzielten Einsparungen praktisch vernachlässigbar sein. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]