Suche - Breiten- und Tiefensuche
Günther Jena
https://www.youtube.com/watch?v=7RCp2jNwxjQ

Transkript (automatisch erstellt)

0:01 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
0:14 einzelnen Knoten bei einer Suche in einem Graf gehen wir von einem Startknoten aus und haben einen oder mehrere Zielknoten in unserem Fall
0:24 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
0:39 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
0:51 bestimmten Algorithmus vor dieser algoritthmus schaut wie folgt aus wir haben eine Liste mit offenen Punkten in diese Liste kommen also
1:03 Knoten hinein die wir der Reihe nach Entdecken diese Liste wird am Anfang mit dem Startknoten initialisiert als nächstes sehen wir
1:13 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
1:26 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
1:35 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
1:48 nehmen wir den ersten Knoten aus der Liste offen heraus dann nennen wir dies den aktuellen Knoten wir überprüfen ist aktueller
1:58 Knoten ein zelknoten ein oder der Zielknoten wenn ja dann ist der Zielknoten gefunden wenn nicht dann erweitern wir diesen Knoten das heißt
2:10 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
2:24 wir führen also zwei Listen einmal mit offenen also gerade entdeckten oder noch zu bearbeiten Knoten und eine Liste mit bereits besuchten
2:36 Knoten wenn wir diesen Knoten abgearbeitet haben geht die Schleife wieder weiter dies wollen wir uns nun an einem Beispiel
2:46 Anschauen der Algorithmus startet indem der starknoten in die Liste der offenen Knoten übernommen wird dann nehmen wir den ersten Knoten aus dieser offenen
2:59 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
3:15 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
3:29 als als nächstes besuchen wir a wir haben noch C und E drin von A aus ist kein weiterer Knoten
3:41 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
3:56 erreichbar S ist schon in der Liste der offenen od besuchten Knoten enthalten und wird dadurch nicht erweitert wir erweitern also um
4:09 B und geben C zu den besuchten Knoten hinzu als nächstes untersuchen wir e von E aus können wir nur Richtung D
4:25 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
4:39 besuchen Knoten enthalten also wird nicht weiter erweitert undüber geben ist der Liste der bereits besuchten Knoten
4:50 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
5:06 wieder das Erel Element aus der Liste das G g ist der Zielknoten also haben wir es erfolgreich
5:16 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
5:28 zu einer sogenannten breiten suche besser darstellen lässt sich dies indem wir noch mal zu der alten Darstellung zurück
5:39 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
5:52 sind immer zuerst in die Breite gegangen und dann so schrittweise in die Tiefe also wir haben Ebene Ebene in diesem Baum
6:04 abgearbeitet im Gegensatz dazu steht die Tiefensuche die Tiefensuche äh handelt die Erweiterung der Knoten anders wir haben bei der breiten suche
6:18 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
6:30 mit S starten untersuchen wir den Knoten s wir erbeitern es um AC C und
6:41 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
6:58 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
7:14 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
7:33 bereits in der offenen Liste drin ich schreib das noch entsprechend vollständig
7:47 hin und B nun untersuchen wir e von E aus lässt sich nur noch D erweitern
8:04 und von D aus landen wir bei unserem gewünschten Zielknoten g und wenn wir diesen Knoten g untersuchen stellen wir fest dass es
8:20 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
8:33 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
8:45 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
8:58 gehen immer zuerst in die Tiefe bevor wir in die Breite gehen dies ist die sogenannte Tiefensuche der einzige Unterschied zur Breitensuche ist dass
9:08 wir die Liste als einen Stack behandeln das heißt wir geben Elemente vorne hinzu die dann vorne wieder weggenommen werden im Gegensatz
9:21 zu einer Warteschlange wie die bei breitens Suche der Fall ist