Breitensuche

Hefteintrag        Lösung für den Scotch-Terrier

Arbeitsweise
Man geht vom Startknoten v aus und besucht zunächst alle Knoten, die den Abstand k = 1 von v haben. Sind diese Knoten in einer Warteschlange zwischengespeichert, werden alle direkten Nachbarn dieser Knoten besucht, nicht entdeckte Knoten kommen in die Warteschlange. Die nächste Tiefenebene wird also erst dann begonnen, wenn alle Knoten der momentanen Ebene schon besucht sind.

Die Front zwischen entdeckten und unentdeckten Knoten erstreckt sich gleichmäßig über die gesamte Breite erstreckt. Daher der Name Breitensuche.

Was ist eine Warteschlange? Eine Warteschlange, auch Queue bezeichnet, ist eine sich dynamisch ändernde Datenstruktur, in welche man Daten speichern und aus der man Daten entfernen kann.
Das Entfernen der Elemente erfolgt nach dem FIFO - Prinzip, d.h. das am längsten in der Warteschlange verweilende Element wird als erstes entfernt.
Bei der Breitensuche werden zuerst alle Markierungen zurückgesetzt, dann der Startknoten markiert und in die Warteschlange eingereiht. Solange de Schlange nicht leer ist,wird der erste Knoten entnommen und besucht, seine noch nicht besuchten Nachbarknoten markiert und an das Ende der Schlange gesetzt. Die Markierung wird mit dem Eigenbau-Graphen des Applets von Aufgabe d) veranschaulicht

Graphen selbst erstellen
Aufgabe a) Nutzen Sie den Grapheditor 1 , um selbst Graphiken zu erstellen.
Aufgabe b) Eine weitere Möglichkeit, Graphen zu erstellen und darauf zum Beispiel die Breitensuche zu veranschaulichen, erreicht man mit dem Tool GATO.

Klicken Sie auf File / Open Alg und dann auf BFS. In dem einen Fenster sehen Sie den Algorithmus, in dem anderen einen Graphen, der in der Demonstration schrittweise durchsucht werden kann. 		 

Algorithmus
1. Bestimme den Knoten, an dem die Suche beginnen soll, und speichere ihn in einer Warteschlange ab.
2. Entnimm einen Knoten vom Beginn der Warteschlange und markiere ihn.
3. Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere "gefunden" zurück.
4. Ansonsten hänge alle bisher unmarkierten Nachfolger dieses Knotens, die sich noch nicht in der Warteschlange befinden, ans Ende der Warteschlange an.
5. Wiederhole ab Schritt 2.
6. Ist die Warteschlange leer, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere "nicht gefunden" zurück.

Applet 1

Aufgabe c) Experimentieren Sie mit diesem Applet zur Breiten- und Tiefensuche, bei dem die Knoten mit Weiß / Grau / Schwarz entsprechend des Fortschritts des Suchvvorgangs gekennzeichnet werden

  weiß unentdeckt
  grau entdeckt, aber noch nicht fertigbehandelt
  schwarz fertig (und damit auch entdeckt)

Reihenfolge: weiß Þ grau Þ schwarz

Komplexität
Jeder Knoten wird höchstens einmal in die Warteschlange eingereiht und damit auch höchstens einmal ausgereiht. Das ergibt: O ( V ) . Und da für jeden Knoten die Adjazenzliste durchlaufen wird, ergibt sich insgesamt höchstens O ( E ) .
Also: O(alle Knoten + alle Kanten)

Anwendung
- alle Zusammenhangskomponenten in einem Graph finden
- alle Knoten innerhalb einer Zusammenhangskomponente finden
- den kürzesten Pfad zwischen zwei Knoten finden
- das Kürzeste-Kreise-Problem

Dijkstra - Algorithmus

Löst folgendes Problem: Wie komme ich am schnellsten von A nach B?

0.

Startstadt markieren und Kennzahl 0 zuweisen und als aktuelle Stadt.bezeichnen

1.

Von der aktuellen Stadt zu allen direkt erreichbaren Nachbarstädten gehen

... für jede Nachbarstadt Folgendes durchführen:

Summe aus der Kennzahl an der aktuellen Stadt und der Streckenlänge dorthin errechnen

- Wenn Nachbarstadt rot markiert, nichts machen
- Wenn Nachbarstadt keine Kennzahl hat, ihr die Summe als Kennzahl zuweisen,       Strecke zur aktuellen Stadt markieren
- Wenn Nachbarstadt eine Kennzahl kleiner der Summe hat, nichts machen
- Wenn Nachbarstadt eine Kennzahl größer der Summe hat,
   dortige Kennzahl sowie die Markierung streichen und
   Summe als neue Kennzahl zuweisen,
   Strecke zur aktuellen Stadt markieren

2.

Bei Städten mit Kennzahl, aber nicht markiert, die Stadt mit der kleinsten Kennzahl wählen

3.

diese als aktuelle Stadt bezeichnen
Wenn mehrere Städte mit kleinster Kennzahl vorhanden, eine beliebige davon als aktuelle Stadt wählen

4.

Stadt und Strecke markieren

5.

Falls es noch unmarkierte Städte gibt - weiter bei 1.

Beispiel bei Wikipedia

Arbeitsblatt

Aufgabe d): Erstellen Sie mit Hilfe dieses Applets ein Wegenetz und ermitteln Sie mit Hilfe des Dijkstra-Algorithmus die kürzeste Strecke zu einem selbst gewählten Ort!
Aufgabe e): Abstrahieren Sie von einer vorhanden Karte auf ein Wegenetz. Erstellen Sie mit Hilfe des Dijkstra-Algorithmus die kürzeste Strecke zu einem selbst gewählten Ort!

Beispiel für eine Straßenkarte, Beispiel für eine Abstraktion dieser Karte
Zumindest eine ähnliche Straßenkarte wäre wichtig; die Abstraktion kann händisch mittels Schablone gezeichnet werden.

Hinweis: Dijkstra-Algorithmus gehört zu den gefräßigen, gierigen Strategien (greedy).
Schema: In jedem Schritt den besten "Happen" bekommen, ohne aufwendiges Backtracking.

- einfache Implementierung
- vergleichsweise sehr effizient
- nicht jedes Problem mit Greedy exakt lösbar

Java-Applet zur Veranschaulichung