nach Jens Gallenbacher: Abenteuer Informatik

Abstraktion #

Als Vorbereitung abstrahieren wir die Karte und behalten nur, was für den Computer, resp. den Algorithmus benötigt wird.

Ausgangskarte #

Als Beispiel wollen wir einen Weg auf einer Karte finden: Es geht von Imstadt nach Lupera.

Schritt 1 #

Zuerst einmal überlegen wir uns, was denn für die Aufgabe überhaupt wichtig ist. Dabei vereinfachen wir die Karte:

• Aus den Städten werden «Knoten» mit einem einzelnen, aber eindeutigen Buchstaben
• Kreuzungen werden zu «Knoten»
• Strassen werden zu einheitlichen «Kanten» (wir vernachlässigen den Strassentyp)
• Die Distanzen bleiben erhalten und werden den Kanten zugewiesen

Schritt 2 #

Wir können weiter vereinfachen:

• Kreuzungs-Knoten werden gleich behandelt wie Städte: Sie erhalten einen Buchstaben der noch nicht vergeben ist.
• Kanten können gerade dargestellt werden: Dort wo sich zwei Kanten kreuzen gibt es keine Kreuzung!

Endergebnis #

Was wir nun erhalten ist ein Gewichteter Graph: Ein Graph besteht aus Kanten und Knoten. Bei einem gewichteten Graphen hat zusätzlich jede Kante ein Gewicht – bei uns die Länge der Strasse welcher durch die Kante dargestellt wird. Im Gegensatz zur Baumstruktur, darf ein Graph auch Loops beinhalten. («Rundfahrten» sind erlaubt.)

Diesen Graphen können wir nun verwenden, um automatisiert einen Weg – oder sogar den kürzesten Weg zwischen zwei Ortschaften zu finden.

Breitensuche #

Bei der Breitensuche gehen wir – salopp gesagt – in alle Richtungen gleich schnell. Dabei werden etwaige Gewichte zwischen den Knoten ignoriert. Wir werden also einen Weg finden, aber nicht zwingend den Kürzesten!

Für die Suche brauchen wir zwei Listen, womit wir unseren Suchfortschritt festhalten:

Closed-List

Hier werden alle abgehandelten Knoten aufgelistet

Open-List

Hier werden alle bekannten Knoten welche als nächste Kandidaten in Frage kommen aufgeführt

Vorbereitung #

Zu Beginn ist die Closed-List leer. Der Startknoten kommt auf die Open-List:

Closed-List: –
  Open-List: I

Schritt 1 #

Wir nehmen den ersten Knoten von der Open-List – das ist I – und besuchen alle Nachbarn. Diese werden der Open-List angehängt. Der Knoten I gilt jetzt als besucht: Er wird von der Open-List gestrichen und kommt auf die Closed-List.

Closed-List: I
  Open-List: M, C, B, H, P

Schritt 2 #

Nun besuchen wir wiederum den ersten Knoten auf der Open-List, nämlich M. Die Nachbarn A und X kommen zuhinterst auf die Open-List. Der Nachbar C ist bereits auf einer Liste, d.h. wir haben bereits einen Weg zu C gefunden. Die Kante zwischen M und C wird entfernt. (Wir wollen am Schluss zu jedem Knoten nur genau einen Weg haben.)
M kommt auf die Closed-List.

Closed-List: I, M
  Open-List: C, B, H, P, A, X

Schritt 3 #

Erneut gehen wir zum ersten Knoten auf der Open-List, also C, und schauen uns dessen Nachbarn an: M und X sind bereites bekannt.
C kommt auf die Closed-List.

Closed-List: I, M, C
  Open-List: B, H, P, A, X

Schritt 4 #

Jetzt sind die Nachbarn von B dran: D kommt auf die Open-List, ebenso Z. Den Weg zu H haben wir bereits gefunden. Wir können dies Kante also streichen.
B kommt auf die Closed-List.

Closed-List: I, M, C, B
  Open-List: H, P, A, X, D, Z

Schritt 5 #

Der nächste Knoten auf der Open-List ist H. Wir fügen die noch nicht besuchten Nachbarn von H zur Open-List hinzu. Es sind dies L, Y und K. L ist unser gesuchtes Ziel: wir haben also einen Weg von I nach L gefunden, und zwar über H. H kommt auf die Closed-List und wir brechen den Algorithmus ab.

Closed-List: I, M, C, B, H
  Open-List: P, A, X, D, Z, L, Y, K

Ergebnis #

Die roten Linien und Knoten im Graphen stellen einen Baum dar. Wenn wir die Knoten nun etwas umpositionieren erhalten wir den folgenden erforschten Baum:

