R2 Wegeprobleme

Ein grundlegendes und zugleich in der Praxis sehr relevantes Problem ist, in einem Netzwerk den kürzesten Weg zu finden. Wir alle nutzen Algorithmen die dieses Problem lösen, wenn wir zum Beispiel in einer Online-Straßenkarte den Weg zwischen zwei Punkten berechnen lassen oder auch wenn wir uns im Navigationssystem den Weg von unserem aktuellen Standort zu einem Ziel anzeigen lassen. Dabei muss kurz nicht immer im Sinne einer kurzen zurückzulegenden Entfernung gemeint sein, sondern es kann auch der zeitkürzeste Weg oder der kostengünstigste Weg gesucht werden.

Zum Auffinden des kürzesten Weges gibt es verschiedene Algorithmen. Moderne Routenplanungssysteme arbeiten sicher mit sehr raffinierten Algorithmen, um in Bruchteilen von Sekunden den kürzesten Weg in sehr großen Netzwerken zu finden. Nachfolgend wird ein sehr elementarer Algorithmus vorgestellt. Auch mithilfe der Linearen Optimierung lassen sich Kürzeste-Wege-Probleme lösen. Allerdings sind spezielle Graphenalgorithmen aus verschiedenen Gründen meist besser geeignet.

Eng verwandt mit dem Kürzester-Weg-Problem ist das Längster-Weg-Problem. Dieses wird ebenfalls in diesem Kapitel behandelt.

Kürzeste Wege Probleme

Die brutale Methode den Weg zu finden – alle Möglichkeiten durchprobieren

Manchmal kann man Probleme auch mit roher Gewalt, oder sagen wir besser mit unermüdlichem Fleiß, lösen, indem man alle Möglichkeiten durchprobiert. Dieser Ansatz, in der Fachsprache vollständige Enumeration genannt, bleibt jedoch in aller Regel hinter intelligenten Lösungsverfahren zurück. Bei den kleinen Problemen, die typischerweise als Beispiele verwendet werden, wird der Vorteil leider oft nicht sichtbar. Dort ist das Durchprobieren noch eine halbwegs gangbare Möglichkeit und scheint im Vergleich zur Anwendung eines Algorithmus das einfachere Vorgehen zu sein. An dieser Stelle sei versichert, dass dies nur bei wirklich kleinen Problemen zielführend ist.

Übrigens ist selbst das systematische Durchprobieren oft nicht so einfach, wie es vielleicht auf den ersten Blick aussieht, da ein Vorgehen (=Algorithmus) gefunden werden muss, dass jeden möglichen Weg berücksichtigt und andererseits nicht mehrfach den gleichen Weg betrachtet.

Nachfolgend zwei wirklich sehr kleine Probleme, die mittels vollständiger Enumeration gelöst werden:

beispiel_kuerzester_weg_im_gerichteten_graph — Abb. 2-1: Beispiel kürzester Weg im gerichteten Graph

Die möglichen Wege in dem einfachen, kreisfreien, gerichteten Graphen aus Abb. 2-1. sind in Abb. 2-2 dargestellt.

Loesung_mit_vollstaendiger_enumeration — Abb. 2-2: Lösung mittel vollständiger Enumeration im gerichteten Graph

Vom Knoten A kommt man in die Knoten B und C,
vom Knoten B kommt man weiter nach D und E,
von Knoten C weiter nach B und E usw.

Man kann die möglichen Wege als Baum aufzeichnen. Die Entfernung vom Startknoten auf dem jeweiligen Weg ist über den Knoten vermerkt.

Es gibt 7 mögliche Wege, der Weg A-C-B-D-Z ist mit 10 der kürzeste Weg von A nach Z.

Schwieriger wird es bei Graphen, die Kreise enthalten bzw. ungerichtet sind, wie z.B. der in Abb. 2.3.

beispiel_kuerzester_weg_im_ungerichteten_graphen — Abb. 2-3: Beispiel Kürzester Weg im ungerichteten Graph

Hier ist beim Durchprobieren der möglichen Wege darauf zu achten, dass innerhalb eines Weges der gleiche Knoten nicht zweimal vorkommt, d.h. dass ein Teilweg ein Kreis ist.

Beispiel
A-B-D-E-B-D-Z
oder
A-B-C-A-B-C-A-B-C-……

Grund ist, dass sonst der Kreis unendlich durchlaufen werden könnte und von daher das Durchprobieren nie abgeschlossen werden könnte.

loesung_mittels_enumeration_ungerichtet — Abb. 2-4: Lösung mittels vollständiger Enumeration im ungerichteten Graph (gestrichene Knoten: Kreis)

In Abb. 2-4. wurde die vollständige Enumeration für den Graphen aus Abb. 2-3 durchgeführt. Der direkte Rückweg (also Kreise wie A-B-A) wurden von vornherein ausgeschlossen. Die Knoten die einen Kreis schließen wurden gestrichen. Selbst die Lösung des kompakten Beispiels ist recht aufwändig.

Hinweis für aufmerksame Leser

Einigen sehr aufmerksamen Lesern ist vielleicht auch aufgefallen, dass innerhalb des Baums mit allen Wegen derselbe Knoten auf verschiedenen Wegen vorkommen kann, und zwar mit unterschiedlichen Entfernungen zum Startknoten. Zum Beispiel kommt der Knoten B zweimal vor, einmal der direkte Weg A-B mit einer Länge von 5 und einmal der kürzere Weg A-C-B mit einer Länge von 4.

Bellmansches_optimalitaetsprinzip — Abb. 2-5: Bellmannsche Optimalitätsprinzip