Breite-First-Suche

Breite-First-Suche
	Reihenfolge, in der die Knoten erweitert werden
Klasse	Suchalgorithmus
Datenstruktur	Graph
Schlimmsten Fall Leistung
Schlimmsten Fall Raumkomplexität

Animiertes Beispiel für eine Breadh-First-Suche. Schwarz: Erkundet, Gray: In der Warteschlange, um später erkundet zu werden

BFS auf Labyrinth-Lösungsalgorithmus

Oberer Teil von Tic-Tac-Toe Spielbaum

Breite-First-Suche (BFS) ist ein Algorithmus Für die Suche a Baum Datenstruktur für einen Knoten, der eine bestimmte Eigenschaft erfüllt. Es beginnt am Baumwurzel und erforscht alle Knoten in der Gegenwart Tiefe Bevor Sie zu den Knoten auf der nächsten Tiefenebene übergehen. Zusätzliches Speicher, normalerweise a Warteschlange, wird benötigt, um die Kinderknoten zu verfolgen, die angetroffen wurden, aber noch nicht erforscht wurden.

Zum Beispiel in a Schachendspiel a Schachmotor kann die bauen Spielbaum Aus der aktuellen Position durch Anwenden aller möglichen Bewegungen und verwenden Sie die Breite, um eine Gewinnposition für Weiß zu finden. Implizite Bäume (wie Spielbäume oder andere Bäume mit Problemlösungen) können von unendlicher Größe sein; Die Suche nach Breite, die zuerst ist garantiert einen Lösungsknoten findet^[1] Wenn man existiert.

Dagegen (schlicht) Tiefe-First-Suche, der den Knotenzweig so weit wie möglich untersucht, bevor Sie andere Knoten zurückverfolgen und erweitern.^[2] Kann sich in einem unendlichen Zweig verlieren und niemals zum Lösungsknoten schaffen. Iterative Vertiefung der Tiefe-First-Suche Vermeiden Sie den letzteren Nachteil zum Preis, die die obersten Teile des Baumes immer wieder zu erkunden. Andererseits verstehen sich beide Tiefen-First-Algorithmen ohne zusätzlichen Speicher.

Die Suche nach der Breite kann verallgemeinert werden auf Grafiken, wenn der Startknoten (manchmal als "Suchschlüssel" bezeichnet)^[3] wird ausdrücklich gegeben und Vorsichtsmaßnahmen gegen einen Scheitelpunkt zweimal getroffen.

BFS und seine Anwendung bei der Suche verbundene Komponenten von Grafiken wurden 1945 von erfunden Konrad Zuse, in seinem (abgelehnten) Ph.D. These auf der Plankalkül Programmiersprache, aber dies wurde erst 1972 veröffentlicht.^[4] Es wurde 1959 von neu erfunden Edward F. Moore, der es benutzte, um den kürzesten Weg aus einem Labyrinth zu finden,^[5]^[6] und später von C. Y. Lee in a entwickelt Drahtrouting Algorithmus (veröffentlicht 1961).^[7]

Pseudocode

Eingang: Ein Graph $G$ und ein Scheitelpunkt beginnen $Wurzel$ von $G$

Ausgabe: Zielzustand. Das Elternteil Verfolgt verfolgt den kürzesten Weg zurück zu $Wurzel$ ^[8]

 1 Verfahren BFS (G, Wurzel) ist  2 Lass Q Seien Sie ein Warteschlange 3 -Etikett Wurzel wie erforscht 4 Q.enqueue (Wurzel) 5 während Q ist nicht leer tun  6 v: = Q.dequeue () 7 wenn v ist das Ziel dann  8 Rückkehr v  9 für alle Kanten von v zu w in G.adjazentiert (v) tun 10 wenn w ist nicht als erkundet gekennzeichnet dann 11 Etikett w wie erforscht 12 Q.enqueue (w))

Mehr Details

Diese nicht rezisive Implementierung ähnelt der nicht rekursiven Implementierung von Tiefe-First-Sucheunterscheidet sich aber auf zwei Arten davon:

Es verwendet a Warteschlange (Zuerst zuerst nach außen) anstelle von a Stapel und
Es prüft, ob ein Scheitelpunkt untersucht wurde, bevor der Scheitelpunkt untersucht wurde, anstatt diesen Scheck zu verzögern, bis der Scheitelpunkt aus der Warteschlange gestaltet ist.

Wenn $G$ ist ein BaumDas Ersetzen der Warteschlange dieses Suchalgorithmus mit einem Stapel ersetzt 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.^[9]

