Robert Sedgewick: Algorithmen

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


42. Dynamische Programmierung



Optimale binäre Suchbäume

Bei vielen Suchanwendungen ist bekannt, daß die Suchschlüssel mit stark variierenden Häufigkeiten auftreten können. Zum Beispiel wird ein Programm, das die Schreibweise von Wörtern in einem deutschen Text prüft, wahrscheinlich viel öfter nach Wörtern wie »und« und »der« suchen, als nach Wörtern wie »dynamisch« und »Programmierung«. In ähnlicher Weise wird ein Pascal-Compiler sicher weit häufiger Schlüsselwörter wie »end« und »do« aufsuchen, als »label« oder »downto«. Wenn Suche in einem Binärbaum angewandt wird, ist es natürlich vorteilhaft, die am häufigsten gesuchten Schlüssel in der Nähe der Spitze des Baumes anzuordnen. Um zu bestimmen, wie die Schlüssel im Baum anzuordnen sind, so daß die Gesamtkosten der Suche minimiert werden, kann ein Algorithmus der dynamischen Programmierung benutzt werden.

Jeder Knoten in dem binären Suchbaum in Abbildung 42.4 ist mit einer ganzen Zahl gekennzeichnet, von der angenommen wird, daß sie der Häufigkeit des Zugriffs auf diesen Knoten entspricht. Das heißt, daß zu erwarten ist, daß bei jeweils 18 Suchvorgängen in diesem Baum viermal nach A gesucht wird, zweimal nach B, einmal nach C usw. Bei jedem der vier Suchvorgänge, die A betreffen, sind zwei Zugriffe auf Knoten erforderlich, bei jedem der zwei Suchvorgänge, die B betreffen, drei Zugriffe auf Knoten usw. Wir können ein Maß für die »Kosten« des Baumes berechnen, indem wir einfach die jedem Knoten zugeordnete Häufigkeit mit seinem Abstand von der Wurzel multiplizieren und dann die Summe dieser Produkte bilden. Dies ist die gewichtete innere Pfadlänge des Baumes. Für den Baum in Abbildung 42.4 beträgt die gewichtete innere Pfadlänge 4*2 + 2*3 + 1*1 + 3*3 + 5*4 + 2*2 + 1*3 = 51. Wir möchten für die gegebenen Schlüssel mit den gegebenen Häufigkeiten den binären Suchbaum bestimmen, der unter allen solchen Bäumen die kleinste innere Pfadlänge besitzt.

Abbildung 42.4
Abbildung 42.4 Ein binärer Suchbaum mit Häufigkeiten.

Dieses Problem weist Ähnlichkeiten zu dem Problem der Minimierung der gewichteten äußeren Pfadlänge auf, das wir bei der Betrachtung der Huffman-Kodierung untersucht haben ( Kapitel 22). Bei der Huffman-Kodierung war es jedoch nicht erforderlich, die Reihenfolge der Schlüssel beizubehalten; bei dem binären Suchbaum müssen wir die Eigenschaft erhalten, daß alle links von der Wurzel befindlichen Knoten Schlüssel besitzen, die kleiner sind usw. Diese Forderung bewirkt, daß das Problem dem oben betrachteten Problem der Multiplikation mehrerer Matrizen sehr ähnlich ist; es kann praktisch das gleiche Programm verwendet werden.

Nehmen wir also an, daß eine Menge von Suchschlüsseln K1 < K2 < ... < KN und eine Menge von zugehörigen Häufigkeiten r0, r1, ..., rN gegeben sind, wobei ri die vermutete Häufigkeit des Zugriffs auf den Schlüssel Ki ist. Wir möchten den binären Suchbaum bestimmen, für den die über alle Schlüssel gebildete Summe der Produkte dieser Häufigkeiten mit den Abständen des Schlüssels von der Wurzel (den Kosten des Zugriffs auf den entsprechenden Knoten) minimal wird.

Der Zugang zu diesem Problem mittels dynamischer Programmierung besteht darin, der Reihe nach für jedes j von 1 bis N - 1 die beste Möglichkeit zu berechnen, einen Unterbaum zu erzeugen, der Ki, Ki+1, ..., Ki+j für 1 <= i <= N - j enthält:

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

Für jedes j wird die Berechnung ausgeführt, indem jeder Knoten als Wurzel ausprobiert wird und im voraus berechnete Werte verwendet werden, um die beste Möglichkeit zur Erzeugung der Unterbäume zu ermitteln. Für jedes k zwischen i und i + j möchten wir den optimalen Baum mit Kk als Wurzel finden, der Ki, Ki+1, ..., Ki+j enthält. Dieser Baum wird gebildet, indem der optimale Baum für Ki, Ki+1, ..., Kk-1 als der linke Unterbaum und der optimale Baum für Kk+1, Kk+2, ..., Ki+j als der rechte Unterbaum verwendet wird. Die innere Pfadlänge dieses Baumes ist gleich der Summe der inneren Pfadlängen der beiden Unterbäume und der Summe der Häufigkeiten für alle Knoten (da jeder Knoten in dem neuen Baum einen Schritt weiter von der Wurzel entfernt ist).

Beachten Sie, daß die Summe aller Häufigkeiten jedesmal zu den Kosten addiert wird, weshalb sie für die Bestimmung des Minimums nicht benötigt wird. Weiterhin muß cost[i,i-1] = 0 gelten, um die Möglichkeit zu berücksichtigen, daß ein Knoten nur einen Nachfolger hat (beim Problem der Multiplikation mehrerer Matrizen gab es keine analoge Möglichkeit).

Wie zuvor ist ein kurzes rekursives Programm erforderlich, um anhand des mit Hilfe des Programms berechneten Feldes best den eigentlichen Baum zu rekonstruieren. Abbildung 42.5 zeigt den für den Baum in Abbildung 42.4 berechneten optimalen Baum. Die gewichtete innere Pfadlänge dieses Baums ist 41.

Abbildung 42.5
Abbildung 42.5 Optimaler binärer Suchbaum.

Eigenschaft 42.3 Das Verfahren der dynamischen Programmierung zur Bestimmung eines optimalen binären Suchbaums erfordert eine zu N3 proportionale Zeit und einen zu N2 proportionalen Speicherplatz.

Der Algorithmus arbeitet wieder mit einer Matrix der Größe N2 und benötigt für jedes Element eine zu N proportionale Zeit. In Wirklichkeit ist es in diesem Falle möglich, die erforderliche Zeit auf N2 zu reduzieren, indem man die Tatsache ausnutzt, daß die optimale Position für die Wurzel eines Baumes nicht zu weit von der optimalen Position für die Wurzel eines etwas kleineren Baumes entfernt sein kann, so daß k in dem obigen Programm nicht alle Werte von i bis i + j durchlaufen muß. w.z.b.w.


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