Diagrammsuche: Breite zuerst vs. Tiefe zuerst

78

Wenn graphische Darstellungen der Suche gibt es zwei einfache Algorithmen: Breite erste und depth-first ( In der Regel erfolgt , indem all adjactent Graph Knoten zu einer Warteschlange hinzuzufügen (Breite-first) oder Stapel (depth-first)).

Gibt es Vorteile eines gegenüber dem anderen?

Die, an die ich denken konnte:

  • Wenn Sie erwarten, dass Ihre Daten ziemlich weit unten im Diagramm sind, kann es sein, dass Depth-First sie früher findet, da Sie sehr schnell in die tieferen Teile des Diagramms vordringen.
  • Wenn Sie dagegen davon ausgehen, dass Ihre Daten ziemlich weit oben im Diagramm sind, gibt width-first möglicherweise das Ergebnis früher wieder.

Gibt es etwas, das ich verpasst habe oder hängt es hauptsächlich von persönlichen Vorlieben ab?

malexmave
quelle

Antworten:

43

Ich möchte eine Antwort von Stack Overflow von hstoerr zitieren, die das Problem gut abdeckt:

Das hängt stark von der Struktur des Suchbaums sowie der Anzahl und dem Ort der Lösungen ab .
Wenn Sie wissen, dass eine Lösung nicht weit von der Wurzel des Baums entfernt ist, ist eine Breitensuche (BFS) möglicherweise besser. Wenn der Baum sehr tief ist und Lösungen selten sind, kann die DFS-Funktion (Depth First Search) für immer verwendet werden, BFS ist jedoch möglicherweise schneller. Wenn der Baum sehr breit ist, benötigt ein BFS möglicherweise zu viel Speicher, sodass dies möglicherweise völlig unpraktisch ist. Wenn häufig Lösungen gefunden werden, diese sich jedoch tief im Baum befinden, kann BFS unpraktisch sein. Wenn der Suchbaum sehr tief ist, müssen Sie die Suchtiefe für die erste Tiefensuche (DFS) ohnehin einschränken (z. B. mit iterativer Vertiefung).

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

Rafał Dowgird bemerkt auch:

Einige Algorithmen hängen von bestimmten Eigenschaften von DFS (oder BFS) ab, um zu funktionieren. Beispielsweise nutzt der Hopcroft- und Tarjan-Algorithmus zum Auffinden von 2 verbundenen Komponenten die Tatsache, dass sich jeder bereits besuchte Knoten, auf den DFS stößt, auf dem Pfad vom Stamm zum aktuell untersuchten Knoten befindet.

Gigili
quelle
5
Ich kann nicht verstehen, warum diese Antwort 27 positive Stimmen hat und es ist genau die Verschmelzung von 2 anderen Antworten, die
Nr.
37

Ein Punkt, der in unserer Multicore-Welt wichtig ist: BFS lässt sich viel einfacher parallelisieren. Dies ist intuitiv sinnvoll (senden Sie Threads für jedes Kind aus) und kann auch so nachgewiesen werden. Wenn Sie also ein Szenario haben, in dem Sie die Parallelität nutzen können, ist BFS der richtige Weg.

Suresh
quelle
8
Wenn DFS in der angegebenen Einstellung ansonsten vorteilhaft ist, können Sie BFS anwenden, bis Sie genügend Threads erzeugt haben, und mit DFS fortfahren. Genauer gesagt, Sie können DFS ausführen und wann immer Sie absteigen und nicht genügend Threads vorhanden sind, einen für das nächste Geschwister erzeugen.
Raphael
Diese Antwort hat 20 positive Bewertungen nicht verdient. Die Frage bezieht sich auf die allgemeine Verwendung der beiden Algorithmen und nicht auf eine bestimmte Verwendung.
Nr.
31

(Ich habe dies zu einem Community-Wiki gemacht. Bitte fühle dich frei, es zu bearbeiten.)

Wenn

  • b ist der Verzweigungsfaktor
  • d ist die Tiefe, in der sich die Lösung befindet
  • d hh ist die Höhe des Baumes (also )dh

Dann

  • DFS benötigt Zeit und RaumO ( h )O(bh)O(h)
  • BFS benötigt Zeit und RaumO ( b d )O(bd)O(bd)
  • IDDFS benötigt Zeit und RaumO ( d )O(bd)O(d)

Gründe zu wählen

  • DFS
    • muss sowieso den ganzen Baum sehen
    • Sie wissen, , die Ebene der Antwortd
    • Es ist mir egal, ob die Antwort der Wurzel am nächsten kommt
  • BFS
    • Antwort ist nah an der Wurzel
    • Sie möchten die Antwort, die der Wurzel am nächsten ist
    • haben mehrere Kerne / Prozessoren
  • IDDFS
    • Sie möchten BFS, haben nicht genug Speicher, aber etwas langsamer ist akzeptabel

