Tiefe-First-Suche

Tiefe-First-Suche
Order in which the nodes get expanded
Reihenfolge, in der die Knoten besucht werden
Klasse Suchalgorithmus
Datenstruktur Graph
Schlimmsten Fall Leistung Für explizite Diagramme ohne Wiederholung, Für implizite Grafiken mit Verzweigungsfaktor b in der Tiefe gesucht d
Schlimmsten Fall Raumkomplexität Wenn die gesamte Grafik ohne Wiederholung durchquert wird, o (längste Pfadlänge durchsucht) = Für implizite Diagramme ohne Beseitigung doppelter Knoten

Tiefe-First-Suche (DFS) ist ein Algorithmus zum Überqueren oder Suchen Baum oder Graph Datenstrukturen. Der Algorithmus beginnt an der Wurzelknoten (Auswählen eines beliebigen Knotens als Stammknoten im Fall eines Diagramms) und erforscht vor dem Rückverfolgung so weit wie möglich entlang jedes Zweigs.

Eine Version der Tiefe-First-Suche wurde im 19. Jahrhundert vom französischen Mathematiker untersucht Charles Pierre Trémaux[1] als Strategie für Labyrinthe Labyrinthe.[2][3]

Eigenschaften

Das Zeit und Platz Die Analyse von DFS unterscheidet sich je nach Anwendungsbereich. In theoretischer Informatik wird DFS normalerweise verwendet, um ein ganzes Diagramm zu durchqueren und Zeit in Anspruch zu ,[4] wo ist die Anzahl von Eckpunkte und die Anzahl der Kanten. Dies ist linear in der Größe des Diagramms. In diesen Anwendungen nutzt es auch Platz im schlimmsten Fall zum Speichern der Stapel von Scheitelpunkten auf dem aktuellen Suchpfad sowie dem Satz bereits besuchter Scheitelpunkte. Somit sind in dieser Einstellung die Zeit- und Raumgrenzen dieselben wie für Breite-First-Suche und die Wahl dieser beiden zu verwendenden Algorithmen hängt weniger von ihrer Komplexität und mehr von den verschiedenen Eigenschaften der Scheitelpunkte ab, die die beiden Algorithmen produzieren.

Für Anwendungen von DFS in Bezug auf bestimmte Domänen, z. B. die Suche nach Lösungen in künstliche Intelligenz oder Web-Crawling, das zu überqueren von der Grafik ist oft entweder zu groß, um sie vollständig oder unendlich zu besuchen (DFS kann darunter leiden Nicht-Termination). In solchen Fällen wird die Suche nur an a durchgeführt Begrenzte Tiefe; Aufgrund begrenzter Ressourcen wie Speicher- oder Festplattenraum verwendet man in der Regel keine Datenstrukturen, um den Satz aller zuvor besuchten Scheitelpunkte zu verfolgen. Wenn die Suche in einer begrenzten Tiefe durchgeführt wird, ist die Zeit in Bezug auf die Anzahl der erweiterten Eckpunkte und Kanten immer noch linear (obwohl diese Zahl nicht mit der Größe des gesamten Diagramms übereinstimmt, da einige Scheitelpunkte mehr als einmal durchsucht werden können Nicht überhaupt nicht), aber die Raumkomplexität dieser Variante von DFS ist nur proportional zur Tiefengrenze und infolgedessen viel kleiner als der Raum, der für die Suche nach der Suche nach Breiten-First-Suche in der gleichen Tiefe benötigt wird. Für solche Anwendungen eignet sich DFS auch viel besser für Heuristik Methoden zur Auswahl eines wahrscheinlichen Zweigs. Wenn eine angemessene Tiefengrenze a priori nicht bekannt ist, iterative Vertiefung der Tiefe-First-Suche Wendet DFS wiederholt mit einer Abfolge von zunehmenden Grenzen an. Im Analysemodus der künstlichen Intelligenz mit a Verzweigungsfaktor Mehr als eins erhöht die iterative Vertiefung die Laufzeit nur um einen konstanten Faktor über den Fall, in dem die korrekte Tiefengrenze aufgrund des geometrischen Wachstums der Anzahl der Knoten pro Ebene bekannt ist.

