Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Suche - Breiten- und Tiefensuche
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 44 Zeilen
- wir schauen uns die Suche in einem Graf an ein Graf besteht aus Knoten wie hier s c b e d g und a und Kanten Kanten verbinden diese
- einzelnen Knoten bei einer Suche in einem Graf gehen wir von einem Startknoten aus und haben einen oder mehrere Zielknoten in unserem Fall
- wählen wir s als unseren starknoten und G als unseren Zielknoten wir können dies auch anders zeichnen hier der exakt gleiche Graf nur anders
- dargestellt wir haben auch wieder S und G als Start und Zielknoten wenn wir jetzt solchen solche einen Graf durchsuchen wollen gehen wir nach einem
- bestimmten Algorithmus vor dieser algoritthmus schaut wie folgt aus wir haben eine Liste mit offenen Punkten in diese Liste kommen also
- Knoten hinein die wir der Reihe nach Entdecken diese Liste wird am Anfang mit dem Startknoten initialisiert als nächstes sehen wir
- dass wir eine Schleife haben wir führen also folgende Punkte mehrfach durch wir überprüfen ist die Liste offen ist diese leer wird beim ersten mal nicht der Fall
- sein weil ja der starknoten drin ist sollte es auch bei einem weiteren Durchlauf diese Liste leer sein so haben wir alle Knoten die erreichbar sind
- durchsucht und es ist der Zielknoten oder einer der Zielknoten war nicht dabei das heißt es führt zu einem Abbruch wenn diese Liste nicht leer ist
- nehmen wir den ersten Knoten aus der Liste offen heraus dann nennen wir dies den aktuellen Knoten wir überprüfen ist aktueller
- Knoten ein zelknoten ein oder der Zielknoten wenn ja dann ist der Zielknoten gefunden wenn nicht dann erweitern wir diesen Knoten das heißt
- wir schauen welche Knoten von diesem Knoten aus entdeckt werden können dazu später noch mehr dieser aktuelle Knoten wird dann zur Liste besucht hinzugefügt
- wir führen also zwei Listen einmal mit offenen also gerade entdeckten oder noch zu bearbeiten Knoten und eine Liste mit bereits besuchten
- Knoten wenn wir diesen Knoten abgearbeitet haben geht die Schleife wieder weiter dies wollen wir uns nun an einem Beispiel
- Anschauen der Algorithmus startet indem der starknoten in die Liste der offenen Knoten übernommen wird dann nehmen wir den ersten Knoten aus dieser offenen
- Liste heraus und erweitern diesen Knoten es wird erweitert um A C und E wir gehen einfach alphabetisch vor damit wir eine Reihenfolge der Erweiterungen definiert
- haben also wir entdecken A C und E jetzt haben wir in den in der offenen Liste AC und e in der besuchten Liste geben wir jetzt den aktuell besuchten Knoten hinzu
- als als nächstes besuchen wir a wir haben noch C und E drin von A aus ist kein weiterer Knoten
- erreichbar also geben wir ihn zu dem besuchten Knoten hinzu als nächstes ist c an der Reihe wir besuchen C von C aus ist nur B
- erreichbar S ist schon in der Liste der offenen od besuchten Knoten enthalten und wird dadurch nicht erweitert wir erweitern also um
- B und geben C zu den besuchten Knoten hinzu als nächstes untersuchen wir e von E aus können wir nur Richtung D
- erweitern und geben e bei den besuchten Knoten hinzu wir bearbeiten B wir sind jetzt hier bei B C und E ist bereits in der Liste der
- besuchen Knoten enthalten also wird nicht weiter erweitert undüber geben ist der Liste der bereits besuchten Knoten
- hinzu nun untersuchen wir d und von D aus lässt sich g erweitern und wir geben D zu den Besuchen Knoten hinzu wir nehmen jetzt
- wieder das Erel Element aus der Liste das G g ist der Zielknoten also haben wir es erfolgreich
- gefunden wir haben die Erweiterung immer hinten angestellt also bei den offenen Knoten haben wir neuentdeckte Knoten hinten angestellt dies führt zu so ein
- zu einer sogenannten breiten suche besser darstellen lässt sich dies indem wir noch mal zu der alten Darstellung zurück
- greifen wir haben mit S gestartet haben dann um AC C und E erweitert haben dann uns den Knoten B angeschaut dann D und dann g also wir
- sind immer zuerst in die Breite gegangen und dann so schrittweise in die Tiefe also wir haben Ebene Ebene in diesem Baum
- abgearbeitet im Gegensatz dazu steht die Tiefensuche die Tiefensuche äh handelt die Erweiterung der Knoten anders wir haben bei der breiten suche
- die neu entdeckten Knoten hinten bei der Liste hinzugefügt der offenen Knoten bei der Tiefensuche fügen wir diese nun vorne hinzu das heißt wieder wenn wir
- mit S starten untersuchen wir den Knoten s wir erbeitern es um AC C und
- E AC C und E S ist besucht nun untersuchen wir a und bei a geht es nicht mehr weiter es kann kein neuer Knoten entdeckt werden
- das heißt wir haben C und E in der offenen Liste S und a ist bereits besucht wir untersuchen nun C von C aus ist B erreichbar und nun
- geben wir das B nicht hinten an der Liste dran sondern wir fügen es vorne ein okay nun sind wir beim B von B lässt sich das E nicht mehr erweitern das ist
- bereits in der offenen Liste drin ich schreib das noch entsprechend vollständig
- hin und B nun untersuchen wir e von E aus lässt sich nur noch D erweitern
- und von D aus landen wir bei unserem gewünschten Zielknoten g und wenn wir diesen Knoten g untersuchen stellen wir fest dass es
- sich um den gewünschten Zielknoten handelt wir haben also nur die Reihenfolge geändert in der neuentdeckte Noten hinzukommen das heißt wir gehen
- wieder wenn wir das über die Ebenen betrachten nicht zuerst in die Breite wir haben ja bei der breiten suche s a c e besucht dann BD und dann g bei der
- Tiefensuche haben wir S und dann a besucht haben dann C besucht sind dann weiter nach B und sind dann wieder zurück nach E D und G das heißt wir
- gehen immer zuerst in die Tiefe bevor wir in die Breite gehen dies ist die sogenannte Tiefensuche der einzige Unterschied zur Breitensuche ist dass
- wir die Liste als einen Stack behandeln das heißt wir geben Elemente vorne hinzu die dann vorne wieder weggenommen werden im Gegensatz
- zu einer Warteschlange wie die bei breitens Suche der Fall ist
Zum Nachlesen
BreitensucheBreitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen.
TiefensucheTiefensuche (englisch depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten …
Bidirektionale SucheIn der Informatik zählt die Bidirektionale Suche zu den Suchverfahren, spezieller zu den uninformierten Suchverfahren. Wie der A*-Algorithmus und der …
Beschränkte TiefensucheBeschränkte Tiefensuche (englisch depth-limited search, DLS) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen.