Breitensuche
Aus Byte-Welt Wiki
Die Breitensuche ist ein Suchverfahren um Bäume zu durchsuchen, welches vollständig und optimal ist. Es zählt zu den uninformierten Suchverfahren.
Ablauf
Es wird ein Startknoten ausgewählt und expandiert, anschließend wird nachgesehen ob das Ziel bei diesen Knoten ist. Sollte es nicht dabei sein werden alle diese Knoten expandiert und nachgesehen ob das Ziel in dieser neuen Ebene ist, wenn nicht wird dieser Schritt wiederholt.
Vorteil
Der Vorteil der Breitensuche ist:
- sie ist vollständig
- sie ist optimal
- einfach zu implementieren, es werden alle nicht geöffneten Koten in einer Liste abgespeichert, welche dann durchlaufen wird um die nächste Ebene zu erzeugen
Nachteil
- hoher Rechen und Speicherbedarf bei großen Bäumen