IDDFS = iterative vertiefende Tiefensuche

rgrig
quelle
1
Dies ist eine hervorragende Antwort. Ich stelle jedoch fest, dass sich diese Antwort auf Bäume bezieht, während sich die Frage auf Diagramme bezieht. Ein Baum ist natürlich eine Grafik, und es mag sein, dass das Wort ersetzt werden kann ... aber wie wäre es mit hder "Höhe des Baumes". Bedeutet das direkt die "Höhe des Graphen"?
user2023370
Ein weiterer Grund für die Verwendung von IDDFS besteht darin, dass Sie nach jeder Iteration eine mögliche Antwort erhalten, je nachdem, wie Sie sie verwenden möchten (wenn Sie beispielsweise nach einem Maximum oder einem Minimum suchen). Dies bedeutet, dass Sie den Algorithmus vorzeitig beenden können, wenn Ihre Antwort "gut genug" ist, oder Sie können die Benutzereingabe beenden (wie eine Schach-Engine, die IDDFS verwendet, um eine optimale Lösung zu finden, aber von einem Spieler unterbrochen wird, der eine Figur bewegt).
jedd.ahyoung
Ein weiterer Punkt, der hinzugefügt werden muss, ist, dass das DFS den Stack verwendet, während das BFS die Warteschlange verwendet.
Karthik Balaguru
17

Ein Szenario (abgesehen vom Auffinden des kürzesten Pfades, der bereits erwähnt wurde), in dem Sie möglicherweise einen über den anderen wählen müssen, um ein korrektes Programm zu erhalten, wären unendliche Graphen:

Wenn wir zum Beispiel einen Baum betrachten, in dem jeder Knoten eine endliche Anzahl von untergeordneten Knoten hat, die Höhe des Baums jedoch unendlich ist, wird DFS möglicherweise nie den gesuchten Knoten finden - es wird nur das erste untergeordnete Knoten dieses Knotens besucht Wenn also das gesuchte Kind nicht das erste Kind seines Elternteils ist, wird es niemals dorthin gelangen. BFS wird es jedoch garantiert in endlicher Zeit finden.

Wenn wir einen Baum betrachten, in dem jeder Knoten eine unendliche Anzahl von untergeordneten Knoten hat, der Baum jedoch eine endliche Höhe hat, wird BFS möglicherweise nicht beendet. Es werden nur die untergeordneten Knoten des Stammknotens besucht. Wenn der gesuchte Knoten das untergeordnete Element eines anderen Knotens ist, wird er nicht erreicht. In diesem Fall wird DFS garantiert, um es in der endlichen Zeit zu finden.

sepp2k
quelle
7
Es ist bemerkenswert, dass beide nur Halbentscheidungsalgorithmen für unendliche Graphen liefern; Sie können nicht in endlicher Zeit entscheiden, dass ein Element nicht im Baum ist (offensichtlich). Wie für praktische Anwendungen beachten , dass (begrifflich) unendliche Datenstrukturen können definiert werden (siehe Abschnitt 3.4)!
Raphael
15

Die Breite zuerst und die Tiefe zuerst weisen mit Sicherheit dasselbe Worst-Case-Verhalten auf (der gewünschte Knoten ist der zuletzt gefundene). Ich vermute, dass dies auch im Normalfall der Fall ist, wenn Sie keine Informationen zu Ihren Diagrammen haben.

Ein netter Vorteil der Breitensuche ist, dass sie kürzeste Pfade (im Sinne der kleinsten Kanten) findet, die möglicherweise von Interesse sind oder nicht.

Wenn Ihr durchschnittlicher Knotenrang (Anzahl der Nachbarn) im Verhältnis zur Anzahl der Knoten hoch ist (dh der Graph ist dicht), hat die Breite zuerst große Warteschlangen, während die Tiefe zuerst kleine Stapel hat. In spärlichen Diagrammen ist die Situation umgekehrt. Wenn der Speicher ein begrenzender Faktor ist, muss die Form des Diagramms möglicherweise Ihre Wahl der Suchstrategie beeinflussen.

Raphael
quelle
Die Länge der Warteschlange in BFS und die Höhe des Stapels in DFS hängen stark von der Implementierung ab. Wenn Sie im Falle von dfs immer den gesamten Nachbarn auf dem Stapel erweitern, wächst dieser stark an, insbesondere wenn der Graph dicht ist. Wenn Sie nur eine Referenz angeben, die angibt, wo Sie fortfahren sollen, wenn dfs von der Rekursion zurückkehrt, wird viel Platz gespart.
uli
3

