Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Tiefensuche, Breitensuche, Dijkstra
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 52 Zeilen
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- sozusagen schon fix und fertig bearbeitet wurden und nicht mehr untersucht wurden und die Knoten die wandern jetzt sozusagen schrittweise aus
- 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
- 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
- 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
- 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
- nimmt erstmal den Startknoten in die mittlere Liste auf hat die natürlich vorne aus der noch aus der Liste der unbearbeiteten Knoten
- rausgenommen hinten bearbeitet worden ist doch nichts das passiert diesem nächsten Schritt und zwar passiert jetzt folgendes man schaut
- jetzt man nimmt den vordersten in dem Fall weg und schaut nach wo kann ich denn von diesem vordersten noch hinlaufen der
- nächsten wo ich hinlaufen kann ist natürlich der Knoten eh das heißt e wird eigentlich hinten dran gehängt
- so das heißt das ganze wird jetzt hier als Cube benutzen
- 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
- schon angedeutet ist natürlich rausgeflogen also er ist jetzt an vorderster Stelle damit wird als nächstes eh bearbeitet was vorne steht
- 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
- 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
- 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
- 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
- weiter also es wird immer vorne weggenommen äh versuchen wir uns noch mal hier so also es wird immer vorne weggenommen
- 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
- 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
- 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
- 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
- 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
- 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
- dann sieht der weitere Ablauf genau so aus wir uns auch ganz gerne hätte nämlich die Linke Liste ist vollständig
- 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
- 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
- der einzige Unterschied zwischen breiten suche Tiefensuche und da extra ist im Grunde dass diese mittlere Liste anders benutzt wird
- 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
- 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
- Zeitpunkt die optimalste Entscheidung das heißt diese mittlere Liste ist nicht nur einfach aneinander hängen beliebiger Art
- 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
- 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
- genommen aber die Knoten sind sozusagen in dieser mittleren Liste aufsteigen sortiert worden ja das ist nicht mehr ganz so einfach zu
- 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
- 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
- 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
- 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
- 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
- einem Kompositum geht also das kann man da noch mal wiederholen noch mal implementieren und ganz ganz ganz viel Stoff sozusagen zu zusammenführen
- 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
- geht immer möglichst lange sozusagen einem Fahrrad entlang bevor man dann irgendwann mal noch andere Wege ausprobiert so weit zu Gemeinsamkeiten
- 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
- 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
- bis zum nächsten Video daher macht's gut ciao
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 …
Dijkstra-AlgorithmusDer Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der …