Dynamische Programmierung

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Algorithmen der dynamischen Programmierung kommen bei Optimierungsproblemen zur Anwendung bei denen das Endergebnis einer unbekannten Kombination von vielen nicht notwendigerweise Teilergebnissen berechnet werden kann.

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

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

Siehe auch: Teile und herrsche

Bücher zum Thema Dynamische Programmierung

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Dynamische_Programmierung.html">Dynamische Programmierung </a>