Dijkstra Algorithmus (Graphentheorie)
Christian Haas - KSH
https://www.youtube.com/watch?v=P0lkQ9YCNqo

Transkript (automatisch erstellt)

0:00 wir erklären euch in diesem lernvideos den decks drago rhythmus dafür muss man zuerst einmal das prinzip des credit algorithmus verstehen
0:09 ein krieg muss versucht in jedem fall schritt so viel wie möglich zu erreichen er schaut immer gerade lokal also vor ort was das beste ist und dann kommt
0:21 manchmal gerade das beste über alles gesehen heraus und manchmal nicht am beispiel der geldübergabe können wir euch das prinzip des credit algorithmus
0:31 zeigen stellen werden uns nun es gibt 50 20 10 552 und einen anstieg der armut müssen immer die größte mitte unter dem zielwert und zieht diese funktion wehrt
0:46 ab danach zieht er die größte mitte die noch kleiner ist als der rest vom rest ab er verfährt so bis der rest gleich null
0:54 ist weil das so kompliziert sind erklären wir auch dies an einem konkreten beispiel nehmen wir an wir müssen 79 rappen zurückgeben
1:04 die größte münze unter dem ziel ist die 50 dann bleiben noch 29 rappen übrig die nächstgrößte minze unter 29 jahren ist die 20 es bleibt nur noch 9 rappen nun
1:18 sieht er 574 haben die nächstgrößte minze ist die zwei übrig bleiben nochmals zwei rappen dieses 2000 kann er gleich mit einer weiteren zwei minuten
1:31 abdecken der rest ist jetzt gleich null mit der zielwert ist er leicht in diesem fall haben wir zufälligerweise auch das
1:39 globale optimum erreicht denn wir haben das geld mit so wenigen münzen wie möglich zurückgegeben das ist jedoch nicht immer so wie wir am
1:48 beispiel der user sehen im laden gibt es 12 96 trierer und einer packung für das osterfest brauchen wir 15 eier
2:01 dabei wollen wir so wenige packungen wie möglich brauchen nach dem release werden wir in diesem fall zuerst seine zwölf verpackten ausgegangen
2:11 nun brauchen wir noch drei weitere die nächste größtmögliche packung ist die eine packung diese müssen wir einen dreimal
2:20 nacheinander nehmen in diesem fall haben wir verpackungen gebraucht das entspricht dem lokal und die bessere lösung wäre jedoch eine neue
2:29 noch besser packen weil wir dann zwei packen gebrauchen was ist das globale optimum für uns zum beispiel jetzt kommen wir zu einem free die algorithmen
2:40 welcher immer das globale optimum erreicht hat extra rhythmus der rhythmus ist aus der klasse der politik mit ihm kann man jeweils den vierzigsten
2:53 weg zwischen zwei beliebigen knoten finden und somit das globale optimum bestimmen er schaut in jedem schritt alle nachbarn
3:02 seien bis jetzt erreichten kloten an und nimmt dann immer denkt noten dazu der die kürzeste distanz zum staat hat die distanz zahlen der knoten vom stadt
3:13 kloten aus änderung sich dabei laufen am anfang haben alle knoten den wertungen um das zu veranschaulichen ein beispiel dazu
3:25 wir starten in frankfurt und wollen den kürzesten weg nach münchen finden wie schon erwähnt haben alle knoten zu beginn denn distanziert unendlich nun
3:37 schaut er sich alle nachbarn des staates knotens frankfurt an das sind mannheim mit der distanz 85 kilometer und würzburg mit der distanz
3:48 186 kilometer er nimmt jetzt den knoten mit der kürzesten distanz zum start drücken das ist mannheim der einzige nachbarn von mannheim ist
4:00 karlsruhe der weg dorthin beträgt vom stark noten aus 165 kilometern diese ist immer noch kürzer als der weg
4:11 nach würzburg deshalb zieht er diesen knoten in betracht dann schaut er sich die nachbarn von
4:19 karlsruhe an das ist nur augsburg mit der distanz 415 kilometern ersucht nun wieder den knoten mit der kürzesten distanz zum staat in
4:32 dem fall ist dass würzburg mid würzburg verbunden sind nur erfurt und nürnberg mit 2 189 kilometern und 3 172 kilometern distanz im vergleich zur
4:48 nürnberg und augsburg ist erfurt am schnellsten erreichbar annimmt erfurt zudem besuchten knoten dazu schaut sich die nachbarn an und merkt dass erfurt
5:00 keine weiteren nachbarn hat der nächste knoten mit der kürzesten distanz ist nürnberg von dort führt ein weg direkt nach münchen mit insgesamt 539 kilometer
5:15 doch augsburg ist schnell erreichbar mit 450 kilometern der einzige weitere nachbar von augsburg ist münchen mit 4 199 kilometern distanz zu stark noten
5:29 somit ist der weg über mannheim karlsruhe und augsburg nach münchen kürzer als der weg über würzburg und nürnberg nach münchen
5:40 wir haben nun den kürzesten weg von frankfurt nach münchen gefunden und kommen wir zu einem etwas komplizierteren beispiel
5:50 wir starten bei a und wollen den kürzesten weg zu gehen denn alle knoten haben am anfang den wert unendlich nun schauen wir uns die nachbars knothe von
6:02 a an und aktualisieren die distanz zahlen von a nach b 7 von a nach cs5 und von a nach b 11 bei großen grafen empfiehlt es sich auch immer
6:17 aufzuschreiben von oma gekommen ist zurzeit ist die distanz am kürzesten deshalb nehmen wir mit zu den besuchten knoten dazubuchen
6:27 die nachbarn von c sind b und stehen zu bewähren es 18 doch von a nach b sind es nur sieben deshalb lassen wir die sieben stehen von
6:42 c nachdem das 22 wir schauen uns jetzt wieder alle nachbarn unserer bis jetzt erreichten knoten an die distanzen 7 11 und 22 stehen zur auswahl
6:56 wir nehmen die kürzeste distanz das ist sieben von a nach b somit nehmen wir b zu den erreichten knoten auf b hat noch zwei nicht
7:08 erreichte nachbars knoten nenne h und 11 wir aktualisieren die distanz zahlen von h&m und schreiben auch wieder dazu von unwerth gekommen sind
7:20 nun werden wieder alle distanzen miteinander verglichen und er entscheidet sich für h da dieser die ganze distanz zum staat kloten hat war
7:30 hat jedoch keine noch nicht erreichten nachbarn deshalb schauen wir uns die übrig gebliebenen distanzen an
7:37 zur auswahl stehen 19 und 22 somit fällt die entscheidung auf den knoten 11 mit der distanz 9 und wenn notieren dass wir vom weg gekommen sind
7:48 wir aktualisieren wieder die distanz zahlen der nachbarn von 11 das ist hier null geht mit der distanz 21 der nachbar mit dem kleinsten distanz
7:59 wert ist nun mit se hat zwei noch nicht besuchte nachbarn zu den es 19 was kleiner ist als 22 deshalb aktualisieren wir diese distanz zahl und notieren den
8:12 herkunfts knoten nachbar ist die distanz wäre 24 was größer ist das einen sonst deshalb dass mir diese distanz wert aus nun bleiben nur noch für distanzen 1920
8:27 zur auswahl da geht der kürzeren distanz nach das system mit 19 damit internet bereit bis hoch zum
8:36 vierten dazu und aktualisiert weder die distanz zahlen dann noch nicht erreichten nach bastürk 19 und 28 was ist größer als sonst deshalb lassen
8:49 wir die am 20 jetzt haben wir eigentlich nach die 21 zur auswahl es war peter von fcg und hat somit den
8:57 kürzesten weg von gegenden an dem das wir aufgeschrieben haben woher werden konnten können wir den weg zurück leichter finden
9:07 wir kamen vom fcf gelangte er über behrendt wir hoffen wir konnten euch weiterhelfen und versteht nun den extrachor rhythmus