Alles oben Genannte ist korrekt, aber es ist bemerkenswert, dass BFS und DFS ihre eigenen Bäume erstellen, basierend auf der Reihenfolge, in der sie den Baum durchlaufen. Jeder dieser Bäume hat seine eigene Eigenschaft, die bei einigen Problemen nützlich sein kann.

Beispielsweise sind alle Kanten im Originaldiagramm, die sich nicht im BFS-Baum befinden, Kreuzkanten. Kanten, die zwischen zwei Zweigen des BFS-Baums liegen. Alle Kanten im Originaldiagramm, die sich nicht im DFS-Baum befinden, sind hintere Kanten. Kanten, die zwei Eckpunkte in einem Zweig des DFS-Baums verbinden. Solche Eigenschaften können bei Problemen wie Sonderfarben usw. hilfreich sein.

MMS
quelle
1

DFS- und BFS-Baum haben jeweils eigene Eigenschaften, mit denen Sie nützliche Informationen zum Diagramm erhalten. Zum Beispiel können Sie mit einem einzelnen DFS Folgendes tun:

  • Suchen von Brücken und Artikulationspunkten (für ungerichtete Grafiken)
  • Zykluserkennung
  • Suche nach stark verbundenen Komponenten (Tarjans Algorithmus)

Mit BFS können Sie die kürzesten Pfade zwischen dem Quellknoten und anderen Knoten im Diagramm finden.

Das Kapitel Graph Algorithms in CLRS fasst diese Eigenschaften von DFS und BFS sehr gut zusammen.

Prise
quelle
-2

Ich denke, es wäre interessant, beide so zu schreiben, dass Sie nur durch Umschalten einiger Codezeilen den einen oder anderen Algorithmus erhalten, sodass Sie feststellen, dass Ihr Dillem nicht so stark ist, wie es zunächst zu sein scheint .

Ich persönlich mag die Interpretation von BFS als Überschwemmung einer Landschaft: Die Gebiete mit geringer Höhe werden zuerst überschwemmt, und erst dann werden die Gebiete mit hoher Höhe folgen. Wenn Sie sich die Landschaftshöhen als Isolinien vorstellen, wie wir es in den Geografiebüchern sehen, ist es leicht zu sehen, dass BFS alle Bereiche unter derselben Isolinie gleichzeitig ausfüllt, genau wie dies bei der Physik der Fall wäre. Die Interpretation von Höhen als Entfernung oder skalierte Kosten liefert daher eine ziemlich intuitive Vorstellung des Algorithmus.

Vor diesem Hintergrund können Sie die Idee der Breitensuche leicht anpassen, um den minimalen Spannbaum, den kürzesten Pfad und viele andere Minimierungsalgorithmen zu finden.

Ich habe noch keine intuitive Interpretation von DFS gesehen (nur die Standardinterpretation über das Labyrinth, aber sie ist nicht so mächtig wie die BFS und das Fluten), daher scheint es für mich, dass BFS besser mit den oben beschriebenen physikalischen Phänomenen korreliert, während DFS korreliert besser mit Entscheidungen, die auf rationalen Systemen getroffen werden (dh Menschen oder Computer entscheiden, welche Schritte bei einem Schachspiel oder beim Verlassen eines Labyrinths unternommen werden).

Für mich liegt der Unterschied darin, welches Naturphänomen am besten zu ihrem Ausbreitungsmodell (Transversing) im wirklichen Leben passt.

user5193682
quelle
2
Willkommen auf der Seite! Allerdings sehe ich nicht wirklich, wie dies die Frage beantwortet. Es scheint Ihre allgemeinen Gefühle und Intuitionen in Bezug auf BFS und DFS zu sein, aber die Frage stellt sich nicht in Bezug auf Gefühle und Intuitionen, sondern in Bezug auf Vor- und Nachteile. Ihre Antwort scheint das überhaupt nicht anzusprechen.
David Richerby
Der Teil, der am meisten mit der Frage zusammenhängt, ist die Anpassung des Algorithmus, um minimale Spannweiten, kürzeste Wege usw. zu finden und zu sagen, dass einige natürliche Phänomene von BFS reproduzierbar sind, während Entscheidungsbäume von DFS
user5193682
1
Die Frage ist nicht, was mit BFS und DFS zusammenhängt. Es geht nicht darum, Bäume oder kürzeste Wege zu finden oder "natürliche Phänomene zu reproduzieren".
David Richerby
Es fragt nach Vorteilen. Wenn man ein physikalisches Phänomen modellieren kann, während es das andere nicht kann, ist dies ein Vorteil, wenn Sie dieses Phänomen modellieren müssen. Ich denke, Sie halten an den Standardkonzepten des Lehrbuchs für Algorithmen fest, wenn Sie das Wort "Vorteil" interpretieren, während ich es nicht bin
user5193682