Wann ist es sinnvoll, die Depth-First-Suche (DFS) gegenüber der Breadth-First-Suche (BFS) zu verwenden?

Question

Ich verstehe die Unterschiede zwischen DFS und BFS, aber ich möchte wissen, wann es sinnvoller ist, das eine dem anderen vorzuziehen.

Kann jemand Beispiele dafür nennen, wie DFS den BFS übertrumpfen würde und umgekehrt?

Answer 1

Das hängt stark von der Struktur des Suchbaums und der Anzahl und Lage der Lösungen (d. h. der gesuchten Elemente) ab.

• Wenn Sie wissen, dass eine Lösung nicht weit von der Wurzel des Baumes entfernt ist, kann eine BFS (breadth first search) besser sein.

• Wenn der Baum sehr tief ist und Lösungen selten sind, wird zuerst in der Tiefe gesucht. (DFS) extrem lange dauern, aber BFS könnte schneller sein.

• Wenn der Baum sehr breit ist, könnte ein BFS zu viel Speicherplatz benötigen, so dass es völlig unpraktisch sein kann.

• Wenn die Lösungen häufig sind, aber tief im Baum liegen, könnte BFS sein unpraktisch sein.

• Wenn der Suchbaum sehr tief ist, müssen Sie die Suchtiefe einschränken die Suchtiefe für die Deep First Search (DFS) ohnehin einschränken (zum Beispiel mit iterativer Vertiefung).

Dies sind jedoch nur Faustregeln; wahrscheinlich müssen Sie selbst experimentieren.

Ich denke, in der Praxis werden Sie diese Algorithmen in ihrer reinen Form ohnehin nicht verwenden. Es könnte Heuristiken geben, die dabei helfen, vielversprechende Teile des Suchraums zuerst zu erkunden, oder Sie könnten Ihren Suchalgorithmus modifizieren wollen, um ihn effizient parallelisieren zu können.

Answer 2

Deep-first-Suche

Die Tiefensuche wird häufig in Simulationen von Spielen (und spielähnlichen Situationen in der realen Welt) eingesetzt. In einem typischen Spiel kann man eine von mehreren möglichen Aktionen wählen. Jede Wahl führt zu weiteren Wahlmöglichkeiten, die wiederum zu weiteren Wahlmöglichkeiten führen, und so weiter zu einem immer größer werdenden baumförmigen Graphen von Möglichkeiten.

Bei Spielen wie Schach oder Tic-Tac-Toe zum Beispiel kann man sich bei der Entscheidung, welchen Zug man machen soll, mental einen Zug vorstellen, dann die möglichen Antworten des Gegners, dann die eigenen Antworten und so weiter. Sie können entscheiden, was zu tun ist, indem Sie sehen, welcher Zug zum besten Ergebnis führt.

Nur einige Wege in einem Spielbaum führen zum Sieg. Einige führen zu einem Sieg Ihres Gegners. Wenn Sie ein solches Ende erreichen, müssen Sie zu einem früheren Knotenpunkt zurückgehen und einen anderen Weg versuchen. Auf diese Weise erkunden Sie den Baum, bis Sie einen Weg mit einem erfolgreichen Ende finden. Dann machen Sie den ersten Zug entlang dieses Weges.

---

Breitensuche (Breadth-first)

Die Breadth-First-Suche hat eine interessante Eigenschaft: Sie findet zuerst alle Punkte, die eine Kante vom Ausgangspunkt entfernt sind, dann alle Punkte, die zwei Kanten entfernt sind, und so weiter. Dies ist nützlich, wenn man versucht, den kürzesten Weg vom Startpunkt zu einem bestimmten Punkt zu finden. Sie starten ein BFS, und wenn Sie den angegebenen Scheitelpunkt finden, wissen Sie, dass der Pfad, den Sie bisher verfolgt haben, der kürzeste Pfad zu diesem Knoten ist. Wenn es einen kürzeren Weg gäbe, hätte das BFS ihn bereits gefunden.

Die Breadth-First-Suche kann zum Auffinden von Nachbarknoten in Peer-to-Peer-Netzwerken wie BitTorrent, GPS-Systemen zum Auffinden von Orten in der Nähe, sozialen Netzwerken zum Auffinden von Personen in der angegebenen Entfernung und Ähnlichem verwendet werden.

