Ich verstehe die Unterschiede zwischen DFS und BFS, aber ich bin daran interessiert zu wissen, wann es praktischer ist, das eine gegenüber dem anderen zu verwenden?
Kann jemand Beispiele nennen, in denen DFS BFS übertrumpfen würde und umgekehrt?
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 Baums entfernt ist, ist eine erste Suche nach Breite (BFS) besser sein.
Wenn der Baum sehr tief ist und die Lösungen selten sind, kann die Suche in der Tiefe zuerst (DFS) extrem viel Zeit in Anspruch nehmen, aber BFS könnte schneller sein.
Wenn der Baum sehr breit ist, könnte 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 unpraktisch sein.
Wenn der Suchbaum sehr tief ist, müssen Sie die Suchtiefe einschränken (DFS) die Suchtiefe ohnehin einschränken (zum Beispiel durch iterativer Vertiefung).
Dies sind jedoch nur Faustregeln; Sie werden wahrscheinlich experimentieren müssen.
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.
Depth First Search wird üblicherweise verwendet, wenn der gesamte Baum durchsucht werden muss. Sie ist einfacher zu implementieren (durch Rekursion) als BFS und erfordert weniger Speicherplatz: Während bei BFS die gesamte Grenze gespeichert werden muss, muss bei DFS nur die Liste der Elternknoten des aktuellen Elements gespeichert werden.
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.
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 die iterative deepening depth-first search. Dieser Algorithmus besucht einige Knoten erneut, trägt aber nur einen konstanten Faktor der asymptotischen Differenz bei.