Tiefensuche

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Tiefensuche (englisch: depth-first search DFS) ist ein Fachbegriff der Informatik welcher ein Verfahren zum Durchsuchen bzw. der Knoten und Blätter einer baumartigen Datenstruktur (siehe auch Wälder und Bäume in der Graphentheorie ) bezeichnet. Tiefensuche steht im Gegensatz zur Breitensuche (englisch: breadth-first search BFS) wobei letztere im Allgemeinen speicheraufwändiger Dafür terminiert die Tiefensuche nicht falls mindestens Pfad des Baumes unendliche Länge hat.

Reihenfolge im Beispielbaum

Man startet an der Wurzel und so weit wie möglich entlang der bestehenden in die Tiefe ehe man zurückgeht (englisch: backtracking ) und dann in bislang unbesuchte Teilbäumen

Formell betrachtet ist Tiefensuche eine uninformierte Suche die voranschreitet durch expandieren des auftretenden Kind-Knotens des Suchbaumes und so tiefer tiefer geht bis sie einen Zielzustand gefunden oder einen Knoten der keine Kinder hat. geht die Suche zurück um von einem gelegenen Knoten wieder abzusteigen.

Algorithmisch betrachtet werden alle gerade expandierten vorne in die Such- Warteschlange zur weiteren Expansion gestellt.

Tiefensuche ist vollständig: wenn der Baum ist wird eine Lösung gefunden falls sie
Tiefensuche ist optimal falls der Baum ist und alle Pfadkosten nicht-negativ sind

Bücher zum Thema Tiefensuche

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Tiefensuche.html">Tiefensuche </a>