Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


42. Dynamische Programmierung



Zeit- und Speicheraufwand

Aus den obigen Beispielen ist ersichtlich, daß der Aufwand an Zeit und Speicherplatz für Anwendungen der dynamischen Programmierung in Abhängigkeit von der Informationsmenge über kleine Teilprobleme sehr unterschiedlich sein kann. Für den Algorithmus der kürzesten Pfade wird kein zusätzlicher Speicherplatz benötigt; für das Rucksack-Problem ist ein zu der Größe des Rucksacks proportionaler Speicherplatz erforderlich; für die übrigen Probleme wird ein zu N2 proportionaler Speicherplatz benötigt. Jedes der Probleme benötigt zur Lösung eine den Speicherplatz um den Faktor N übersteigende Zeit.

Das Spektrum der Anwendungsmöglichkeiten der dynamischen Programmierung ist weit umfangreicher, als die Beispiele zeigen. Vom Standpunkt der dynamischen Programmierung aus kann die Rekursion auf der Grundlage des Prinzips »Teile und Herrsche« als ein Spezialfall betrachtet werden, in dem eine minimale Menge an Information über kleine Probleme berechnet und gespeichert werden muß, und die erschöpfende Suche (das wir in Kapitel 44 betrachten) kann als ein Spezialfall angesehen werden, in dem eine maximale Menge an Information über kleine Probleme berechnet und gespeichert werden muß. Die dynamische Programmierung ist eine in vielerlei Gestalt auftretende natürliche Methode der Entwicklung von Lösungsverfahren für Probleme aus diesem Bereich.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]