Zur MathePrisma-Startseite
Zur Modul-Startseite  


Dynamisches Programmieren (Dynamisches Programmieren)
 

 
 
hier wird's erst mal trockener
 
Vermutlich haben Sie manchmal den optimalen Weg gefunden, manchmal aber auch nicht. Wie berechnet der Computer den kürzesten Weg durch das Lager?
Alle möglichen Wege und deren Länge zu bestimmen, ist auch für einen Computer zu aufwändig, zumal es hier eine viel bessere Strategie gibt:

das algorithmische Prinzip des
dynamischen Programmierens
 
Voraussetzungen
 
  1. Gesucht ist eine Lösung für ein Problem der Größe n.
    Diese Lösung ist, ebenso wie die Lösungen verwandter Probleme kleinerer Größe, durch eine geeignete Optimalitätsbedingung charakterisiert.

  2. Die Lösung für ein Problem einer bestimmten Größe kann durch Erweiterung oder Kombination von geeigneten Lösungen kleinerer Probleme gewonnen werden.

  3. Unter all den Möglichkeiten, Lösungen kleinerer Probleme zu erweitern oder zu kombinieren, lassen sich Möglichkeiten erkennen, die nicht auf Lösungen größerer Probleme führen (weil sie die entsprechende Optimalitätsbedingung nicht erfüllen).

Unter diesen Voraussetzungen bietet sich dann folgendes algorithmische Vorgehen an. Die kleinste Problemgröße bezeichnen wir dabei mit 0.
 
dynamisches Programmieren
 
Algorithmus

erzeuge zunächst alle Lösungen für die Probleme der Größe 0

für k=1,...,n
für alle Probleme der Größe k
bestimme mögliche Lösungen für dieses Problem durch Erweiterung / Kombination von Lösungen zu Problemen der Größe < k.

verwerfe davon alle die, welche die Optimalitätsbedingung nicht erfüllen.
 

 
Programmiertechnisch muss hier eine sich mit k eventuell ändernde Zahl von Lösungen verwaltet werden. Daher stammt der Name "dynamisches Programmieren".
 
Seite 3/5