Breitensuche

Die Breitensuche (Breadth First Search, BFS) sucht nach dem kürzesten (kostengünstigsten) Weg in einem Baum, sie liefert also immer den idealen Weg.

Vorgehensweise

Hierbei werden zuerst alle Nachbarknoten des Startknoten (alle Knoten mit der Tiefe 1) durchsucht und erst danach alle Nachbarknoten der Nachbarknoten (alle Knoten mit der Tiefe 2) usw. Dies hat den Vorteil, dass der kürzeste Weg mit Sicherheit als erstes gefunden wird. Zyklen im Suchgraph sind zwar etwas lästig (und sollten somit bei praktischer Verwendung vermieden werden), jedoch sind diese für diesen Algorithmus nicht notwendigerweise auszuschließen.

Im Gegensatz zur Tiefensuche löst sie trivialere Probleme sehr schnell. Trivialere Probleme sind hier beispielsweise:

• Ziel ist nur wenige Schritte entfernt
• Schachmatt in wenigen Zügen

Algorithmus

Suche_Weg( Knoten Ziel, Knoten Start )
  Knoten_Queue KQueue
  KQueue.Push( Start )

  Für alle Knoten aus KQueue
    Aktuell = KQueue.Pop

    Wenn Aktuell = Ziel
      Ziel gefunde

    Für K = alle nicht besuchten Nachbarknoten von Aktuell
      KQueue.Push( K )

Dieser Algorithmus benötigt eine Laufzeit von O(n), wobei n die Anzahl der Knoten ist. Oder anders ausgedrückt: eine Laufzeit von O(t^v), wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Der Speicherbedarf ist O(n) bzw. wiederum O(t^v).

In der Praxis wird häufig auch eine Variante dieses Algorithmus verwendet, wo die Tiefe iterativ erhöht wird, und in dieser Tiefe ein Tiefensuch-Algorithmus verwendet wird. Dies sieht als Algorithmus folgendermaßen aus:

Suche_Weg( Knoten Ziel )
  Tiefe = 1

  Solange Ziel nicht gefunden
    Tiefensuche( Ziel, Startknoten, Tiefe )
    Tiefe = Tiefe + 1

und die Tiefensuche wiederum sehr ähnlich (jedoch mit einer maximalen Tiefe):

Tiefensuche( Knoten Ziel, Knoten Aktuell, Integer Tiefe )
  Wenn Aktuell = Ziel
    Ziel gefunden

  Wenn Tiefe = 0
    Return

  Für K = jeder noch nicht besuchte Nachbarknoten von Aktuell
    Suche_Weg( Ziel, K, Tiefe - 1 )

Die iterative Tiefensuche hat zwar die maximalen Kosten von O(n^2) jedoch anders betrachtet wiederum die maximalen Kosten von O(t^v), wobei t wiederum die Tiefe des Zieles und v der (durchschnittliche) Verzweigungsgrad des Baumes ist. Anhand der Laufzeit bedeutet dies natürlich eine Verschlechterung, jedoch wird der Speicherbedarf für diesen Algorithmus von O(t^v) auf O(t) gesenkt. Bei großen Suchgraphen ist dies somit (zumindest in gewissen Fällen) ein Fortschritt.

Breitensuche mit Kosten

Bei der Breitensuche (welche den optimalen Weg suchen soll) sind die (Weg-)Kosten von einem Knoten zum anderen durchaus relevant. Es ist eine modifizierte Variante des Breitensuch-Algorithmus denkbar, wobei die Wegkosten iteriert werden. Die Wegkosten können jedoch eine sehr hohe Auflösung (beispielsweise 0,1 Meter wo die Knoten Kilometerweit entfernt sind) besitzten. Eine iterative Breitensuche wird somit verhältnismäßig schwer.

Die nicht iterative Breitensuche können wir jedoch verhältnismäßig einfach modifizieren, indem wir statt dem Queue einen Heap verwenden, welcher uns die minimalen Werte zurück gibt. Da ein Heap mit n Elementen zum Einfügen eines Elementes eine Laufzeit von O(log(n)) besitzt, besitzt dieser leicht abgewandelte Algorithmus eine maximale Laufzeit von O(n*log(n)).