Das Q Die Warteschlange enthält die Grenze entlang dessen der Algorithmus derzeit sucht.

Knoten können als untersucht werden, indem sie je nach Implementierung in einem Satz oder durch ein Attribut für jeden Knoten gespeichert werden.

Beachten Sie, dass das Wort Knoten ist normalerweise mit dem Wort austauschbar Scheitel.

Das Elternteil Das Attribut jedes Knotens ist nützlich für den Zugriff auf die Knoten auf einem kürzesten Pfad, beispielsweise durch Rückverfolgung vom Zielknoten zum Startknoten, sobald das BFS ausgeführt wurde und die Vorgängerknoten eingestellt wurden.

Breite zuerst die Suche erzeugt eine sogenannte Breite erster Baum. Sie können sehen, wie a Breite erster Baum schaut im folgenden Beispiel aus.

Beispiel

Das Folgende ist ein Beispiel für den Breadh-First-Baum, der durch Laufen eines BFS auf Deutsch Städte von Frankfurt:

Eine Beispielkarte von Süddeutschland mit einigen Verbindungen zwischen Städten

Der BREATH-First-Baum, der beim Ausführen von BFS auf der angegebenen Karte erhalten wird und in der angegebenen Karte beginnt Frankfurt

Analyse

Zeit und Raumkomplexität

Das Zeitkomplexität kann ausgedrückt werden als ${\ displayStyle o (| v |+| e |)}$ Da jeder Scheitelpunkt und jeder Rand im schlimmsten Fall untersucht werden. ${\ displayStyle | v |}$ ist die Anzahl der Eckpunkte und ${\ displayStyle | e |}$ ist die Anzahl der Kanten in der Grafik. Beachten Sie, dass ${\ displayStyle o (| e |)}$ kann zwischen variieren ${\ displayStyle o (1)}$ und ${\ displayStyle o (| v |^{2})}$ , abhängig davon, wie spärlich das Eingangsdiagramm ist.^[10]

Wenn die Anzahl der Scheitelpunkte im Diagramm im Voraus bekannt ist und zusätzliche Datenstrukturen verwendet werden, um zu bestimmen, welche Scheitelpunkte bereits zur Warteschlange hinzugefügt wurden, ist die Raumkomplexität kann ausgedrückt werden als ${\ displayStyle o (| v |)}$ , wo ${\ displayStyle | v |}$ ist die Anzahl der Eckpunkte. Dies gilt zusätzlich zu dem für das Diagramm selbst erforderlichen Raum, der je nach dem variieren kann Grafikdarstellung Wird durch eine Implementierung des Algorithmus verwendet.

Wenn Sie mit Grafiken arbeiten, die zu groß sind, um explizit (oder unendlich) zu speichern $d$ BFS nimmt vom Startknoten (gemessen in der Anzahl der Kantenquellen) und nimmt BFS an $O (b d + 1)$ Zeit und Erinnerung, wo $b$ ist der "Verzweigungsfaktor"des Diagramms (der durchschnittliche Außengrad).^[11]^{: 81}

Vollständigkeit

Bei der Analyse von Algorithmen wird angenommen Adjazenzliste, Adjazenzmatrix, oder eine ähnliche Darstellung. Bei der Anwendung von Graph -Traversal -Methoden in jedoch künstliche Intelligenz Die Eingabe kann ein sein implizite Darstellung einer unendlichen Grafik. In diesem Zusammenhang wird eine Suchmethode als vollständig beschrieben, wenn garantiert ein Zielzustand findet, wenn es existiert. Die Suche nach der Breite ist vollständig, aber die Tiefe-First-Suche ist nicht. Bei der implizit dargestellten unendlichen Graphen wird die Breite-First-Suche schließlich den Zielstatus finden, aber die erste Suche in der Tiefe kann in Teilen des Diagramms, die keinen Zielzustand haben und niemals zurückkehren, verloren gehen.^[12]

BFS -Bestellung

Eine Aufzählung der Eckpunkte eines Diagramms soll eine BFS -Bestellung sein, wenn es sich um die mögliche Ausgabe der Anwendung von BFS auf dieses Diagramm handelt.