DFs können auch verwendet werden, um a zu sammeln Probe von Graphknoten. Unvollständige DFs, ähnlich wie unvollständig BFS, ist voreingenommen auf Knoten von Hoch Grad.

Beispiel

Animiertes Beispiel für eine Tiefe-First-Suche

Für die folgende Grafik:

An undirected graph with edges AB, BD, BF, FE, AC, CG, AE

Eine Tiefensuche, die am Knoten A beginnt, unter der Annahme, dass die linken Kanten im gezeigten Diagramm vor rechten Kanten ausgewählt werden, und die Suche an die Suche zuvor besuchte Knoten und nicht wiederholt (da dies ein kleines Diagramm ist), wird besuchen Die Knoten in der folgenden Reihenfolge: A, B, D, F, E, C, G. Die Kanten durchquerten in diesem Suchformular a Trémaux Baum, eine Struktur mit wichtigen Anwendungen in Graphentheorie. Die gleiche Suche durchzuführen, ohne sich zuvor besuchte Knoten zu erinnern F, e Zyklus und nie C oder G.

Iterative Vertiefung ist eine Technik, um diese unendliche Schleife zu vermeiden, und würde alle Knoten erreichen.

Ausgabe einer Tiefe-First-Suche

Die vier Arten von Kanten, die durch einen Spannungsbaum definiert sind

Das Ergebnis einer Tiefe-First-Suche eines Diagramms kann bequem in Bezug auf a beschrieben werden Spannungsbaum der während der Suche erreichten Eckpunkte. Basierend auf diesem Spanning -Baum können die Kanten des ursprünglichen Diagramms in drei Klassen unterteilt werden: Vorwärtskanten, die von einem Knoten des Baumes zu einem seiner Nachkommen zeigen, Hinterkanten, die von einem Knoten zu einem seiner Vorfahren zeigen, und Kanten überqueren, was auch nicht tun. Manchmal Baumkanten, Kanten, die zum Spanning -Baum selbst gehören, werden getrennt von Vorwärtskanten klassifiziert. Wenn die Originalgrafik ungerichtet ist, sind alle seine Kanten Baumkanten oder hintere Kanten.

Scheitelpunktbestellungen

Es ist auch möglich, die Tiefensuche zu verwenden, um die Scheitelpunkte eines Diagramms oder Baums linear zu bestellen. Es gibt vier mögliche Möglichkeiten, dies zu tun:

  • A Vorbestellung ist eine Liste der Eckpunkte in der Reihenfolge, die sie zum ersten Mal vom Tiefen-ersten-Such-Algorithmus besucht haben. Dies ist eine kompakte und natürliche Methode, um den Fortschritt der Suche zu beschreiben, wie bereits in diesem Artikel. Eine Vorbestellung eines Ausdrucksbaum ist der Ausdruck in Polnische Notation.
  • A Veröffentlichung ist eine Liste der Eckpunkte in der Reihenfolge, die sie waren letzte vom Algorithmus besucht. Eine Veröffentlichung eines Ausdrucksbaums ist der Ausdruck in Polnische Notation umgekehrt.
  • A Reverse Vorbestellung ist das Gegenteil einer Vorbestellung, d. H. Eine Liste der Eckpunkte in der anderen Reihenfolge ihres ersten Besuchs. Reverse Vorbestellung ist nicht dasselbe wie die Veröffentlichung.
  • A Reverse -Postordering ist das Gegenteil eines Postorders, d. H. Eine Liste der Eckpunkte in der entgegengesetzten Reihenfolge ihres letzten Besuchs. Reverse -Postordering ist nicht mit der Vorbestellung gleich.

Zum Binärbäume Es gibt zusätzlich In-Ordering und Rückwärtsbeschreibung.

Wenn Sie beispielsweise den angegebenen Diagramm unten am Knoten A durchsuchen, ist die Abfolge der Traverals entweder A B D B A C A oder A C D C A B A (die Entscheidung, zuerst B oder C von A zu besuchen, ist bis zum Algorithmus). Beachten Sie, dass wiederholte Besuche in Form der Rückverfolgung zu einem Knoten, um zu überprüfen, ob es noch nicht besuchte Nachbarn hat, hier enthalten ist (auch wenn festgestellt wird, dass es keine hat). Somit sind die möglichen Vorbestellungen A B D C und A C D B, während die möglichen Veröffentlichungen d b c a und d c b a sind und die möglichen Rückwärtsbeschreibungen A C B D und A B C D sind

A directed graph with edges AB, BD, AC, CD

Reverse -Postordering erzeugt a Topologische Sortierung von jedem Regie acyclische Graphen. Diese Bestellung ist auch nützlich in Kontrollstrahlanalyse da es oft eine natürliche Linearisierung der Kontrollströme darstellt. Das obige Diagramm kann den Kontrollfluss im folgenden Codefragment darstellen, und es ist natürlich, diesen Code in der Reihenfolge A B C D oder A C B D zu berücksichtigen, aber nicht natürlich, um die Reihenfolge A B D C oder A C D B. zu verwenden

wenn (A) dann { B } anders { C }D

Pseudocode

Eingang:Ausgabe: Eine rekursive Implementierung von DFS:[5] 

Verfahren DFS (G, v) ist     Etikett v wie entdeckt für alle gerichtete Kanten von v zu W das sind in G.adjazentiert (v) tun  wenn Scheitel w ist nicht wie entdeckt gekennzeichnet dann             rekursiv dfs (G, w))

Eine nicht rekursive Implementierung von DFS mit der Komplexität des Weltraumraums , mit der Möglichkeit von doppelten Eckpunkten auf dem Stapel:[6] 

Verfahren Dfs_iterative (G, v) ist     Lassen S Sei ein Stapel S.drücken(v)) während S ist nicht leer tun  v = S.Pop() wenn v ist nicht wie entdeckt gekennzeichnet dann             Etikett v wie entdeckt für alle Kanten von v zu w in G.adjazentiert (v) tun   S.drücken(w))
An undirected graph with edges AB, BD, BF, FE, AC, CG, AE

Diese beiden Variationen von DFS besuchen die Nachbarn jedes Scheitelpunkts in der entgegengesetzten Reihenfolge voneinander: der erste Nachbar von v Besucht von der rekursiven Variation ist die erste in der Liste der benachbarten Kanten, während in der iterativen Variation der erste besuchte Nachbarn der letzte in der Liste der benachbarten Kanten ist. Die rekursive Implementierung besucht die Knoten aus dem Beispieldiagramm in der folgenden Reihenfolge: A, B, D, F, E, C, G. Die nicht rekursive Implementierung besucht die Knoten als: a, e, f, b, d , C, G.

Die nicht rezisive Implementierung ist ähnlich wie Breite-First-Suche unterscheidet sich aber auf zwei Arten davon:

  1. Es verwendet einen Stapel anstelle einer Warteschlange, und
  2. Es verzögert die Überprüfung, ob ein Scheitelpunkt entdeckt wurde, bis der Scheitelpunkt aus dem Stapel gekommen ist, anstatt diesen Scheck vor dem Hinzufügen des Scheitelpunkts zu machen.

Wenn G ist ein BaumWenn Sie die Warteschlange des Suchalgorithmus für Breite durch einen Stapel ersetzen, erhalten Sie einen Tiefen-First-Suchalgorithmus. Für allgemeine Diagramme würde das Ersetzen des Stapels der iterativen Tiefen-First-Suchimplementierung durch eine Warteschlange auch einen Breadth-First-Suchalgorithmus erzeugen, wenn auch ein etwas nicht standardmäßiges.[7]

Eine weitere mögliche Implementierung der iterativen Tiefe-First-Suche verwendet einen Stapel von Iteratoren der Liste der Nachbarn eines Knotens anstelle eines Stapels Knoten. Dies liefert den gleichen Traversal wie rekursive DFs.[8] 

Verfahren Dfs_iterative (G, v) ist     Lassen S Sei ein Stapel S.push (Iterator von G.adjazentiert (v)) während S ist nicht leer tun  wenn S.peek (). hasNext () dann  w = S.peek (). Weiter () wenn w ist nicht wie entdeckt gekennzeichnet dann                 Etikett w wie entdeckt S.push (Iterator von G.adjazentiert (w)) anders  S.Pop()

