Bellman-Algorithmus

Der Algorithmus von Bellman konstruiert aus einer gegebenen Schlüsselliste und einer korrespondierenden Suchwahrscheinlichkeit einen optimalen binären Suchbaum. Der Algorithmus basiert auf dem von Richard Bellman 1957 gefundenen Satz über optimale mittlere Suchdauern in binären Suchbäumen und verwendet die Methode der Dynamischen Programmierung.

Inhaltsverzeichnis

Algorithmus

Eingabe

n Suchschlüssel, die in einer Sequenz k_i, 0<i\le n geordnet sind. Außerdem ist für jeden Schlüssel ki die Suchwahrscheinlichkeit pi gegeben. Für jedes ki bezeichnet qi − 1 die Wahrscheinlichkeit, dass nach einem nichtvorhandenen Schlüssel x, mit ki − 1 < x < ki für 1<i\le n bzw. x < ki für i = 1, gesucht wird.

Da pi und qi Wahrscheinlichkeiten sind, muss die Summe aller pi und qi 1 ergeben:

\sum_{i=1}^n p_i + \sum_{i=0} q_i = 1

Ausgabe

Die minimale erwartete Suchdauer in einem optimalen binären Suchbaum zu der Schlüsselmenge ki und der optimale Suchbaum, unter dem die minimale erwartete Suchdauer erreicht wird.

Gibt es allerdings geometrisch fallende Wahrscheinlichkeiten, dann kann die Suchdauer zu den zugehörigen sehr seltenen Schlüsseln nicht logarithmisch beschränkt werden.

Berechnung der Suchdauer

Mit der Suchdauer einer Schlüsselsuche bzw. den Suchkosten für eine Schlüsselsuche wird die Anzahl der besuchten Knoten auf einem Pfad von der Wurzel bis zum Schlüsselknoten in einem binären Suchbaum bezeichnet. Wenn also ein Schlüssel ki eine Tiefe von d(ki) im Baum hat, dann sind seine Suchkosten d(ki) + 1.

Um die Suchdauer nach nichtvorhandenen Schlüsseln zu modellieren, erhält jedes Blatt ki zwei Kinder-Knoten di − 1 und di. Wenn bei der Suche ein di-Blatt erreicht wird, dann ist der Knoten nicht in dem binären Suchbaum enthalten.

Für einen gegebenen Suchbaum T lässt sich die erwartete Suchdauer berechnen:

\begin{align}
E(T) & = & \sum_{i=1}^n (d(k_i)+1) p_i + \sum_{i=0}^n (d(d_i) +1) q_i \\
     & = & \sum_{i=1}^n d(k_i) p_i + \sum_{i=1}^n p_i + \sum_{i=0}^n d(d_i) q_i + \sum_{i=0}^n q_i \\
     & = & 1 + \sum_{i=1}^n d(k_i) p_i + \sum_{i=0}^n d(d_i) q_i
\end{align}

Rekursive Berechnung

Der Bellman-Algorithmus berechnet die erwartete Suchdauer unter einem optimalen binären Suchbaum rekursiv auf der Sequenz der Suchschlüssel. Die Spezifikation des Algorithmus erfolgt durch Matrix-Rekurrenzen.

Initialisierung:


M[i,i-1] = q_{i-1}, 0<i\le n

Rekursion:

M[i,j] = \begin{Bmatrix}
\min_{i\le r\le j} M[i, r-1] + M[r+1,j] + w(i,j)
\end{Bmatrix}, 0\le i\le n, 0<j\le n, i\le j

In jeder Zelle M[i,j] steht die minimale Suchdauer unter einem optimalen Suchbaum für die Teilsequenz i,j der Suchschlüsselsequenz ki, wobei w(i,j) die Summe aller Suchwahrscheinlichkeiten der Schlüssel in dem Baum zur Teilsequenz bezeichnet. Also ist die minimale Suchdauer für die gesamte Sequenz in der Zelle M[1,n] gespeichert.

In der Rekursion entspricht jede Wahl für r der Auswahl von kr als Wurzel des Baums der Teilsequenz i,j. Die Erzeugung der Wurzel erhöht die Tiefe jedes Knoten in diesem Baum um 1. Also muss die erwartete Suchdauer in diesem Baum um w(i,j) erhöht werden.

w(i,j) ist definiert als

w(i,j) = \sum_{l=i}^j p_l + \sum_{l=i-1}^j q_l

und kann effizient mit einer Matrix-Rekurrenz berechnet werden.

Backtracking

Um einen optimalen Suchbaum mit der minimalen erwarteten Suchdauer zu konstruieren muss die Berechnung des optimalen Wertes in M[1,n] mittels Backtracking zurückverfolgt werden. Alternativ kann in einer Implementation des Algorithmus eine zusätzliche Hilfs-Matrix verwendet werden, welche bei der Berechnung von M mit den optimalen Werten von r für jedes i,j gefüllt und nach der abgeschlossenen Berechnung von M ausgewertet wird.

Komplexität

Die Laufzeit der Berechnung der Matrix für die w(i,j)-Werte liegt in \mathcal O(n^2). Die Matrix M enthält \mathcal O(n^2) Einträge und für jeden Eintrag muss über \mathcal O(n)-Elemente optimiert werden. Also liegt die Laufzeitkomplexität des Algorithmus in \mathcal O(n^3) und der Speicherbedarf in \mathcal O(n^2).

Die Iteration über r in der Rekursion lässt sich weiter einschränken, so dass die Gesamtlaufzeit aller Iterationen in \mathcal O(n) liegt. Also liegt dann die Gesamtlaufzeit des so modifizierten Algorithmus in \mathcal O(n^2).[1]

Literatur

Quellen

  1. Donald Ervin Knuth: The Art of Computer Programming 3. Sorting and Searching. 2. Auflage. Addison-Wesley Longman, Amsterdam 1998, ISBN 0201896850, S. 436–442.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bellman — Den Namen Bellman tragen unter anderem: Carl Michael Bellman (1740–1795), schwedischer Liederdichter des Rokoko Gina Bellman (*1966), britische Schauspielerin Richard Bellman (1920–1984), amerikanischer Mathematiker (Bellman Algorithmus,… …   Deutsch Wikipedia

  • Algorithmus von Bellman und Ford — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Bellman-Ford-Moore-Algorithmus — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Bellman-Ford-Algorithmus — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Algorithmus von Dijkstra — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Algorithmus von Floyd und Warshall — Der Algorithmus von Floyd und Warshall (auch Floyd Warshall Algorithmus oder Tripel Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. In Floyds Version findet er die kürzesten Pfade zwischen… …   Deutsch Wikipedia

  • Richard Bellman — (* 29. August 1920 in Brooklyn, New York; † 19. März 1984 in Los Angeles, Kalifornien) war ein US amerikanischer Mathematiker. Inhaltsverzeichnis 1 Leben 2 Schriften 3 …   Deutsch Wikipedia

  • Moore-Bellman-Ford-Algorithmus — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Dijkstras Algorithmus — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Floyd-Warshall-Algorithmus — Der Algorithmus von Floyd und Warshall (auch Floyd Warshall Algorithmus oder Tripel Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”