Lassen ${\ displayStyle g = (v, e)}$ ein Diagramm sein mit ${\ displayStyle n}$ Eckpunkte. Erinnere dich daran ${\ displayStyle n (v)}$ ist der Satz von Nachbarn von ${\ displayStyle v}$ . Lassen ${\ displaystyle \ sigma = (v_ {1}, \ dots, v_ {m})}$ eine Liste verschiedener Elemente von sein ${\ displayStyle v}$ , zum ${\ displayStyle v \ in v \ setminus \ {v_ {1}, \ dots, v_ {m} \}}$ , Lassen ${\ displayStyle \ nu _ {\ sigma} (v)}$ Sei das geringste ${\ displayStyle i}$ so dass ${\ displayStyle v_ {i}}$ ist ein Nachbar von ${\ displayStyle v}$ wenn so ein ${\ displayStyle i}$ existiert und sei ${\ displayStyle \ Infty}$ Andernfalls.

Lassen ${\ displaystyle \ sigma = (v_ {1}, \ dots, v_ {n})}$ eine Aufzählung der Eckpunkte von sein ${\ displayStyle v}$ . Die Aufzählung ${\ displayStyle \ sigma}$ soll eine BFS -Bestellung sein (mit Quelle ${\ displayStyle v_ {1}}$ ) Wenn, für alle ${\ displayStyle 1 <i \ leq n}$ , ${\ displayStyle v_ {i}}$ ist der Scheitelpunkt ${\ displayStyle W \ in v \ setminus \ {v_ {1}, \ dots, v_ {i-1} \}}$ so dass ${\ displaystyle \ nu _ {(v_ {1}, \ dots, v_ {i-1})} (w)}$ ist minimal. Äquivalent, ${\ displayStyle \ sigma}$ ist eine BFS -Bestellung, wenn für alle ${\ displayStyle 1 \ leq i <j <k \ leq n}$ mit ${\ displayStyle v_ {i} \ in n (v_ {k}) \ setminus n (v_ {j})}$ Es gibt einen Nachbarn ${\ displayStyle v_ {m}}$ von ${\ displayStyle v_ {j}}$ so dass ${\ displayStyle m <i}$ .

Anwendungen

Breadth-First-Suche kann verwendet werden, um viele Probleme in der Graphentheorie zu lösen, beispielsweise:

Kopieren Müllsammlung, Cheneys Algorithmus
Finden der kürzester Weg zwischen zwei Knoten u und v, mit der durch Anzahl der Kanten gemessenen Pfadlänge (ein Vorteil gegenüber Tiefe-First-Suche)^[13]
(Umgekehrte) Cuthill -Mckee Netznummerierung
Ford -Fulkerson -Methode zum Berechnen der Maximaler Fluss in einem Flussnetzwerk
Die Serialisierung/Deserialisierung eines binären Baums gegenüber der Serialisierung in sortierter Reihenfolge ermöglicht es, dass der Baum effizient neu konstruiert wird.
Konstruktion des Fehlerfunktion des Aho-Corasick Muster -Matcher.
Testen Bipendität einer Grafik.
Implementierung paralleler Algorithmen zur Berechnung des transitiven Verschlusses eines Diagramms. ^[14]

Siehe auch

Verweise

^ Das heißt, ein Knoten, der die angegebene Eigenschaft erfüllt
^ Cormen Thomas H.; et al. (2009). "22,3". Einführung in Algorithmen. MIT Press.
^ "Graph500 -Benchmark -Spezifikation (Supercomputer -Leistungsbewertung)". Graph500.org, 2010. archiviert aus das Original Am 2015-03-26. Abgerufen 2015-03-15.
^ Zuse, Konrad (1972), Der Plankalkül (auf Deutsch), Konrad Zuse Internet Archive. Siehe S. 96–105 der verknüpften PDF -Datei (interne Nummerierung 2.47–2.56).
^ Moore, Edward F. (1959). "Der kürzeste Weg durch ein Labyrinth". Verfahren des internationalen Symposiums über die Theorie des Umschusses. Harvard University Press. S. 285–292. Wie von Cormen, Leiserson, Rivest und Stein zitiert.
^ Skiena, Steven (2008). "Sortieren und Suchen". Das Algorithmus -Designhandbuch. Springer. p. 480. Bibcode:2008adm..book ..... s. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
^ Lee, C. Y. (1961). "Ein Algorithmus für Pfadverbindungen und seine Anwendungen". IRE -Transaktionen auf elektronischen Computern. doi:10.1109/tec.1961.5219222.
^ Cormen, Thomas H. "22.2 BRAITH-First Search". Einführung in Algorithmen. ISBN 978-81-203-4007-7. OCLC 1006880283.
^ "Stack-basierte Graphtraversal ≠ Tiefe erste Suche". 11011110.github.io. Abgerufen 2020-06-10.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "22.2 Breite-First-Suche". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. S. 531–539. ISBN 0-262-03293-7.
^ Russell, Stuart; Norvig, Peter (2003) [1995]. Künstliche Intelligenz: ein moderner Ansatz (2. Aufl.). Prentice Hall. ISBN 978-0137903955.
^ Coppin, B. (2004). Künstliche Intelligenz beleuchtet. Jones & Bartlett Learning. S. 79–80.
^ Aziz, Adnan; Prakash, Amit (2010). "4. Algorithmen auf Grafiken". Algorithmen für Interviews. p. 144. ISBN 978-1453792995.
^ Dhulipala, Laxman; Blelloch, Guy E.; Shun, Julian (21. August 2019). Theoretisch effiziente parallele Graphalgorithmen können schnell und skalierbar sein. p. 17. Arxiv:1805.05208. doi:10.1145/3210377.3210414. ISBN 9781450357999. S2CID 44126609.