Dieser Baum zeigt zu jedem erforschten Knoten genau einen Weg vom Startknoten aus. Da wir den Algorithmus abgebrochen haben, sobald wir den Zielknoten gefunden haben, sind nicht alle Knoten aufgelistet. Aber wir finden den gesuchten Weg zum Zielknoten.

Wir zeichnen nun noch mit Pfeilen die Reihenfolge ein in welcher wir diese Knoten «durchsucht» haben:

Diese Art der Baumsuche nennt man Breitensuche.

Ameisen #

Mit der Breitensuche haben wir einen Weg gefunden, aber nicht zwingenderweise den schnellsten. Wie können wir nun aber die Gewichte der Kanten berücksichtigen und den schnellsten Weg finden? Dafür führt Jens Gallenbacher die Idee mit den Ameisen ein:

Die Ameisen starten gleichzeitig beim Startknoten. In alle Richtungen schwärmen sie gleich schnell aus:

Erreichen Ameisen einen ersten Nachbarknoten, so teilen sie sich sogleich und folgen allen weiteren Verzweigungen, immer noch im genau gleichen Tempo.

Dasselbe passiert nun bei verschiednen Knoten. Teilweise marschieren Ameisen auf der selben Kante aufeinander zu.

Treffen sich aus unterschiedlicher Richtung kommende Ameisen auf einer Kante, so wird diese Kante entfernt: Man weiss dass die beiden Knoten, von wo die Ameisen aus auf diese Kante gekommen sind, bereits entdeckt sind.

So geht das Entdecken weiter: Bei neuen Knoten teilen sich die Ameisen, bei Kanten begegnen sie sich.

Schlussendlich ist jeder Knoten von Ameisen entdeckt worden. Und zwar immer auf dem schnellsten Weg vom Startknoten aus. Wenn wir die nicht-durchgestrichenen Kanten zurück zum Start verfolgen, haben wir also den schnellsten Weg gefunden.

Dijkstra #

Wir wollen versuchen den «Ameisen»-Algorithmus für den Computer umzusetzen. Es macht nämlich wenig Sinn, sich gleichmässig auf den Kanten fortzubewegen. Wir kennen ja die Distanzen zwischen den Knoten. Statt zu schauen, welche Ameisen zuerst beim nächsten Knoten sind, wählen wir den «besten» Knoten von unserer Open-List und gehen dort weiter! Dazu notieren wir auf unser Open-List immer die bereits zurückgelegte Distanz vom Startknoten.

Vorbereitung #

Der Startknoten kommt auf die Open-List. Die zurückgelegte Distanz (von Startknoten zu Startknoten) ist natürlich 0.

Closed-List: –
  Open-List: I (0)

Schritt 1 #

Wir fügen alle Nachbarn des Startknotens auf die Open-List. Dabei berechnen wir wie weit es vom Startknoten zum jeweiligen Knoten ist.
I kommt auf die Closed-List.

Closed-List: I
  Open-List: M (43), C (40), B (34), H (65), P (55)

Vorbereitung Schritt 2 #

Wir suchen den besten Kandidaten aus unserer Open-List heraus. Der Knoten B hat die kleinste Distanz, also machen wir dort weiter!

Schritt 2 #

Wir berechnen für alle Nachbarn des Knotens B ihre Distanz vom Startknoten über B. Ist der Knoten noch nicht auf der Open-List, wird dieser hinzugefügt. Ist ein Knoten – wie hier der Knoten H – bereits auf der Open-List, schauen wir, ob wir einen kürzeren Weg gefunden haben. Wenn ja, aktualisieren wir den Knoten auf der Open-List.
B kommt auf die Closed-List.

Closed-List: I, B
  Open-List: M (43), C (40), H (64), P (55), X (60), A (103), D (98), Z (66)

Schritt 3 #

Der nächste «beste» Kandidat auf unserer Open-List ist C. Die Nachbarn von C sind aber bereits auf der Open-List – und zwar mit kürzerer Distanz als über C.
C kommt auf die Closed-List.

Closed-List: I, B, C
  Open-List: M (43), H (64), P (55), X (60), A (103), D (98), Z (66)

Der Algorithmus #

Der Algorithmus kann wie folgt schematisch dargestellt werden:

Endzustand #

Wenn wir nur den besten Weg finden wollen, können wir den Algorithmus abbrechen, sobald der Zielknoten der «beste» Kandidat auf der Open-List ist. Dann wissen wir: Es gibt keinen kürzeren Weg!

Wir können den Algorithmus auch weiterlaufen lassen. Am Schluss erhalten wir dann einen «Baum» (alle roten Kanten). Dieser Baum stellt die schnellsten Wege von I zu jedem anderen Knoten des Graphen dar.

gerichtete Graphen #

Das Ganze funktioniert auch für sogenannt «gerichtete Graphen», also z.B. Karten mit Einbahnstrassen: