Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.
Lizenzbestimmungen
Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel
Bellman-Algorithmus
aus der freien Enzyklopädie
Wikipedia.
Die Inhalte stehen unter der
GNU Lizenz für freie Dokumentation.
Eine Liste der Autoren ist
dort
abrufbar.
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 (siehe Idee).
Idee
Der Bellman-Algorithmus ist ein Beispiel für
Dynamische Programmierung.
Komplexität
Das Ausprobieren sämtlicher Möglichkeit hat exponentielle Komplexität. Durch das verwenden von Teilergebnissen (Konzept der
Dynamischen_Programmierung) kann das Aufzählen der (sinnvollen) Möglichkeiten allerdings auf kubischen Aufwand reduziert werden. Der Algorithmus liegt also in der Komplexitätsklasse
.
