Konzept: Dynamische Programmierung


Verbreitet die Message!

Ein fortgeschrittenes Konzept der Informatik ist dynamische Programmierung. Nehmen wir dazu folgendes einfache Problem und das zugehörige Beispiel her. Stellen wir uns vor man möchte den kürzesten Weg einer Strecke berechnen. Nehmen wir folgendes einfache Beispiel:

Die Frage ist nun, wie man auf kürzestem Weg vom Startpunkt (grün) zum Endpunkt (rot)kommt. Die Zahlen an den Kanten sind dabei die Streckenlängen der Wege – die Grafik dabei nicht maßstabsgetreu. Dabei gilt, dass man den Endpunkt nur über seine direkten Nachbarn (gelb) erreicht und alle weiteren Knoten ebenfalls nur über deren direkte Nachbarn.

Zwischenfrage: Welche allgemeinen Lösungsansätze fallen Dir zu diesem Problem direkt ein? Es ist sinnvoll, dass du dir für das Verständnis vorerst eigene Gedanken machst, bevor du weiterliest.. Poste einen Kommentar mit Deinen Lösungsansätzen!

Ansätze

Es gibt drei Ansätze:

  1. Der naive Ansatz.
  2. Greedy Ansatz
  3. Ansatz mit dynamischem Programmieren

Naiver Ansatz

Der naive Ansatz ist mit einem intuitiven Ansatz („scharfes Hinsehen“) vergleichbar: Man probiert alle Möglichkeiten aus und findet so das Minimum der Strecke. Wie viele Strecken gibt es?

Die Anzahl der Möglichkeiten nimmt mit der Anzahl der Knoten in unserem System exponentiell zu. Im Ausgangsbeispiel sind dies nur 2 Strecken – in einem komplexeren System wird es schnell sehr ineffizient!

Wenn man das Problem auf Städte mit mehreren zehntausend Knotenpunkten und Kanten bezieht ist klar, dass dieser Ansatz nicht akzeptabel ist!

Einfache Heuristik (Greedy)

Ein Greedy-Algorithmus meint, dass in jedem Iterationsschritt die nächstbeste Lösung gewählt wird, also hier von Punkt zu Punkt entschieden wird, welcher Weg korrekt ist. Eine Heutistik ist eine suboptimale, dafür ‘einfache’ (bezogen auf die Laufzeit) Strategie. Diese Heuristik führt nicht zu einem optimalen, dafür zu einem schnell berechenbaren Ergebnis. In unserem Beispiel wählen wir die Strategie vom Startpunkt auszugehen und immer den Weg zum nächsten Knoten zu wählen der am kürzesten ist. Es ist schnell klar, dass dadurch nicht immer der kürzeste Weg gefunden werden kann:

Auch ohne zahlenmäßige Länge der Kanten wird klar, dass zuerst den kürzeren Weg zu wählen (rot) insgesamt zu einem längeren Pfad führt.

Dynamisches Programmieren

Beim Dynamischen Programmieren versucht man nicht, wie üblich, direkt Ergebnisse zu berechnen, sondern man geht schrittweise voran, merkt sich Zwischenergebnisse und rechnet mit diesen Zwischenergebnissen weiter, bis man zum Endergebnis vorangeschritten ist.

Am Beispiel ist der Ansatz, schrittweise jeweils die Kosten des kürzesten Weges zu einen Knoten zu berechnen und sich das Zwischenergebnis für jeden Knoten zu merken. Aufbauend auf diesem Zwischenergebnis, dass den kürzesten Weg zum aktuellen Knoten angibt, kann der kürzeste Weg für den nächsten Knoten berechnet werden. Dies wird wieder als Zwischenergebnis abgespeichert und so bis zum letzten Knoten (Endpunkt) verfahren. So wird effizient die/eine Optimallösung gefunden.

Am Beispiel:

Wir betrachten im ersten Schritt den Startpunkt und einen seiner Nachbarn. Wir schauen uns alle Pfade an, die von dem Startpunkt zum Nachbarn führen – dies ist hier immer nur einer. Deshalb ist auch klar, was die minimalen Wege zum Erreichen der Nachbarn sind: Kosten um Startpunkt zu Erreichen: 0 + Weglänge zum Knoten.

Das war einfach, denn es gibt ja nur eine Verbindung vom Startpunkt zu dessen direkten Nachbarn. Formal haben wir alle möglichen Pfade zwischen zwei Knoten Knoten 1 und Knoten 2 gebildet und daraus das Minimum ausgewählt. Dieses Minimum haben wir zu den bisherigen Kosten für den Weg von Knoten 1 zu Knoten 2 addiert.


Interessant wird es im nächsten Schritt, wir gehen wieder von den letzten Knoten aus und schauen uns deren Nachbarn (gelb) an:

Wir haben hier schon die eindeutigen Nachbarn, mit wieder jeweils nur einer einzigen Möglichkeit berechnet. Wir haben wieder die Knoten paarweise betrachtet und die Kosten um den Knoten zu erreichen mit der einzigen/minimalen Wegstrecke addiert.

Mit ?? sind die Knoten mit mehreren Pfaden markiert, bei denen (noch) nicht klar ist, welche Auswahl wir treffen müssen. Was müssten wir hier (programmatisch) tun?*
Wir müssen hier alle möglichen Kosten berechnen und daraus das Minimum auswählen. Beim Unteren Knoten müssten wir also den mit 6, 5, 7 beschrifteten Knoten betrachten und jeweils die Wegstrecken addieren. Daraus wählen wir dann das Minimum aus (Ergebnisse zur Kontrolle in der nächsten Grafik zu sehen).

* Wir haben hier in der Praxis das Problem, dass wir in einem Schritt die minimalen Kosten für den unteren ?? Knoten berechnen wollen, aber im gleichen Schritt die Kosten für seine Nachbarn benötigen. Wie könnten wir damit umgehen?


Im nächsten Schritt verfahren wir genauso und verwenden letztendlich die Aussage, dass zum Nachbarn A (oben), der kürzeste Weg 7 ist. Der kürzeste Weg zum Nachbarn B ist ebenfalls 7. Der Pfad von A nach Z (rot) hat die Länge 1, während der von B nach Z 6 lang ist ist. Also ist der kürzeste Weg 7+1 = 8. Der kürzeste Weg vom Start bis zum Endpunkt ist also acht.

Fazit

Das Prinzip auf dynamischer Programmierung basiert darauf sich Speicherplatz zu nutze zu machen, um Zwischenergebnisse nicht immer wieder wegzuwerfen, sondern darauf aufbauend zu nutzen. Man muss jedoch sicherstellen, dass das Vorgehen von vornherein zum korrekten Ergebnis führt und dies auch beweisen können. Wie könnte man das beweisen?

Verbreitet die Message!

Schreiben Sie einen Kommentar