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

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

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

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle k_{i}}$ eine Tiefe von ${\displaystyle d(k_{i})}$ im Baum hat, dann sind seine Suchkosten ${\displaystyle d(k_{i})+1}$.

Um die Suchdauer nach nichtvorhandenen Schlüsseln zu modellieren, erhält jedes Blatt ${\displaystyle k_{i}}$ zwei Kinder-Knoten ${\displaystyle d_{i-1}}$ und ${\displaystyle d_{i}}$. Wenn bei der Suche ein ${\displaystyle d_{i}}$-Blatt erreicht wird, dann ist der Knoten nicht in dem binären Suchbaum enthalten.

Für einen gegebenen Suchbaum ${\displaystyle T}$ lässt sich die erwartete Suchdauer berechnen:

${\displaystyle {\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:

${\displaystyle M[i,i-1]=q_{i-1},0<i\leq n}$

Rekursion:

${\displaystyle 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 ${\displaystyle M[i,j]}$ steht die minimale Suchdauer unter einem optimalen Suchbaum für die Teilsequenz ${\displaystyle i,j}$ der Suchschlüsselsequenz ${\displaystyle k_{i}}$, wobei ${\displaystyle 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 ${\displaystyle M[1,n]}$ gespeichert.

In der Rekursion entspricht jede Wahl für ${\displaystyle r}$ der Auswahl von ${\displaystyle k_{r}}$ als Wurzel des Baums der Teilsequenz ${\displaystyle 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 ${\displaystyle w(i,j)}$ erhöht werden.

${\displaystyle w(i,j)}$ ist definiert als

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle M}$ mit den optimalen Werten von ${\displaystyle r}$ für jedes ${\displaystyle i,j}$ gefüllt und nach der abgeschlossenen Berechnung von ${\displaystyle M}$ ausgewertet wird.

Komplexität

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

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

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 (englisch). 
• 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. 

Quellen

1. 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.