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.

Algorithmus

Eingabe

$n$ Suchschlüssel, die in einer Sequenz $k_{i},0<i\leq n$ geordnet sind. Außerdem ist für jeden Schlüssel $k_{i}$ die Suchwahrscheinlichkeit $p_{i}$ gegeben. Für jedes $k_{i}$ bezeichnet $q_{i-1}$ die Wahrscheinlichkeit, dass nach einem nichtvorhandenen Schlüssel $x$, mit $k_{i-1}<x<k_{i}$ für $1<i\leq n$ bzw. $x<k_{i}$ für $i=1$, gesucht wird.

Da $p_{i}$ und $q_{i}$ Wahrscheinlichkeiten sind, muss die Summe aller $p_{i}$ und $q_{i}$ 1 ergeben:

$\sum _{i=1}^{n}p_{i}+\sum _{i=0}^{n}q_{i}=1$

Ausgabe

Die minimale erwartete Suchdauer in einem optimalen binären Suchbaum zu der Schlüsselmenge $k_{i}$ 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 $k_{i}$ eine Tiefe von $d(k_{i})$ im Baum hat, dann sind seine Suchkosten $d(k_{i})+1$.

Um die Suchdauer nach nichtvorhandenen Schlüsseln zu modellieren, erhält jedes Blatt $k_{i}$ zwei Kinder-Knoten $d_{i-1}$ und $d_{i}$. Wenn bei der Suche ein $d_{i}$-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{aligned}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{aligned}}$

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\leq n$

Rekursion:

$M[i,j]={\begin{Bmatrix}\min _{i\leq r\leq j}M[i,r-1]+M[r+1,j]+w(i,j)\end{Bmatrix}},0\leq i\leq n,0<j\leq n,i\leq j$

In jeder Zelle $M[i,j]$ steht die minimale Suchdauer unter einem optimalen Suchbaum für die Teilsequenz $i,j$ der Suchschlüsselsequenz $k_{i}$, 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 $k_{r}$ 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})$.

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 356–363. 
• Donald E. Knuth: The Art of Computer Programming 3. Sorting and Searching. 2. Auflage. Addison-Wesley Longman, Amsterdam 1998, ISBN 0-201-89685-0, S. 436–442.