Breitensuche

Aus Byte-Welt Wiki
Version vom 14. Mai 2007, 10:02 Uhr von EagleEye (Diskussion | Beiträge) (Ablauf)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springenZur Suche springen

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:

  1. sie ist vollständig
  2. sie ist optimal
  3. 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

  1. hoher Rechen und Speicherbedarf bei großen Bäumen