Tiefensuche, Breitensuche, Dijkstra
Ingo Bartling
https://www.youtube.com/watch?v=KaKbmE0O8rk

Transkript (automatisch erstellt)

0:01 hallo in diesem Video möchte ich erklären wie die Tiefensuche breiten Suche und daixtra auf einem Graphen implementiert werden können und dass sie
0:10 alle drei im Grunde gleich implementiert werden können das muss man nicht so machen es gibt selbstverständlich auch andere Art und Weise wie man sie
0:17 implementieren kann aber das stellt für mich im Grunde so ein bisschen das Highlight in der aktuellen aktuellen Lehrplan der 11 Klasse da weißen
0:26 Zusammenhang Macht zwischen dem zweiten halb und dem ersten Halbjahr im ersten Halbjahr gab es ja die Liste und die Q und den Stack und so weiter und jetzt im
0:36 zweiten Halbjahr gibt's die Grafen und die binärbäume und hier diese drei Algorithmen Tiefensuche breiten suchen und lassen sich sehr ähnlich mit Hilfe
0:45 von Stacks und in dem Fall Priorität Warteschlange tatsächlich umsetzen so wie funktioniert das funktioniert so dass ich drei Listen brauche ich brauche
0:54 eine Liste für die unbearbeiteten Knoten das sind alle Knoten die sozusagen noch nicht erreicht wurden und noch nicht in Betracht gezogen werden konnten dann
1:05 gibt es hier eine mittlere Liste die heißt jetzt hier mal Breitensuche weil ich es einfach die breiten Suche machen möchte und da gibt es die Knoten die
1:12 sozusagen schon fix und fertig bearbeitet wurden und nicht mehr untersucht wurden und die Knoten die wandern jetzt sozusagen schrittweise aus
1:21 dieser Liste in diese Liste und wenn Sie hier bearbeitet wurden dann weiter in die hinterste Liste das heißt am Schluss ist anders als es jetzt hier aussieht
1:29 ist dann diese Liste leer die Liste leer und diese Liste leer mit allen Knoten wie es geht falls das nicht sein sollte also falls beispielsweise hier noch
1:41 tatsächlich irgendwelche Knoten drin sein sollten dann weiß man dass der Graph beispielsweise nicht zu hängen zusammenhängt war aber das soll uns in
1:50 dem Fall jetzt nicht interessieren wir machen das Ganze für einen zusammenhängenden Graphen so der erste Schritt der natürlich passiert ist man
1:58 nimmt erstmal den Startknoten in die mittlere Liste auf hat die natürlich vorne aus der noch aus der Liste der unbearbeiteten Knoten
2:08 rausgenommen hinten bearbeitet worden ist doch nichts das passiert diesem nächsten Schritt und zwar passiert jetzt folgendes man schaut
2:16 jetzt man nimmt den vordersten in dem Fall weg und schaut nach wo kann ich denn von diesem vordersten noch hinlaufen der
2:22 nächsten wo ich hinlaufen kann ist natürlich der Knoten eh das heißt e wird eigentlich hinten dran gehängt
2:33 so das heißt das ganze wird jetzt hier als Cube benutzen
2:38 und im nächsten Schritt ist es so dass A gestrichen wird aber wandert in die Liste hier der fertig bearbeiteten Knoten und eh entsprechend habe ich ja
2:49 schon angedeutet ist natürlich rausgeflogen also er ist jetzt an vorderster Stelle damit wird als nächstes eh bearbeitet was vorne steht
2:56 und wenn ich mir den Grafen anschaue dann kann man sehen von Ehe kommen nach B oder ich komme nach C das heißt in dem Fall wandern B und C hier hinten dran B
3:09 und C und raus so also e wird von vorne weggenommen B und sie wurden hinten angehängt sind jetzt aufgerutscht so jetzt gehe ich
3:19 nach B und schnell fest ah okay ich komme hier bis nach F das heißt in dem Fall hänge ich jetzt einfach aus dem F des F fliegt aus der Liste raus wird
3:28 hier hinten dran gehängt und im nächsten Schritt wird wieder das vordere genommen also das B und es bleiben C&F übrig so und so geht das jetzt im Grunde immer
3:36 weiter also es wird immer vorne weggenommen äh versuchen wir uns noch mal hier so also es wird immer vorne weggenommen
3:46 und es wird hinten dran gehängt das ist die klassische Q und so geht das im Grunde jetzt genau weiter und warum das jetzt breiten suche
3:54 heißt kann man jetzt hier an diesem gepunkteten Linien erkennen weil im Grunde diese Knoten wie in bei Wellen sozusagen in der Breite abgesucht werden
4:02 also ich beginne hier mit dieser ersten Welle also wo quasi die Störung im Wasser ist dann Betracht sich alle Knoten die sozusagen ein Kanten Schritt
4:11 entfernt sind das ist der Knoten eh dann kam mir hier der Knoten B und C als nächstes ich kann ja noch ein bisschen weitergehen
4:19 so B da kommt jetzt C also es sind dann hier alle Knoten betrachtet worden zwei Kanten Schritte zwei Kanten Schritte als nächstes kommen alle mit drei Kanten
4:30 Schritten das ist sehr F und D ja und ganz zum Schluss kommt dann geh und wenn man das jetzt sofort setzt das könnt ihr gerne mal machen
4:40 dann sieht der weitere Ablauf genau so aus wir uns auch ganz gerne hätte nämlich die Linke Liste ist vollständig
4:48 abgearbeitet worden die ist leer das heißt der Graph war auch tatsächlich Zusammenhängen ich habe alle Knoten erreicht ich habe auch alle abgearbeitet
4:55 abgearbeitet ist auch gut und alle Knoten sind zu einer anderen Reinfolge aber das ist völlig egal sind tatsächlich abgearbeitet worden so in
5:04 der einzige Unterschied zwischen breiten suche Tiefensuche und da extra ist im Grunde dass diese mittlere Liste anders benutzt wird
5:13 und zwar habe ich für die breiten suche eine Cube benutzt so für die Tiefensuche benutzt sie ein Steak kann man sich vielleicht auch merken
5:22 t und Stack so und der dikstra der ist ja ein sogenannter greedy Algorithmus das heißt ein gieriger Algorithmus übersetzt und damit macht er zu jedem
5:33 Zeitpunkt die optimalste Entscheidung das heißt diese mittlere Liste ist nicht nur einfach aneinander hängen beliebiger Art
5:41 also es wird wieder vorne noch hinten einfach angehängt sondern das wird immer nach Priorität eingefügt das heißt immer der nächste beste zu erreichende Knoten
5:49 wird gewählt damit muss ich sozusagen aufzeichnen wie weit die Knoten entfernt sind wenn es gleich weiter sind ist egal und da werden immer zwar auch von vorne
6:00 genommen aber die Knoten sind sozusagen in dieser mittleren Liste aufsteigen sortiert worden ja das ist nicht mehr ganz so einfach zu
6:07 implementieren deswegen wird sie oft in der Schule auch anders implementiert dass wir eine priority aber ich sag mal vom Verständnis her sollte das
6:15 prinzipiell klar sein und wer Lust Zeit und Muße hat kann das natürlich gerne auch mal implementieren denn Übung macht den Meister und es ist noch kein Meister
6:22 vom Himmel gefallen also macht es mal ich werde jetzt in einem anderen Video die breiten suche implementieren das geht relativ einfach wird mich dazu zu
6:33 an den arilies bedienen das ist so eine pseudo Datenstruktur nenne ich immer ganz gerne so eine Mischung als Liste und Harry das kann man ganz effizient
6:40 machen ansonsten auch da kann man natürlich noch mal den Stoff der das erste Halbjahres wiederholen weil es da natürlich im Grunde eigentlich auch in
6:48 einem Kompositum geht also das kann man da noch mal wiederholen noch mal implementieren und ganz ganz ganz viel Stoff sozusagen zu zusammenführen
6:56 und noch vielleicht ergänzen zum zum Abschluss die Tiefensuche heißt natürlich Tiefensuche weil man jetzt nicht in dieser Breite sucht sondern man
7:05 geht immer möglichst lange sozusagen einem Fahrrad entlang bevor man dann irgendwann mal noch andere Wege ausprobiert so weit zu Gemeinsamkeiten
7:15 und Unterschieden und wenn es hier mögt im anderen Video werde ich dann wie gesagt die breiten suchen noch implementieren nach dieser Form den DAX
7:24 haben wir die auch noch implementieren da werde ich allerdings eine andere Implementierung wählen einfach um auch zu zeigen dass man es anders machen kann
7:30 bis zum nächsten Video daher macht's gut ciao