WikiDer > Breitenorientierte Suche

Breadth-first search
Reihenfolge, in der die Knoten des Diagramms angezeigt werden.

Breitenorientierte Suche (BFS) ist ein Suchalgorithmus auf einen Anzahl das an der Wurzel (Startknoten) des Graphen beginnt und für jedes der Kinder prüft, ob es die Lösung ist, und diesen Vorgang dann für jedes dieser Kinder durchführt, bis die gewünschte Lösung gefunden ist. BFS ist eine Form von uninformierte Suche, da bei der Suche keine Informationen zum Suchproblem verwendet werden.

Eigenschaften

Der Algorithmus hat a Zeitkomplexität von O(bd), wobei b de Verzweigungsfaktor des Zählers und d ist der Tiefe des Grafen. Der Algorithmus hat auch a Raumkomplexität von O(bd). Diese Suchmethode ist vollständig: Wenn eine Lösung existiert, wird eine Breitensuche sie finden, aber wenn der Graph unendlich viele Knoten und keine Lösung enthält, wird der Algorithmus nicht terminieren.

Wenn jede Seite im Graphen die gleichen Kosten hat, ist der Algorithmus optimal: Er wird in der Lage sein, einen Weg von der Wurzel zur Lösung mit optimalen Kosten zu finden. Auf einem gewichteten Graphen gibt BFS möglicherweise keine optimale Lösung zurück, da der kürzeste Weg nicht mehr eine optimale Lösung bedeuten muss (die Kanten können hohe Kosten verursachen, während ein unentdeckter Knoten eine bessere Lösung sein kann).

Operation

BFS kann implementiert werden mit a FIFOWarteschlange. Im Pseudocode der Algorithmus funktioniert so:

  1. Addiere die Quadratwurzel der Zählung zur Warteschlange
  2. Wenn sich ein Knoten in der Warteschlange befindet, entfernen Sie ihn aus der Warteschlange und zeigen Sie den Knoten an:
    • Wenn dies eine Lösung ist: Stoppen Sie die Suche und geben Sie die Lösung an
    • Falls dies keine Lösung ist: Fügen Sie alle Kinder dieses Knotens am Ende der FIFO-Warteschlange hinzu
  3. Wenn die Warteschlange leer ist: Alle Knoten wurden angezeigt. Beenden Sie die Suche und geben Sie an, dass es keine Lösung gibt
  4. Fahren Sie mit Schritt 2 fort

Siehe auch

Siehe die Kategorie Breitenorientierte Suche von Wikimedia Commons für Mediendateien zu diesem Thema.