herzlich willkommen zur einführung ihrer mama detail sowie eine finte programmierung heute wollen wir über weiter über dynamische datenstrukturen reden konkret über die grafen und wir haben beim letzten mal über besprochen wo ihm als spezialfall von graphen heute geht es um berichtete gewichtete grafen und die suche in solchen ja was ist überhaupt ein christ traf bisher war unsere baumstrukturen und entsprechend unsere grafen immer eingerichtet sprich vater zwischen zwei knoten könnten in beide richtungen genutzt werden gerichte darauf kann das nicht das heißt dass es durchaus möglich dass wir von einem knoten zu dem anderen kommen aber nicht den gleichen weg zurück verwenden können diese darstellung oder diese abstraktion bildet die realität natürlich deutlich besser ab wir kommen gleich noch mal so ein paar beispiele wichtig für uns also dass ein solcher drauf dann dargestellt wird über entsprechende kanten zeigen die pfeile drücken also aus in welche richtung ich diese kante nutzen kann und weiß ich schon mal heißt jetzt gesehen haben in diesem unseren beispiel wir haben uns jetzt den fall dass hier ein knoten unterschiedliche anzahl von ausgehen und eingehenden kanten haben kann das war natürlich vor nicht der fall bei einem ungerechten graf worden hier einen server ausgehen dann eigentlich immer gleich weil wie gesagt jeder kannte in beide richtungen genutzt werden könnte hier ist das nicht mehr der fall das heißt hier wäre es also möglich dass man hier ist es möglich dass wir von knoten sechs zu vier anderen knoten ausgehend ja uns weiter bewegen können zudem knoten 6 zurück kommen wir aber hat sich nun über die 7 und hiervon der acht zurück alles andere sei nicht möglich weil es noch wichtig zu wissen was ein zyklus ist dann von morgens spricht dafür den zyklus oder kreis kreise gesagt nicht in geometrisch abstrakten sind im kreis bedeutet einfach dass ich das ein ford gibt über mehrere knoten wo ich zum anfangspunkt zurückkommen also hier beispielsweise von einem neuen über die 10 12 und zurück zum 9 das ist also ein zyklus und diese zyklus diese zyklen oder auch eine zyklen freiheit also sprich einen drauf ohne solche zyklen diese eigenschaft ist ja wichtig weil sie können sich vorstellen wenn nicht algorithmen durch einen graben laufen lassen und ja es hängt sich in solchen zyklen fest dann kommt es natürlich zu keinem ergebnis was natürlich sehr sehr schlecht ist gut waren bildungs beispiele je nach morgen abstrahiert gibt es also unzähliger unseren transportwesen ist also ein knoten eine beliebige kreuzung die kanten sind entsprechend straßen und gerichtete kanten werden alle straßen im web kontext wäre jeder jede website einen knoten die entsprechenden links zu anderen webseiten zu anderen seiten enthält eine solche heime link ist eingerichtete kannte weil sie kann nur in eine richtung beschritten werden und es muss erst ein neuer hyperlink zurück definiert werden ansonsten komme ich nicht mehr zur ursprung seite zurück genauso im finanzsektor hier gibt es banken mit entsprechenden knoten transaktionen also die überweisungen die ich louis direktionalen eine richtung durchführen telefonnummer genauso im kommunikationsbereich usw so gut die fragestellungen haben wir teilweise schon beantworten unsere mini zahl beispiel das heißt wir müssen grundsätzlich klären ob es überhaupt in diesen gerichteten graben einen weg zwischen der knoten erst in den knoten theaters und ortet gibt wenn das nicht der fall ist ist keine kommunikation möglich die meisten probleme werden sich eher auf die zweite frage beziehen heißt was ist der kürzeste fort das heißt es mehrere wege von essen nach t welcher ist der beste hinsichtlich irgendeiner metriken hab das jetzt sozusagen die anzahl der zwischen knoten sind ob das die kosten über die kanten sind ob das irgendwelche anderen parameter sehen das sei mal dahin gestellt ja die zyklen freiheit haben wir gerade geklärt und gibt natürlich noch alle anderen fragen würden noch die konnektivität das heißt gibt es einen gerichteten fort der alle knoten in diesem grafen verbindet entspricht ich möchte die menge der kanten so weit aus zunimmt dass trotzdem alle knoten verbunden sind auch die anzahl der kranken minimiert wird gut hier erstmal das anwendungsbeispiel im web domain noch mal vor veranschaulicht das heißt ich habe irgendeine stopp-seite auf diese stopp-seite gibt es verschiedene links zu anderen webseiten die entsprechend hier vernetzt sind und sind laptops sprich die die robots die von suchmaschinen kommen machen genau das kann sich auch serbe relativ schnell implementieren diese krone machen nichts mehr außer diese diese links in der warteschlange machen und da rein zu stecken und dann besuchen sie link nach link die neuen seiten ab und machen genau das gleiche wie so das heißt ich nehme jetzt beliebige seite was zum beispiel die 45 neue website hier findet jeder irgendwelche links die führen scheinbar nicht zurück zur seite 1 und dann führen wieder zu anderen webseiten diese neuen links packe ich wieder in meine worte schlange und wenn ich alle hier aufgenommen haben nächsten aus meiner großen worte schlange raus und bist du was du die ganze struktur und so bilde ich sozusagen wenn meine zwei infrastruktur eine kraft oder präsentation ab und gleichzeitig sehe ich damit auch wie der vernetzungsgrad zwischen einzelnen seiten zwischen einzelnen unterseiten ist das führende links gibt ob die nur unidirektionale sind was dann wieder aussagekraft hat bezüglich der stärke dieser vernetzung also wenn ich natürlich nur ausgehende links habe ist natürlich was deutlich anderes als wenn ich von einem möglichen anderen seiten auch wieder zurück verlinkt werden und genau das machen die suchmaschinen auch mit ihren algorithmen zur bewertung von von links oder von treffen im netz gut für uns im kontext von java ist eine schöne art ab wie das ist die kraft und die bietet eigentlich alles was sie genau dafür brauchen das heißt sie können damit ihre kanten ihre knoten definieren sie können entsprechend solch geraten diese aufgebraucht haben aufgebaut ärmer umkehren dann können hier wunderbar damit arbeiten das heißt wenn sie hier immer mit rumspielen ist das genau ihre freundin der programmierung dienst verwenden sollten gut wir wollen jetzt einen kleinen exkurs mache ninja spezielle probleme innerhalb solcher grafen und zwar ist hier der große bereich der minimalen spannbauer vielleicht haben sie schon mal gehört bin ich mal gespannt waren auch mst genannte minimum spanning tree definiert sich als ein innerhalb eines solchen tragen und diese paarung oder dieser spannung der iss verbunden der ist nicht zyklisch also abzüglich es gibt keine kreise oder keine zu den inhalt dieses baumes und enthält alle knoten eines vorgegebenen graben nur um ein beispiel das also zum minimale spann warum ist völlig losgelöst ob diese grafen gerichtet oder hingerichtet sind ob sie gewichtet oder um gewichtet sind all das spielte keine rolle hier ist erst mal allgemein die definition wieder dem spanier das heißt er verbindet alle knoten in einem graphen ist dabei kreisfrei und bildet entsprechend durch diese eigenschaften eine spezialform eines grafen welche baum und deswegen heißt der minimaler spannbauer gut wir beschäftigen uns natürlich mit diesem falle jetzt hier mal mit der spezial vor dem spezial von eur mit der anwendung auf spezielle graf nämlich in unserem fall gewichtete grafen gewichteter graf ist im unterschied zu einem gerichteten graf wieder was anderes bei einem gewichteten kragen dann einfach die kanten zwischen zwei knoten wir sehen's hier die haben einfach ein gericht stellen sich also vor sie müssen im land hin und her aufbauen sowie portugal und in portugal ist gibt es große teile der autobahn und auto oder straßenabschnitte sind mit mautpflichtig und das ist jetzt nicht gesagt ist sondern dass die kürzeste strecke unbedingt die günstig ist weil die kürzeste strecke oder die eine bestimmte strecke die zwar schnell geht aber unglaublich hohe kosten verursacht eine andere strecke da vielleicht ein bisschen länger dafür dass sie kostengünstiger genau das kann ich damit ausdrücken ich kann ja das sagen je nach meinem bei kriterium ruhiger zu sagen kosten in abstrakter form ansätze auf dessen datendurchsatz ist ob das reale kosten sind ob das denn distanz ist die kann ich sozusagen auch solche erkannten anwenden hier in unserem beispiel haben wir uns mal ein bisschen für einfach gemacht haben einfach gesagt versuchen in form dieser distanz so etwas habe ich mal die länge der der der kranken auszudrücken also sprich sehr lange kranken wir haben eine hohen wert kurze kann geringer werk auch wenn es nicht überall hundertprozentig zutrifft muss ich schon hier die 24 23 das wird wahrscheinlich nicht passen aber wir haben auf jeden fall ihren beispiel grafen einen gewichteten beispiel grafen bei denen die kanten bestimmte gewicht haben und diese gerichte sind positiv warum sind die positiven ja wenn die negativ werden müsste der algorithmus minimal abgeändert werden hier in dem fall und die ursprüngliche variante geht tatsächlich davon aus dass man überall positive kanten gewichte haben das heißt wir kriegen keine kosten gutgeschrieben ein erkannter verwenden weil das in der realität auch so möglich ist nein aber es gibt es keine möglichkeit um eine mautstraße strecke rückwärts nach vorn und damit dann geld zu verdienen das funktioniert nicht so über die kanten gewicht haben als wir schon besprochen was die entsprechend repräsentieren können und mein ziel ist jetzt also in diesem großen grauen also mit allen karten fed und den markiert eine minimale spannung ganze finden das heißt finden wir den teil graf und den teil bau mit diesem fall der alle knoten miteinander verbindet und dabei die geringsten kosten verursacht und der minimale spannender macht genau das das heißt er hat mir jetzt einen weg gefunden oder anhalten als einen teil grafen aufgebaut der zugang frei ist und der alle knoten einander verbindet so ob tatsächlich minimalen ist oder nur ein sehr günstiger im kopf das werden wir uns je nach lösungsansatz jetzt mal anschauen gut an denn das brauche ich für solche minimalen spannend bäume gibt es auch wieder an der praxis zu hause also gerade im netzwerk technikbereich die netzwerkadministration ein standardprotokoll es gibt es minimal spanning tree protocol was bei der kommunikation von ja rechnersystemen standort protokoll ist hier vor ort verwenden ist in der bilderkennung sattelten des bildes auffinden von straßen und das genutzt also in allen möglichen bereichen kommen solche spannend war immer zum einsatz und deswegen müssen wir die hier auch können und vor allen dingen müssen wir verstanden haben in ihrer ausprägung dann auch auf unterschiedliche probleme anwenden können gut im kontext von solchen minimalen spannt bäumen ist noch ein anderer begriff relativ wichtig und oder die priorisierten 2000 das sogenannte qi die strategien minimale spannender verwandeln verwenden solche politische strategien oder wie die ansatz und kriege bedeutet hier mal die freie übersetzung gefräßig habgierig warum macht man das ganze in der marken problem man muss außen oder auch nur unheimlich großen anzahl von entscheidungen möglichst sinnvolle auswählen um zum ziel zu kommen stellen sich also vor sie haben sind krediten oder allgemein algorithmus und der muss ihnen von irgendeinem stoff knoten aber bekannte aber ist mit dir als nächstes besucht und die muss er noch irgendeine nach unten entscheidungskriterium auswählen welche jährige kannte er die kritik wird man ihnen machen einfach nichts weil das ganze stück biete im modus zu nehmen was nach ihrer nach ihrer einfachen metrik dass die optimale entscheidung wäre und achten dabei nicht auf irgendwelche nachteile die ihnen dadurch entstehen würden das heißt in unserem fall ich schaue mir meine kranken an meiner nachbarschaft von den knoten dich besuchen kann eben einfach und günstig da muss man dann die günstigste keine nämlich mit der arbeite ich und ich weiß es nicht ob diese entscheidung global betrachtet gut war oder ob es später vielleicht noch eine andere möglichkeit gibt die das besser darstellt im einfachsten fall wird diese kritisch strategie wirklich völlig stupide immer nur die günstigste kante nähen die demokraten findet versuchen weiter zu arbeiten das heißt ich muss mich entscheiden ich muss irgendeine entscheidung treffen auf basis von beschränkt informationen aus diesen beschränken informationen suche ich mir einfach immer die aktuell für mich beste entscheidung raus und hoffe dass ich damit auch zu einem ergebnis kommen mit diesen erklärungen kommen auch gleichzeitig zu dem problem wie die strategie algorithmus wird in vielen vielen anwendungsfällen keine globale optimale lösung finden dh er wird nicht das beste in einem großen problem finden er wird nur eine sehr gute lösung finden und zwar eine sehr gute lösung dahingehend also in schneller zeit mit lokalen informationen günstige entscheidungen trifft die sicherlich auch lokal gut sind und eine gute küche allgemeine lösung bieten aber es ist nicht die allerbeste waren wir einfach ausgedrückt sie haben 100 möglichkeiten oder tausend möglichkeiten so einen brauchen eine lösung zu finden und normale kritik strategien werden ihn mit einer relativ hohen wahrscheinlichkeit eine lösung finden die unter den top-50 von diesen 1000 dabei ist es auch nicht gewährleistet dass sie immer die beste lösung von diesen 1000 lösungen finden gibt aber auch wieder algorithmen ansätze kommunal gleich noch dazu die mit import gleichen tricks genau dieses problem lösen bzw umgehen und dann tatsächlich auch ein globales optimum finden gut schauen muss es mal an und zwar am beispiel von floskeln rhythmus der kraske algorithmus ist also ein algorithmus zum finden oder zu generieren eines minimalen spann baums der kristall rhythmus muss man sagen hat als vorgabe hat er die sicht auf einen kompletten grafen dh erkennt den grafen komplett mit allen knoten und allen kanten und die aufgabe jetzt in diesem grund muss möglichst schnell einen solchen minimalen spandau zu finden und der arbeitet nach dieser brien die strategie für die straight für die simple und wir haben das hier mal schritt für schritt also hier zu lesen von links nach rechts unserem zeile für zeile weil dargestellt das heißt der kastler rhythmus hängt an und schaut sich alle knoten an die knoten werden markiert welcher knoten ist schon mal welche knoten wurde schon besucht eine nicht besucht und sie ohne nachweis besuchten werden dann dunkel grau eingefärbt und der kreis der algorithmus nutzt für die darstellung der kanten beziehungen hat jahrzehnts liste und mit entsprechenden gewichten das heißt dass unsere liste durch also geordnet immer verbindungen zwischen den jeweiligen knoten hiervon 07 oder von der 23 und in der zweiten spalte sehen wir halt die gewichte unserer gewichteten kannten das heißt dass diese summer hier dargestellt auch als distanz werden etwa das heißt zwischen 0 und 7 haben wir also ein gewicht von 0,6 und von dort 23 diese distanz zu sagen ist geringfügig mehr kommen als das heißt diese art lizenz liste spricht die konnektivität zwischen den einzelnen knoten sind schon von vornherein sortiert nach den gewichten wir sehen uns hier so in der cross cult was macht das nichts war also sich diese liste und auch noch zu bearbeiten nimmt sich die günstigste karte raus wer weise diese zwischen null und sieben diese gleich hinzugefügt und r schaut jetzt ok welche knoten kommen damit in meine neu gebildete tragende struktur rein das also was multiples besucht die die sieben wird mit aufgenommen an er prüft in jedem zyklus oder in jeder integration ob die entstandene kraft zyklen frei ist ganz ganz wichtig das heißt gibt es jetzt hier irgendwie eine möglichkeit über noch einen anderen knopf dazu gehört habt nein es ist ja nicht der fall dann nehme ich mir im nächsten schritt die nächste günstigste krankt das wäre hätte die zwischen dem knoten 23 also die hier mit der gewinn von 0 17 was es jetzt entstanden jetzt sind sozusagen zwei trafen entstanden die sind noch nicht miteinander verbunden ist aber für krastel nicht schlimm er prüft ob es jetzt wieder zyklen gibt also spricht gibt es irgendeine möglichkeit wo die nun enthaltenen knoten über irgendeine form zu dem kreis für das ist nicht der fall so ist das ganze gültig die nächste günstige kannte war dann zwischen da einst unter 7 das heißt dass du diese hier die anderen knoten die jetzt schon besucht hat werden so aufgenommen diese beiden sind also jetzt hier enthalten in dem in der neu gebildete struktur die zwei die drei noch nicht warum nicht weil sie noch nicht verbunden sind mit diesem mit diesem haupt grafen ja so deswegen bleibt es gar nicht so die 1 kommt hinzu auch hier wird zwischen 1 und 7 wird geprüft bin ich weiter in zyklen frei das ist gegeben also passt dass diese drei knoten bilden also jetzt in der verbundene struktur jetzt kommt tatsächlich in der gewichtung die kante zwischen nur zwei mit der gewichtung und nun kommen wir 26 dazu was jetzt passiert das aha wir haben jetzt hier also tatsächlich eine verbundene struktur dies immer noch kreisfrei jetzt kommt die fünf und die sieben dazu unter abfolge auch das passt noch wir sind beide im kreis frei der knoten wird aufgenommen wir haben jetzt ihren verbundenen teichen und jetzt ist interessant jetzt wurde also nach der 5 und 7 würde jetzt die einzelnen die drei kommen warum wird diese kante übersprungen obwohl sie deutlich günstiger sei als die hier drüben da ganz einfach weil in dem fall so diese kann die aufnehmen würden würde diese würde dieser kraft nicht mehr kreis frei sein werden also dann hier in loop und das hat das wollen wir natürlich nicht genauso die knoten die verbindungs kanten zwischen den knoten 15 das war ja diese könnte würde auch zu einer kreis zu dem zyklus hierfür nur zu einem kreis funktioniert nicht die 27 hier dazwischen genauso deswegen ist die nächste kapitel hinzugefügt wird die kante zwischen 34 und der 5 die hier unten wir verbinden wieder unseren trafen das heißt nun sind alle knoten inhalt dieses graf verbunden auch die sechs das heißt wir müssen irgendwo noch die sechs hinzufügen kraske weiß natürlich dass die knoten menge die wir jetzt hier verbunden haben noch kleiner ist als die gesamtnoten menge deswegen sucht er weiter prüft bei jedem durchlauf keine zyklen freiheit hat da kommen also eine ganze menge von verkannten wo diese eigenschaft nicht mehr erfüllt werden ist einschließlich die günstigste karte wo die sechs hier enthalten ist diese kante ist nämlich zwischen dem 26 diese wird aufgenommen damit ist jetzt die anzahl der verbundenen knoten leichter anzahl der knoten in der gesamte block i die mir gegeben hat damit bricht mein algorithmus ab ich habe keinen kreis hier in diese struktur und damit ist mein minimaler spann waren fertig ob jetzt diese lösung die wir hier unten haben tatsächlich die global optimale ist ist nicht trivial sofort zu sagen wir können aber sagen dass eine günstige lösung in sehr kurzer zeit gefunden worden ist ja das ist das wichtige beim kraske da findet ein sehr schneller zeit einem minimalen spannbauer mit sehr günstigen mit sehr günstigen kannten ist auch nicht sicher gestellt dass die global optimal nun ist gut ein weiteres beispiel was ich tun möchte ist der prim algorithmus der prima algorithmus unterscheidet sich im vergleich zu proske dahin gehen dass den prima rhythmus so ähnlich wie in der realen welt die topologie nicht komplett bekannt ist der prima algorithmus nimmt sich also tatsächlich wie unsere sap web crawler vorhinein stocknote in unserem fall dink 0 und hat tatsächlich auch nur die sicht auf den gesamten trafen so weit wie die sichtweite familie einigen knoten ist das heißt von diesen knoten aus sind vier kanten möglich vier verbindungs pfade und nur auf dieser wissensbasis kann der algorithmus arbeiten das heißt prim findet uns einen minimalen spender beginnen von einem staat klugen innerhalb einer beliebigen struktur die struktur ist vorher nicht bekannt und prim wird uns aber nach dem gleichen prinzip wie krass eine günstige möglichkeit oder eine günstige lösung finden so fern dass diese gibt nach dem kriege prinzip wird aber auch hier nichts sicher stellen dass es eine globale optimale lösung ist wir machen also das gleiche wie beim casting gemacht haben quad vorher nur dass wir hier eine begrenzte wissensbasis haben das heißt hier das in unserer aktuellen verfügbaren kannten wir nehmen die günstigste wieder ganz credit like das ist die zwischen 007 das heißt unsere zwei stunden hier verbunden und jetzt zum knoten 7 und in unserer verarbeitung sind datenstruktur können wir jetzt eine menge von neuen kanten hier hinzu die man nutzen können das heißt unsere datenbasis die wir immer schön sortieren auch kanten gewichten wird erweitert nämlich zwischen denen oder mit dem kanten von der 007 das heißt unsere datenbasis gewachsen wird wiederum sortiert nach gewicht und jetzt ist sozusagen unser nur hinsicht weise begünstigt der pfad wieder ganz stupide der einfachste pfad hier oben genommen von der 107 ist nun der global günstigste der aktuellen sicht haben die verwende ich mit damit kommt jetzt der knoten 1 hin zu müssen also jetzt vertrieben und knoten 1 bietet uns neue möglichkeiten der kommunikation wieder über drei neue karten hier dazu kommen dass wir jetzt unsere liste als basis jahr wieder gewachsen die kanten des knoten 1 dann hier mit aufgenommen wir machen wieder eine sortierung über alle verfügbaren kanten und nehme auch hier wieder die kündigte oben raus das wäre von unter 2 das heißt es kommt jetzt hier entsprechend diese könne dazu wir sind weiterhin kreisfrei das passt wir nehmen die nächsten hinzu schauen dass man entsprechend hier wird und eine neue kannte vernehmung nicht besucht haben es kommt dann hier zwischen der 5 und 7 die kommt hinzu dann brauchen wir wieder nicht besuchte knoten dieser bisher haben nehmen hier zwischen vier und fünf diese kannte hinzu und schließlich dann hier unten die letzte kante die uns einen neuen knoten unsere struktur mit aufnimmt das wäre hier wieder die kante zwischen 36 und dazu auch hier wieder das ergebnis eine stark aus gestimmte grafen struktur und bauern zu sagen der wieder alle knoten in diesem netzwerk verbindet und auch hier wurde wieder penibel darauf geachtet die so geschaffene struktur keine kreise existieren ja das heißt hier haben wir einen grafen gefunden der uns ein ergebnis liefert beginnen von einem von uns vorgegebenen stadt kloten hier oben in dem kraftwerk muss ist das nicht gefallen der findet so auch als allererstes dass hier ein es ist aber nicht voraussetzung dass die null unterstadt knoten ist krastel kennt von anfang an alle knoten und alle kann hat also die menge dieser knoten und hat die menge aller verfügbaren kann und wird die entsprechend abarbeiten ja krastel können es aber auch beliebig sozusagen system bin nun beispielsweise vom knoten 4 starten und das ergebnis starten vom knoten 4 wird ein deutlich anderes sein als ein knoten 0 weil natürlich mit einer begrenzten sicht von stadt kloten 4 wir haben ganz andere linie gewählt werden als beim stadt kloten nur deswegen denke ich klar sagen dass betrachten unsere müller unsere minuten4 mal da ist der schritt würden wir diesen vier kanten von der 405 3 4 740 und das in nur sechs den günstigsten wählen und es wird in jedem fall also die kante zwischen den mühlen dafür genutzt werden ja wer das sind wir in unserem fall die man hierdurch kein gesamten stadt kloten 0 kommt dieser knoten er kommt diese kante zwischen der 40 nie zum tragen weil immer knoten mit günstigeren kranken aufgenommen werden konnten beim stadt kloten 4 und dem fall oder man von hier starten würden würde diese kante zwischen der vierten oder auf jeden fall mit gewählt werden das heißt wir sie zum verständnis es muss tatsächlich klar sein dass mit unterschiedlichen startpunkten ein solcher minimaler spann waren jeweils unterschiedlich ausgeprägt sein kann er dem was ich also hier von stationen von algorithmus verwendet kommen also unterschiedliche ergebnisse war es der letzte vertreter auf denen wir hier eingehen möchten ist der treiber wird muss warum ist das extra algorithmus für uns ein so wichtiger algorithmus ganz klar er findet im gegensatz zu ihnen anderen verfahren tatsächlich global optimale lösungen der texte algorithmus sucht uns einen kürzesten als einen global günstigsten fall unsere klopps ersten fahrt beginnen von einem beliebigen stadt kloten aus der dijkstra wird auf zwei arten angewendet entweder bereich der suche eines kürzesten vaters zu einem bestimmten knoten das heißt ich möchte einen einzelnen bestimmten knoten finden ich kann den text aber auch anwenden um einen kompletten minimalen spannender und im gesamten netzwerk zu finden um sozusagen alle knoten möglichst günstig zu finden erfinder wie gesagt ist er hat extra und dieser algorithmus lässt sich auf gewichtete ungerichtete graben anwenden und die eigenschaft oder die besondere eigenschaften für den extras dass er seine ergebnisse oder seien seine zwischenergebnisse in jeder runde neu bewertet das heißt mit jeder neu hinzugefügten kann oder mit jeder neu hinzugefügten wissensbasis in form von neuen kannten wird bewertet ob die bisherigen lösungen noch optimal sind oder ob es bessere möglichkeiten gibt das ergebnis ist in jedem fall und uns wieder ein minimaler und zwar auf sollte klaus ernst haben keine 90 banken so das beispiel ist ja mal von herrn oldenburg oder entschuldigung von der uni oldenburg übernommen weil es einfach sehr einleuchtend ist und wir machen jetzt einmal das beispiel ein auf basis dieser sehr einfache struktur hier unten sehen also unsere verschiedenen knoten und unsere stadt kloten ist sozusagen die der knoten 1 und wir sehen an jedem knoten tipps aktions und tube und dieses tube was das auszudrücken hat es hinten nur legende dargestellt die -1 heißt also der distanz war das heißt über welche distanz ist der aktuelle knoten zu erreichen das heißt alle knoten sind bisher unbesiegt alle haben den negativen distanz wert sobald diese gefunden sind werden sie natürlich mit einem aktuelles transferred gefüttert und sie haben nach den common noch einen zweiten platz hause auf das aktuell der nämlich den knoten über den sie erreichbar sind das heißt immer der knoten über welche über denen sie gerade erreicht werden denn eingetragen beispielsweise wenn ich eine an der auf den knoten drei springe und kommen über den knoten 2 dann wird hier entsprechend die zwei stehen weil die der knoten 3 über die über den knoten 2 besucht wird besuche ich den knoten 3 über den knoten 4 wurde hier nach dem komma entsprechend wenn es hier stehen also jeweils der vorhergehende knoten über den die sofort führt hin zum ziel knoten der wirte hinten eingetragen und der wird auch kontinuierlich aktualisiert wir uns jetzt das beispiel auch zeigen wird wir stoppen das einfach mal wir nehmen also die sichtweise unseres staates knotens 1 der hat also hier frei verfügbare kanten mit der gewichtung 25 und 1 er wird sich jetzt also die eins aussuchen als günstigsten fall das sieht natürlich von diesem knoten aus auch die anderen knoten die erreichbaren aktualisiert ja auch dass die einst bleibt weiterhin mit einer negativen distanz direkt erreichbar knoten selber ist ich kann jetzt den knoten 2 über den knoten 1 erreichen der distanz zwei über den vorgänger mit der distanz zwei entschuldigung ich habe den knoten 3 das erreichbar über war auch über den knoten 1 mit der distanz von 50 den ich habe das falsch ausgedrückt der erste punkt ist sozusagen der knoten über diese erreichbar sind der zweite punkt drückt die distanz aus der knoten 3 kann also über knoten 1 erreicht gehabt steht hier vorne drin mit der gesamtdistanz von fünf nämlich diese ein kannte und der knoten ziehen kann erreicht werden ebenfalls über knoten 1 mit dem distanz wert von 1 damals erst mal trägt er unerreichbar die wissensbasis wird ausgebaut und jetzt ist die frage macht er weiter er nimmt sich jetzt also aus der gesamten anzahl der verfügbaren kanten jetzt die nächste kannte wo sozusagen das globale die global distanz am wenigsten ansteigt das heißt aber dass entweder hier diese diese kante mit länger 1 hinzufügen warum bei der die gesamtdistanz sich auf zwei erhöht oder aber er wird hier oben die zwei nehmen war ja auch dann die gesamtdistanz auf zwei also spricht diese zwei von einer kante und diese 2 1 1 1 in der repräsentation von den kosten gleichwertig in unserer reise jetzt erstmal die zwei war hier sozusagen noch die kanten von also in unserer umsetzung wird als beispiel ist die anzahl der herbst mit zähnen oder sagen der 200 direkten kommunikation ist für ihn günstiger als zweimal einzel die wiese unten wir haben weil hier zwei cops so zwei einzelne kommunikationspanne mit nutzen würden das heißt dann nimmt sich hier oben die 2 die zwei ist an weiteren entsprechend erreichbar die drei wir sehen uns aber jetzt ich gehe noch mal ein über zurück bisher war der knoten 3 über die 1 erreichbar mit distanz 5 im nächsten schritt springe ich hoch habe dann auch hier neue kannte entdeckt zum knoten 3 und jetzt sage ich mir zu sagen dass jetzt die der knoten 3 mit distanz vier unten erreichbar ist über den knoten 4 das heißt jetzt werden diese pfade die hier oben und hier unten aufgetaucht sind mit in unsere entscheidungsbasis aufgenommen ich bin hier unter 2 aber alle kranken die von dem knoten 4 und von dem knoten 2 verfügt was entwerten meine entscheidungsbasis mit aufgenommen das heißt im nächsten schritt wird diese lange kannte die ursprünglich noch hallen morgen nicht mehr gewählt weil es einen kürzeren fahrt gibt eine kürzere zeit existiert entsprechend genau hier das heißt über den knoten 4 mit dem distanz wert 1 + 3 ist dieser knoten jetzt günstiger erreichbar als über den direkt wegen so einem nächsten schritt kommt natürlich dann hier diese einst dazu meine entscheidungsbasis oder meine wissensbasis über die möglichen kanten wächst entsprechend und ich kann jetzt entsprechend neu definieren wie es weitergeht als nächstes kommt jetzt hier diese eine zu warum weil 11 bis 13 und das ist global betrachtet die günstigsten distanzen ja 2 wenn ich das hier oben gehen würde und würde ich ihr eine neue kann in zu gehen würde ich in jedem fall mehr als diese globalen kosten drei haben zwei +352 plus 24 wenn ich hier und mal da gehen würde eins bis drei sind auch 4 deswegen ist hier diese fahrt zunächst günstigste in meiner aktuellen sichtweise bekannten deswegen gehe ich hier hoch und ich sehe jetzt sozusagen die sich hier oben das ganze erinnert ich kann jetzt also die die 3er weiterhin gut 3 und neuen pfad erreichen die drei ist jetzt also nicht mehr über diesen pfad erreichbar auch nicht mehr über diesen pfad weil ich einen neuen global günstigeren fahrt über die klotener 45 und dann zur freien gefunden einen schritt zurück bisher order günstigste entsprechend über knoten vier jetzt besuche ich den knoten fünf meiner neuen nutzbaren kanten kommen hinzu die einst und die die die einzel hoch sei und die kosten 2 zum knoten 6 und im nächsten schritt werden hier oben also das ganze aktualisiert und meine preise über den neuen günstigste erreichbar damit komme ich über knoten fünf günstiger so drei ja über knoten 5 mit dem globalen distanz wert einer anderen distanzen bleiben gleich die 2 ist weiterhin günstigste erreicht euro die 1 die 42 günstigste euro die einst und jetzt schaue ich noch zu habe ich den letzten knoten den ich hier jetzt von zwei stellen aus begehen können zunächst erstmal über die fünf spielerinnen treiben auch über die drei und schaue was hier ein globales optimum ist ich bin im knoten 6 und stelle fest dass die dass die distanz vier die günstigste ist und meine erreichbarkeit über den knoten für den günstigsten vater stellen dh ein gewicht über die vier +1 zur fünf plus zwei sind insgesamt vier in der gewichtung und damit ist dass der günstigste pfad der pfad hier oben ist auch weiterhin der der teurer und wird deswegen nicht genutzt und fällt raus und damit ist das jetzt unser ergebnis und bildet unseren globalen minimalen spannbauer beginnend von unserem staat knoten einzeln ja gut normalerweise würden wir hier noch jetzt mehrere beispiele machen das ist ganz ganz wichtig dass diese minimal dass ich diese minimalen spannen bäume und die verschiedene algorithmen also fast prien und den dijkstra algorithmus verstehen anwenden können probieren sie das aus machen sie das auf dem papier und implementiert und das ganze dann aus das wird definitiv ins schwerpunkt zeit dahin auch später in algorithmen und datenstrukturen wieder begegnen wird deswegen sie müssen sich in dem durchsuchen von solchen trafen dann solchen dynamischen strukturen müssen uns einfach gut zurechtkommen diese algorithmen müssen zu verstanden haben implementieren können anwenden können in diesem sinne war es vorher ich bedanke mich für die aufmerksamkeit und wir sehen uns zur nächsten einheit