Knuth, Donald E. (1997), Die Kunst des Computerprogrammierens Vol 1. 3. Aufl., Boston: Addison-Wesley, ISBN 978-0-201-89683-1

Externe Links

Offene Datenstrukturen - Abschnitt 12.3.1 - Breite zuerst suchen, Pat Morin

[1] Das heißt, ein Knoten, der die angegebene Eigenschaft erfüllt

[2] Cormen Thomas H.; et al. (2009). "22,3". Einführung in Algorithmen. MIT Press.

[3] "Graph500 -Benchmark -Spezifikation (Supercomputer -Leistungsbewertung)". Graph500.org, 2010. archiviert aus das Original Am 2015-03-26. Abgerufen 2015-03-15.

[:0-4] Zuse, Konrad (1972), Der Plankalkül (auf Deutsch), Konrad Zuse Internet Archive. Siehe S. 96–105 der verknüpften PDF -Datei (interne Nummerierung 2.47–2.56).

[5] Moore, Edward F. (1959). "Der kürzeste Weg durch ein Labyrinth". Verfahren des internationalen Symposiums über die Theorie des Umschusses. Harvard University Press. S. 285–292. Wie von Cormen, Leiserson, Rivest und Stein zitiert.

[skiena-6] Skiena, Steven (2008). "Sortieren und Suchen". Das Algorithmus -Designhandbuch. Springer. p. 480. Bibcode:2008adm..book ..... s. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[7] Lee, C. Y. (1961). "Ein Algorithmus für Pfadverbindungen und seine Anwendungen". IRE -Transaktionen auf elektronischen Computern. doi:10.1109/tec.1961.5219222.

[8] Cormen, Thomas H. "22.2 BRAITH-First Search". Einführung in Algorithmen. ISBN 978-81-203-4007-7. OCLC 1006880283.

[9] "Stack-basierte Graphtraversal ≠ Tiefe erste Suche". 11011110.github.io. Abgerufen 2020-06-10.

[clrs-10] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "22.2 Breite-First-Suche". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. S. 531–539. ISBN 0-262-03293-7.

[11] Russell, Stuart; Norvig, Peter (2003) [1995]. Künstliche Intelligenz: ein moderner Ansatz (2. Aufl.). Prentice Hall. ISBN 978-0137903955.

[coppin-12] Coppin, B. (2004). Künstliche Intelligenz beleuchtet. Jones & Bartlett Learning. S. 79–80.

[13] Aziz, Adnan; Prakash, Amit (2010). "4. Algorithmen auf Grafiken". Algorithmen für Interviews. p. 144. ISBN 978-1453792995.

[14] Dhulipala, Laxman; Blelloch, Guy E.; Shun, Julian (21. August 2019). Theoretisch effiziente parallele Graphalgorithmen können schnell und skalierbar sein. p. 17. Arxiv:1805.05208. doi:10.1145/3210377.3210414. ISBN 9781450357999. S2CID 44126609.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Datenstrukturen und Algorithmen
Datenstrukturen	Array Assoziatives Array Binärer Suchbaum Fenwick Tree Graph Hash-tabelle Haufen Verlinkte Liste Warteschlange Segmentbaum Stapel Saite Baum Trie
Algorithmen	Backtracking Binäre Suche Breite-First-Suche Tiefe-First-Suche Teilen und erobern Dynamische Programmierung Falten Gierig Minimax Rekursion Sortierung Streaming Linie fegen Topologische Sortierung
Liste der Datenstrukturen Liste der Algorithmen