BFSbasiert

BFSbasiert bezeichnet in der Informatik ein Verfahren, dessen Zentralprinzip auf der Breitensuche (Breadth-First Search, BFS) beruht. Es handelt sich um einen Oberbegriff für Algorithmen, die den Zustandsraum oder Graphen schichtweise erkunden, indem sie Knoten in der Reihenfolge ihrer Distanz zum Startknoten expandieren.

Funktionsweise: BFS nutzt eine Warteschlange, beginnt beim Startknoten, fügt unbesuchte Nachbarn hinzu und markiert sie. Die Exploration erfolgt Ebene für Ebene, wodurch der kürzeste Weg in ungewichteten Graphen garantiert ist. BFS-basierte Methoden arbeiten oft deterministisch und liefern reproduzierbare Ergebnisse, solange der Graph feststeht.

Eigenschaften: BFS-basierte Ansätze sind vollständig in endlichen Graphen; sie liefern oft optimale Lösungen für ungewichtete Kanten. Der Speicherbedarf entspricht typischerweise der Größe der aktuellen Frontier plus bereits besuchter Knoten, im Worst-Case O(V). Die Laufzeit ist O(V+E), wobei V die Knoten und E die Kanten des Graphen bezeichnet.

Anwendungen: Typische Einsatzgebiete sind Wegsuche in Grids oder Netzwerken, Puzzle- oder Routenlösungen, Level- oder Zustandsanalyse in Spiele- und KI-Anwendungen sowie Grundlegungen der Graphentraversal-Analyse.

Varianten: Zu den Varianten gehören bidirektionale BFS, die von Start- und Zielknoten gleichzeitig ausgehen, sowie BFS-Varianten auf impliziten Graphen oder in Kombination mit zusätzlichen Heuristiken, die Distanzschätzungen berücksichtigen.

Vor- und Nachteile: Vorteile sind Einfachheit, Zuverlässigkeit und die Garantie, ungewichtete kurze Pfade zu finden. Nachteile bestehen in potenziell hohem Speicherbedarf und eingeschränkter Eignung für gewichtete Graphen oder sehr große Graphen; dort kommen oft andere Suchstrategien wie A* oder Dijkstra zum Einsatz.

Siehe auch: Breadth-First Search, Graphentraversal, Suchalgorithmen.