Anwendungen

Randomisierter Algorithmus ähnlich wie bei der Erzeugung eines Labyrinths.

Zu den Algorithmen, die die Tiefe-First-Suche als Baustein verwenden, gehören:

Komplexität

Das Rechenkomplexität von DFS wurde von untersucht von John Reif. Genauer gesagt bei einer Grafik , Lassen Seien Sie die Bestellung, die durch den Standard -rekursiven DFS -Algorithmus berechnet wird. Diese Bestellung wird als Lexikographie-Tiefenanordnung bezeichnet. John Reif berücksichtigte die Komplexität der Berechnung der lexikografischen Tiefenanordnung bei der Suchreihenfolge bei einem Diagramm und einer Quelle. EIN Entscheidungsversion des Problems (Test, ob ein Scheitelpunkt u tritt vor einem Scheitelpunkt vor v in dieser Reihenfolge) ist P-Komplett,[11] was bedeutet, dass es "ein Albtraum für ist Parallelverarbeitung".[12]: 189

Eine Tiefe-First-Suchreihenfolge (nicht unbedingt die lexikographische) kann durch einen randomisierten parallelen Algorithmus in der Komplexitätsklasse berechnet werden RNC.[13] Ab 1997 war es nicht bekannt NC.[14]

Siehe auch

Anmerkungen

  1. ^ Charles Pierre Trémaux (1859–1882) École Polytechnique von Paris (x: 1876), französischer Ingenieur des Telegraphen
    in der Öffentlichkeit, 2. Dezember 2010-von Professor Jean Pelletier-Thibert in Académie de Macon (Burgundy-Frankreich)-(Zusammenfassung in The Annals Academic, März 2011-veröffentlicht- ISSN 0980-6032)
  2. ^ Sogar Shimon (2011), Graphalgorithmen (2. Aufl.), Cambridge University Press, S. 46–48, ISBN 978-0-521-73653-4.
  3. ^ Sedgewick, Robert (2002), Algorithmen in C ++: Graphalgorithmen (3. Aufl.), Pearson Education, ISBN 978-0-201-36118-6.
  4. ^ Cormen, Thomas H., Charles E. Leiser und Ronald L. Rivest. S.606
  5. ^ Goodrich und Tamassia; Cormen, Leiserson, Rivest und Stein
  6. ^ Seite 93, Algorithmus Design, Kleinberg und Tardos
  7. ^ "Stack-basierte Graphtraversal ≠ Tiefe erste Suche". 11011110.github.io. Abgerufen 2020-06-10.
  8. ^ Sedgewick, Robert (2010). Algorithmen in Java. Addison-Wesley. ISBN 978-0-201-36121-6. OCLC 837386973.
  9. ^ Hopcroft, John; Tarjan, Robert E. (1974), "Effiziente Planaritätstests" (PDF), Journal of the Association for Computing Machinery, 21 (4): 549–568, doi:10.1145/321850.321852, HDL:1813/6011, S2CID 6279825.
  10. ^ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémamux Trees and Planarity", Internationales Journal of Foundations of Computer Science, 17 (5): 1017–1030, Arxiv:Math/0610935, Bibcode:2006math ..... 10935d, doi:10.1142/s0129054106004248, S2CID 40107560.
  11. ^ Reif, John H. (1985). "Die Tiefensuche ist von Natur aus sequentiell". Informationsverarbeitungsbriefe. 20 (5): 229–234. doi:10.1016/0020-0190 (85) 90024-9.
  12. ^ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithmen und Datenstrukturen: Die grundlegende Toolbox (PDF). Springer.
  13. ^ Aggarwal, a.; Anderson, R. J. (1988), "A Random NC Algorithmus für die erste Suche der Tiefe ", Combinatorica, 8 (1): 1–12, doi:10.1007/bf02122548, HERR 0951989, S2CID 29440871.
  14. ^ Karger, David R.; Motwani, Rajeev (1997), "und NC Algorithmus für minimale Schnitte ", Siam Journal über Computing, 26 (1): 255–272, Citeseerx 10.1.1.33.1701, doi:10.1137/s0097539794273083, HERR 1431256.

Verweise

Externe Links