Infos Home | Impressum | Original Artikel & Autoren Liste

Dynamische Programmierung

Algorithmen der dynamischen Programmierung kommen bei Optimierungsproblemen zur Anwendung, bei denen das Endergebnis aus einer unbekannten Kombination von vielen, nicht notwendigerweise unabhängigen, Teilergebnissen berechnet werden kann.

Um sich bei der Lösung kostspielige Rekursionen ohne Wiederverwendung schon berechneter Zwischenlösungen zu ersparen, werden einfach sämtliche Teilergebnisse im Voraus berechnet und in einer Tabelle oder Liste gespeichert. Dabei ist noch das Problem zu lösen, wie die Teilergebnisse geeignet indiziert werden. Das Endergebnis ergibt sich dann im Enddurchlauf, indem die optimale Verkettung von Teillösungen durchlaufen und diese Teillösungen zusammengerechnet werden.

Die Grundprinzipien der dynamischen Programmierung wurden zwar schon in den 1957 von Richard Bellman formuliert, ihre Hauptanwendung fanden sie jedoch erst bei den Sequenz-Alignment-Problemen der Bioinformatik.

Siehe auch: Teile und herrsche

Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.

Webtipps: Branchenbuch Deutschland