imported>Invisigoth67: typo

2024-10-06T14:40:36Z

typo

Neue Seite

Der '''Algorithmus von Bellman''' konstruiert aus einer gegebenen Schlüsselliste und einer korrespondierenden Suchwahrscheinlichkeit einen optimalen [[Binärer Suchbaum|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 [[Dynamische Programmierung|Dynamischen Programmierung]].

== Algorithmus ==
;Eingabe:
<math>n</math> Suchschlüssel, die in einer Sequenz <math>k_i, 0<i\le n</math> geordnet sind. Außerdem ist für jeden Schlüssel <math>k_i</math> die Suchwahrscheinlichkeit <math>p_i</math> gegeben. Für jedes <math>k_i</math> bezeichnet <math>q_{i-1}</math> die Wahrscheinlichkeit, dass nach einem nichtvorhandenen Schlüssel <math>x</math>, mit <math>k_{i-1}<x<k_i</math> für <math>1<i\le n</math> bzw. <math>x<k_i</math> für <math>i=1</math>, gesucht wird.

Da <math>p_i</math> und <math>q_i</math> Wahrscheinlichkeiten sind, muss die Summe aller <math>p_i</math> und <math>q_i</math> 1 ergeben:

<math>\sum_{i=1}^n p_i + \sum_{i=0}^n q_i = 1</math>

;Ausgabe:
Die minimale erwartete Suchdauer in einem optimalen binären Suchbaum zu der Schlüsselmenge <math>k_i</math> 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 (Graphentheorie)|Pfad]] von der [[Wurzel (Graphentheorie)|Wurzel]] bis zum Schlüsselknoten in einem binären Suchbaum bezeichnet. Wenn also ein Schlüssel <math>k_i</math> eine [[Tiefe (Graphentheorie)#Tiefe|Tiefe]] von <math>d(k_i)</math> im Baum hat, dann sind seine Suchkosten <math>d(k_i)+1</math>.

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

Für einen gegebenen Suchbaum <math>T</math> lässt sich die [[Erwartungswert|erwartete]] Suchdauer berechnen:

<math>\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}
</math>

; 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:''

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

''Rekursion:''

<math>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
</math>

In jeder Zelle <math>M[i,j]</math> steht die minimale Suchdauer unter einem optimalen Suchbaum für die Teilsequenz <math>i,j</math> der Suchschlüsselsequenz <math>k_i</math>, wobei <math>w(i,j)</math> 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 <math>M[1,n]</math> gespeichert.

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

<math>w(i,j)</math> ist definiert als

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

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 <math>M[1,n]</math> mittels [[Backtracking]] zurückverfolgt werden. Alternativ kann in einer Implementation des Algorithmus eine zusätzliche Hilfs-Matrix verwendet werden, welche bei der Berechnung von <math>M</math> mit den optimalen Werten von <math>r</math> für jedes <math>i,j</math> gefüllt und nach der abgeschlossenen Berechnung von <math>M</math> ausgewertet wird.

== Komplexität ==

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

Die Iteration über <math>r</math> in der Rekursion lässt sich weiter einschränken, so dass die Gesamtlaufzeit aller Iterationen in <math>\mathcal O(n)</math> liegt. Also liegt dann die Gesamtlaufzeit des so modifizierten Algorithmus in <math>\mathcal O(n^2)</math>.<ref>{{Literatur |Autor=[[Donald E. Knuth]] |Titel=The Art of Computer Programming 3. Sorting and Searching |Verlag=Addison-Wesley Longman |Ort=Amsterdam |Jahr=1998 |ISBN=0201896850 |Auflage=2. |Seiten=436–442}}</ref>

== Literatur ==
* {{BibISBN|0262032937|Seite=356–363}}
* {{Literatur |Autor=[[Donald E. Knuth]] |Titel=The Art of Computer Programming 3. Sorting and Searching |Verlag=Addison-Wesley Longman |Ort=Amsterdam |Jahr=1998 |ISBN=0201896850 |Auflage=2. |Seiten=436–442}}

== Quellen ==
<references />

[[Kategorie:Dynamische Programmierung]]

[[en:Binary search tree#Optimal binary search trees]]

Bellman-Algorithmus - Versionsgeschichte

imported>Invisigoth67: typo