Dynamische Programmierung (1)

Bei der Berechnung beispielsweise der fünften Fibonacci-Zahl ergibt sich der folgende Baum von zu lösenden Teilproblemen:
Fibonacci
Man sieht sofort, daß alle überhaupt benötigten Teilprobleme auch in dem ganz links stehenden Ast liegen. Unsere Rekursionsgleichung
(1) F(n) = F(n-1) + F(n-2) für n > 2
(2) F(1) = F(2) = 1
können wir statt als Zerlegungsvorschrift auch als Aufbauvorschrift lesen und die Knotenwerte im linken Ast von unten nach oben berechnen; die restlichen Werte im Baum fallen dabei mit ab, und genau so haben wir es auch von Hand gemacht.

Die hier verwendete Lösungsstrategie: 

ist bekannt unter der merkwürdigen Bezeichnung dynamische Programmierung (dynamic programming). Sie ist an vielen Stellen anwendbar und stammt ursprünglich aus dem Bereich der Planungsrechnung (Unternehmensforschung oder Operations Research), einem Teilgebiet der Betriebswirtschaftslehre.

Aus demselben Gebiet kommen weitere für uns befremdliche Begriffe wie lineare, quadratische, ganzzahlige Programmierung  (besser heute: lineare Optimierung etc). Dort geht es darum, aus einer Schar von möglichen Zuständen, die durch geeignete Einflußgrößen unter festgelegten Nebenbedingungen gegeben sind, eine optimale Lösung im Sinne einer vorgegebenen (z.B. linearen) Zielfunktion auszuwählen. Mit Programmierung in unserem Sinne hat das primär nichts zu tun, obgleich man natürlich heute Computerhilfe dabei in Anspruch nimmt, sogar in großem Umfang.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36