Robert Sedgewick: Algorithmen

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


42. Dynamische Programmierung



Das Prinzip »Teile und Herrsche« diente als Grundlage für die Entwicklung vieler der von uns untersuchten Algorithmen: Um ein umfangreiches Problem zu lösen, zerlege man es in kleinere Probleme, die unabhängig voneinander gelöst werden können. In der dynamischen Programmierung wird dieses Prinzip bis zum Extrem weiterentwickelt: Wenn wir nicht genau wissen, welche kleineren Probleme zu lösen sind, lösen wir sie einfach alle und speichern dann die Ergebnisse zum Zwecke der späteren Verwendung bei der Lösung größerer Probleme. Dieser Ansatz ist in Operations Research weit verbreitet. Hierbei bezieht sich der Begriff »Programmierung« auf den Prozeß der Formulierung der Bedingungen eines Problems, um das Verfahren anwendbar zu machen. Dies ist eine Technik, auf deren weitere Einzelheiten wir nicht eingehen werden; wir betrachten lediglich einige Beispiele. (Die »Programmierung«, die uns interessiert, besteht in der Erstellung von Pascal-Programmen zur Ermittlung der Lösungen.)

Wir haben bereits einige Algorithmen betrachtet, die in das Schema der dynamischen Programmierung passen. Zum Beispiel laufen sowohl der Algorithmus von Warshall zur Bestimmung der transitiven Hülle eines Graphen als auch der Algorithmus von Floyd zur Bestimmung aller kürzesten Pfade in einem gewichteten Graph (beide aus Kapitel 32) in der Weise ab, daß die Knoten der Reihe nach betrachtet werden, wobei für den gerade betrachteten Knoten unter Benutzung von Lösungen für alle zuvor betrachteten Knoten Teilprobleme gelöst werden.

Bei jeder Anwendung der dynamischen Programmierung können zwei Schwierigkeiten auftreten. Erstens muß es nicht immer möglich sein, die Lösungen kleinerer Probleme so zu kombinieren, daß sich die Lösung eines größeren Problems ergibt. Zweitens kann die Anzahl der zu lösenden kleinen Probleme unvertretbar groß sein. Es ist noch nicht gelungen, genau anzugeben, welche Probleme mit Hilfe der dynamischen Programmierung in effizienter Weise gelöst werden können; es gibt viele »schwierige« Probleme, für die sie nicht anwendbar zu sein scheint (siehe Kapitel 44 und 45), aber auch viele »leichte« Probleme, für die sie weniger effizient ist als Standardalgorithmen.

Im vorliegenden Kapitel stellen wir mehrere Probleme vor, für die die dynamische Programmierung sehr effizient ist. Diese Probleme erfordern es, nach der »besten« Lösung einer Aufgabe zu suchen. Sie besitzen die generelle Eigenschaft, daß jede Entscheidung, die beider Bestimmung der besten Lösung eines kleinen Teilproblems getroffen wird, eine gute Entscheidung bleibt, wenn dieses Teilproblem zu einem Teil eines umfangreicheren Problems wird.


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