Answer 3

Nette Erläuterung von http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Ein Beispiel für BFS

Hier ist ein Beispiel dafür, wie ein BFS aussehen könnte. Dies ist so etwas wie ein Level Order Tree Traversal, bei dem wir QUEUE mit einem ITERATIVEN Ansatz verwenden werden (RECURSION wird meistens mit DFS enden). Die Zahlen stellen die Reihenfolge dar, in der auf die Knoten in einem BFS zugegriffen wird:

Bei einer Tiefensuche beginnt man an der Wurzel und folgt einem der Zweige des Baums so weit wie möglich, bis man entweder den gesuchten Knoten gefunden hat oder auf einen Blattknoten (einen Knoten ohne Kinder) stößt. Wenn Sie auf einen Blattknoten stoßen, setzen Sie die Suche beim nächstgelegenen Vorfahren mit unerforschten Kindern fort.

Ein Beispiel für DFS

Hier ist ein Beispiel dafür, wie ein DFS aussehen könnte. Ich denke, dass das Post-Order-Traversal im Binärbaum mit der Arbeit auf der Blattebene beginnen wird. Die Zahlen stellen die Reihenfolge dar, in der auf die Knoten in einem DFS zugegriffen wird:

Unterschiede zwischen DFS und BFS

Vergleicht man BFS und DFS, so liegt der große Vorteil von DFS darin, dass es einen viel geringeren Speicherbedarf hat als BFS, da es nicht notwendig ist, alle Kindzeiger auf jeder Ebene zu speichern. Je nach den Daten und dem, wonach Sie suchen, kann entweder DFS oder BFS von Vorteil sein.

Wenn man beispielsweise in einem Familienstammbaum nach einer Person sucht, die noch am Leben ist, kann man davon ausgehen, dass sich diese Person am unteren Ende des Stammbaums befindet. Das bedeutet, dass ein BFS sehr lange brauchen würde, um diese letzte Ebene zu erreichen. Ein DFS hingegen würde das Ziel schneller finden. Würde man jedoch nach einem Familienmitglied suchen, das vor sehr langer Zeit verstorben ist, dann wäre diese Person näher an der Spitze des Baumes. Dann wäre ein BFS in der Regel schneller als ein DFS. Die Vorteile der beiden Verfahren hängen also von den Daten und der Art der Suche ab.

Ein weiteres Beispiel ist Facebook; Vorschlag für Freunde von Freunden. Wir brauchen unmittelbare Freunde für Vorschläge, bei denen wir BFS verwenden können. Um den kürzesten Weg zu finden oder den Zyklus zu erkennen (mit Rekursion), können wir DFS verwenden.

Answer 4

Breadth First Search ist im Allgemeinen der beste Ansatz, wenn die Tiefe des Baums variieren kann und Sie nur einen Teil des Baums nach einer Lösung durchsuchen müssen. Zum Beispiel ist die Suche nach dem kürzesten Weg von einem Startwert zu einem Endwert ein gutes Beispiel für die Verwendung von BFS.

Die Suche in der Tiefe wird üblicherweise verwendet, wenn Sie den gesamten Baum durchsuchen müssen. Sie ist einfacher zu implementieren (mit Rekursion) als BFS und erfordert weniger Status: Während bei BFS die gesamte "Grenze" gespeichert werden muss, muss bei DFS nur die Liste der Elternknoten des aktuellen Elements gespeichert werden.

Answer 5

DFS ist platzsparender als BFS, kann aber unnötig in die Tiefe gehen.

Ihre Namen sind aufschlussreich: Wenn es eine große Breite (d. h. einen großen Verzweigungsfaktor), aber eine sehr begrenzte Tiefe (z. B. eine begrenzte Anzahl von "Zügen") gibt, dann kann DFS dem BFS vorzuziehen sein.

---

Über IDDFS

Es sollte erwähnt werden, dass es eine weniger bekannte Variante gibt, die die Raumeffizienz von DFS, aber (kumulativ) die Level-Order-Visitation von BFS kombiniert, nämlich das iterative Vertiefung der Tiefensuche (depth-first search) . Dieser Algorithmus durchläuft einige Knoten, trägt aber nur einen konstanten Faktor der asymptotischen Differenz bei.