|
|
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
|
|
|
Voraussetz-
ungen
|
- 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.
- Die Lösung für ein Problem einer bestimmten Größe
kann durch
Erweiterung oder Kombination von geeigneten Lösungen kleinerer
Probleme gewonnen werden.
- 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".
|
|
|
