Shortest Paths II

Video thumbnail (Frame 0) Video thumbnail (Frame 12313) Video thumbnail (Frame 24445) Video thumbnail (Frame 26624) Video thumbnail (Frame 37887) Video thumbnail (Frame 41794) Video thumbnail (Frame 52499) Video thumbnail (Frame 64854) Video thumbnail (Frame 77209) Video thumbnail (Frame 85225) Video thumbnail (Frame 92831) Video thumbnail (Frame 98282) Video thumbnail (Frame 102414) Video thumbnail (Frame 118619) Video thumbnail (Frame 121876) Video thumbnail (Frame 124597) Video thumbnail (Frame 128819)
Video in TIB AV-Portal: Shortest Paths II

Formal Metadata

Title
Shortest Paths II
Title of Series
Part Number
7
Number of Parts
15
Author
License
CC Attribution - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Metre Round-off error Zahl Haar measure Wavefront Permanent Real number Laufzeit Queue (abstract data type) Cloning Canonical ensemble Set (mathematics)
Stress (mechanics) Link (knot theory) Index Permanent Laufzeit Vertex (graph theory) Maxima and minima Supremum Quote Length Length
Metre Geometry Kante Addition Zahl Polygon mesh Moment (mathematics) Laufzeit Set (mathematics) Strecke Distance Physical quantity Index Permanent Iteration Length
Mathematics Standard deviation Wavefront Radical (chemistry) Distribution (mathematics) Direction (geometry) Moment (mathematics) Set (mathematics)
Kante Stress (mechanics) Greatest element Wavefront Link (knot theory) Consistency Compass (drafting) Surface Direction (geometry) Moment (mathematics) Set (mathematics) Inequality (mathematics) Equation Dreiecksungleichung Mathematics Energie Velocity Permanent Structural equation modeling Interface (chemistry) Iteration Summation Length Untere Schranke
Logical constant Standard deviation Trail Consistency Distribution (mathematics) Direction (geometry) Plane (geometry) Mathematics Sign (mathematics) Term (mathematics) Negative number Summation Length Untere Schranke Euklidischer Raum
Kante Geometry Trigonometry Dependent and independent variables Graph (mathematics) Coordinate system Set (mathematics) Hausdorff space Plane (geometry) Keilförmige Anordnung Angle Iteration Subgraph Function (mathematics) Green's function Interface (chemistry) Mathematical optimization Directed graph
Kante Trail Shortest path problem Shortest path problem Convex hull Dependent and independent variables Graph (mathematics) Direction (geometry) Set (mathematics) Function (mathematics) Rectangle Hierarchy Plane (geometry) Schulmathematik Angle Subgraph Selectivity (electronic) Directed graph
Standard deviation Trail Link (knot theory) Graph (mathematics) Direction (geometry) Moment (mathematics) Algebraic structure Binary file Distance Forest Keilförmige Anordnung Military operation Length
Operations research Stress (mechanics) Keilförmige Anordnung Iteration Military operation Negative number Theorem Condition number Distance Directed graph
Kante Operations research Trail Shortest path problem Direction (geometry) Moment (mathematics) Desire path Laufzeit Equation Theory Distance Inversion (music) Equivalence relation Degrees of freedom (physics and chemistry) Function (mathematics) Theorem Condition number Vertex (graph theory) Length Directed graph Length
Trail Iteration Function (mathematics) Iteration Vertex (graph theory) Infinity Length Directed graph Length
Kante Keilförmige Anordnung INTEGRAL Iteration Laufzeit Desire path Supremum Optimum Square Infinity Element (mathematics) Factorization
Kante Trail Shortest path problem Laufzeit Element (mathematics) Rollbewegung Rounding Energie Iteration Optimum Length Limit of a function Directed graph
so genau sind die Änderungen der immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt so hallo
allerseits ich darf Sie herzlich begrüßen für heute wieder wir waren beim letzten Mal stehen geblieben mit dem Thema kürzesten Wege ein Thema das in aus der GDI 2 auf jeden Fall bekannt vorkommen sollte auch teilweise die speziellen Themen die wir hatten wir haben nochmal kurz beispielsweise eine von Deix zu unseren geschaut wissen noch nicht fertig ganz mit dem Algorithmus von der Xtra hier noch mal eine interessante Implementation der Karte Kilo man sich also die 2 und auch hier vom letzten Mal dass die Karte Kilobyte extra einen sehr ein wichtiges Thema ist wichtig für die Laufzeit weil sie ja in jedem Schritt immer eine gibt er gewiss immer dass er den Knoten finden müssen das aktuelles Leben ist natürlich die Distanz wert der kürzeste ist von einem Knoten die bisher noch nicht behandelt worden sind und es verschiedene Möglichkeiten sie haben der es vor die Möglichkeit kennen gelernt mit einem Hieb wir haben die andere Möglichkeit übersprungen die dann natürlich auch nicht Prüfungs- relevant sind was allerdings sicherlich noch mal etwas an und Einsicht freilich ist ist diese Implementation diese prallte Khieu die sich da als in der winterlichen nennt da ja das hat zu tun mit dem englischen Wort oder Ja wählen oder im Sinne von na Telefon wählen oder 3 heißt auch die Wählscheibe der comma noch dazu was hinter dieser Intuition steckt aber zunächst mal machen uns klar die ist was hier steht denn diese Beobachtung sie ändern sich ne in da extra gehen wir in jedem Schritt den man im Schritt einen Knoten in Zug wer den wir den wir vollständig abarbeiten und den der hat die richtigen Distanz wert und der dieser Distanz wird wird im Gespräch noch nie wieder verändert was wir uns klar machen müssen hier ist das diese Distanz Werte die wir permanent setzen in dem wir ein Knoten aus der Partie die rausnehmen und und dann die wieder anfassen seines Tanz wird nie wieder ändern dass diese Distanz Werte nannte Kerry sind also nicht absteigen immer permanent aufsteigend oder mal zufällig gleichbleibend sind warum sie ändern sich an die schöne Bilderchen die viel gezeichnet hatten war zumal ich glaube zu ein bisschen Flüssigkeit wird man so das ist wie üblich und Graf irgendwo in der Mitte vielleicht oder wo auch immer ist unser Staat Noten und wir haben schon eine ganze Menge von Knoten sind und wo mittendrin Wir haben eine ganze Menge Fangquoten endgültig abgearbeitet die sind hier alle drin in dieser Menge und jetzt sehen wir einen 9 Knoten irgendwohin zu das sollte man gut aufgenommen werden ja in einem neuen Kanonen zu und was ist die Aussage dieser beobachten die außer diese Beobachtung ist letztendlich und wenn nicht diese 9 Knoten zu nehmen ich hoffe dass wir uns nicht aufgenommen worden wenn ich jetzt diesen neuen Klonen zunehmend dann ist sein Label nicht kleiner als irgendeines dieser Lebens die vorher schon hinzugenommen worden sind die falschen endgültig abgearbeitet worden sind dass die außer dieser Beobachtung letztendlich niedergebrochen auf den Verlauf des Algorithmus und warum ist das so na ja weg wenn wir umdenken und hier drin wie zum Beispiel der hier einen größeren Distanz wird als der hätte den wir jetzt hier über irgendwie irgendeine kannte hinzunehmen mehr dann ist das ein Widerspruch letztendlich zu zum Fortgang des Algorithmus dann wäre der hier viel früher genommen worden als dieser Knoten hier die Situation wäre gar nicht da dass diese Klonen schon bearbeitet worden ist und in der hier noch nicht in den ja in jedem Schritt immer gehe das kleinste Element ja die Wellenfront hätte es denn hier erreicht bevor sie die nie erreicht hätte also es kann nicht sein und das heißt dass diese Distanz wird hier von diesen 9 Knoten nehmen mindestens so groß sein muss wie der Distanz wird von jedem anderen Knoten das machen erst mal klar dass diese Distanz hatte diese Schlüssel Werte der Partie Khieu wie wir sie wie wir die Elemente nacheinander rauszuholen das ist dass die in aufsteigender Reihenfolge sind so was bringt uns das jetzt im für die Implementation April wird jetzt Warteschlange wir betrachten einen sicherlich nicht ganz realistischen Fall dass die Kantenlängen ganzzahlig sind indische Religion und also ganzzahlig das ist beispielsweise herbei die er bei einem Navi wieder Fall nicht ganz einige Kilometer aber ganzzahlige Vielfache von 100 Metern ja damit rechnen zum Navi oder vielleicht Seite sei es auch Meter ist auch egal denn selbst sind offen zentimetergenau rächen wird es immer noch ganzzahlige Vielfache einer Basiseinheit heißt bei dem Navi haben wir immer diese Situation gegeben denken Sie sich andere Situationen also wenn jetzt Kilometer rechnen wenn jetzt beispielsweise Zeit rechnen haben natürlich ganzzahlige Vielfache der Einheit Sekunde oder wenn sie eine andere Situation denn wie beispielsweise Bahnverkehr dann sie ganzzahlige Vielfache der Basiseinheit Minute ja also es ist jetzt keine wirkliche Einschränkung davon auszugehen dass die Kantenlängen ganzzahlig sind selbst wenn sie das nicht haben Sie es wenn Sie und eine Anwendung haben in der sie wirklich Double Werte haben wo sie wirklich stehen ausnutzen dass sie mit der theoretisch reelle Zahlen modellieren können können Sie wenn Sie unbedingt wollen natürlich mit einem ganz kleinen Rundungsfehler alle diese reellen Zahlen auch in ganzzahlige Vielfache einer sehr kleinen Einheit Zahl umrechnen das geht natürlich also immer also dass es praktisch keine Einschränkung so das ist jetzt die 1. Variante ja die er diese 1. Variante erklärt noch nicht warum das Ganze was mit norwegischer zu tun hat aber die brauchen erstmal mal als Vorbereitung für die zweite die eigentliche Variante was hier steht ist die Beute Kilo ist letztendlich ein aber ab einer gewissen Menge die beginnt mit 0 das soll 0 seinen kein Osterei und endet mit 1 wird er mal sehen was ist sie das ist die der größte vorkommen kann ja denken Sie sich wieder bei einem Navi denken Sie sich die Haare die nicht länger als ganzzahlige Vielfache von 100 Metern was könnte die Lippe der längste Straßenabschnitt seinen Sohn nach wie vor kommt wie lang könnte der sein gut es gibt wahrscheinlich wohl in den alten und wenn wir in Europa sind irgendwo in den Alpen oder sonst irgendwo lange Wegstrecken ohne ab aber ohne Gabelung ohne Kreuzung die vielleicht auch mal wirklich weil sie nicht 20 30 Kilometer langes und vielleicht auch ein bisschen mehr nehme aber an 50 es gibt keine Wegstrecke die länger als 50 Kilometer und das dazwischen eine Kreuzung oder irgendwas ist dann wäre 500 also 50 x x f wurde der 50 Kilometer gleich 500 mal 100 Meter wäre 500 mehr geeignete zur Ostsee so und wichtig
ist dass die Distanz Labels die vorkommen können die Länge von Christen fahren oder überhaupt die Länge von Fahrten ja muss ich mag es so sein dass die Länge von Faden nicht größer sein können als n x C warum Version Farbkanäle höchstens N minus 1 kannten haben wir da keine Züge enthält ja so wir mehr sehen es kann haben muss um und zu enthalten n die Anzahl der Knoten C ist die ist nur Schranke auf der auf der auf der Länge einer kannte ende Snow Schranke für die Anzahl kannten in einem weg also es als sie die eine obere Schranke insgesamt für die Länge eines weg ist das heißt also wir wissen von vorne rein ohne weiter nachzudenken das unsere Distanz Werte über diesen Bereich 0 bis N x 10 sein werden und genau da tragen wir sehen ob wir tragen sie immer wenn wir Distanz wird Delta haben oder ich nehme ne nochmal und anderen wert Kader der war ja die Abkürzung für für die Distanz werde der Einzelknoten das speichern wir in einer Liste der beispielsweise Änderung der Datenstruktur wo wir leicht immer ein beliebiges Element rausnehmen können wie zum Beispiel Minister wo wir das Kopfende man sofort rausnehmen können oder am Kopf so was sprechen können da sprechen wir in jeder Datenstruktur diejenigen ab wo die Distanz Werte Delta des jeweiligen Knotens gleich klar ist das machen wir immer dann wenn wir einen Knoten bei einem bloßen distanziert setzen abtreten schieben wir diesen Knoten von der Liste der vom als von seinem alten Distanz wird ja wir haben Knoten abgebildet von einem kalt sein kann comma das heißt diesen Knoten schieben wir von der jetzigen nächste wurde ist bei K zu der Liste von von Gastrecht Wasser neue Distanz wert ist und da die Labels da die da diese die Welt die wir permanent setzen Dieter in dem es die also von Poltik herausnehmen wollen da die die Krisen sind wie diese Beobachtung sagt da sie monoton wachsend ist das besagt wir können einmal in einem es gern von links nach rechts von 0 bis maximal ehemals sie einmal durch alle wer hat also durch alles Slots durchgehen die Knoten die da drin sind abarbeiten zum 1. Lord gehen und fertig und nie wieder zurückkehren das heißt also wir haben gar nicht diese ganze Problematik sehen sich mit Hip Datenstruktur als Beute Kilo mit dem ganzen umorganisieren und logarithmischer Zeit und so weiter sondern wir gehen ein einziges Mal durch die Bräute Khieu die Knoten die Elemente sind hier gespeichert in diesen Listen und wenn wir einmal über eine bestimmte Slots ein bestimmt Index verlassen haben die Knoten die da drin sind die fassen wir nie wieder an die haben die richtigen Werte das ist die Idee dieser Implementation die gute Idee denn wer weiter das ja da billigend lässt das ist glaube ich Geschmackssache man könnte und es in die Linke lässt mehr nehmen und immer am Anfang der Liste der einspeichern werden wenn ein wenn einen Knoten dahin gehört und das nächste man außen vom Anfang der Liste erleben ich glaube das macht den Unterschied dass das nur schauen wir haben wir gesehen habe ich eben gesagt und das noch mal genau präziser von dem was ich gesagt habe wir gehen einmal von links nach rechts durch das gern im Englischen das gerne das einmal durch oh und wann immer wieder wir fahren mit 0 1 wo und wann immer wieder offen deren Baked stoßen wäre müsste die weiter es gibt dann keine Knoten der dieses Label enthält der diese Distanz wird enthält also gehen wir weiter und so lange bis wir einen Distanz wird ein Index finden der nicht länger als 2 Knoten sind die diesen Distanz wird aktuell haben und da auf auf den Knoten der in diesem backe drin ist wenn wir dann die nächste tration von als an und raus aus der Politik Ju und Bauarbeiten auf die übliche Art und Weise wie es geht immer natürlich in der Algorithmus und da ist es immer derselbe es geht nur darum zu organisieren wie wir immer an den nächsten Knoten ankommen Frage ja vor Vorsicht Vorsicht ich glaube ich muss die Illustration ist mir aufgefallen als sich das gezeichnet dass diese Frage kommen könnte habe ich habe mal abgewartet ob die Frage kommt ich glaube ich muss diese Illustration noch mal ein bisschen anders mache gestalten um das deutlicher zu machen was die Rolle der einzelnen backe zu empfangen Quoten sind so hoch wir stehen jetzt gerade auf diesen bat die Baguettes hierher und es nicht mehr da haben wir mindestens einen Knoten zum Abarbeiten ja den bei ihr was machen wir jetzt was wir jetzt machen ist wir gucken uns alle seine Nachfolger an ja wir konnten uns ein nach seinen Nachfolger einer seiner Nachfolge warten 7 ich muss es ein bisschen deutliche Zeichen einer seiner Nachfolger hat zum Beispiel diese Länge dieser Distanz hat K so was machen wir mit dem Nachfolger die gegebenenfalls unter gewissen Bedingungen ändern wir reduzieren wir diesen Distanz wird von diesen Nachfolger zu einem etwas kürzeren Distanz wird K comma gut so dass wir also hier jetzt vervollständigt das Bild wieder was wir eben hatten so sie sehen hier sind wir gerade das ist das ist der Wert des aktuellen Knotens aus der Beute Jura aus das ist der Wert eines Knotens der Nachfolger ist von dem aktuellen Knoten und von dem ändern wie er den Distanz wert von K auf comma glaube es wird das Bild etwas klar für einen genau einen Knoten vielleicht würde ich das noch mal wissen rechnen kann einen Knoten der Nachfolger ist von dem aktuellen Knoten den fügen wir an Frage dem so wie es jetzt gezeichnet habe brauchen wir doppelt verlinkt Listen ach so ja stimmt Sie haben Recht es hat schon seinen Sinn warum es doppelt verketteten Listen sind damit wir nämlich hier aus dem aus dieser Liste sehr bequem das Franken stimmt dass ein guter Hinweis also ich korrigiere das was ich gesagt habe doppelt verketteten Listen sind essentielle für die Laufzeit diese Implementation Fendant ist wie seit geraumer ich die Vorlesung vor vom stellen sich nicht nicht genau was ich bezahlt werden dafür für die für die Nachwelt das alles aufgenommen gut gibt es das ganz konkret hier noch weitere fragen wenn ich den Kommerz zu der eigentlichen ab
Update Operation also zunächst noch mal was Sie eben gesagt haben an dem man sich einen Distanz wird ändert ich hab's hier Kalkanstrich genannt hier auf der Folie ist von D 1 nach die 2 genannt so die Laufzeit muss man sich nochmal mal überlegen wir fassen jede kann einmal an befassen natürlich jeden Knoten einmal an aber die Laufzeit um in einen Knoten anzufassen ist natürlich in dem Ende Mai 10 den 2. Summanden da drin das Oma nicht nochmal extra aufzuschreiben und wir gehen einmal die ganze denn wer diesen backe durch das dessen Länge asymptotisch in Waldsee ist das ist die Laufzeit dafür ist vorteilhaft wenn das Großzeh keinen allzu großen Wert Internet so dass in Waldsee vielleicht gegenüber dem nicht allzu groß ins Gewicht fällt idealerweise sogar kleiner ist als die Zahl beziehen überschaubar wir haben eben in den Fall 50 Kilometer ist die längste Strecke in Granularität 100 Meter wäre C 500 das ist sicherlich etwas womit man gut leben kann wenn man das ganze europäische stehen das Streckennetz er als Grafen dazu so und jetzt gehen wir einen Schritt weiter die nächste auf
Beobachtung in wir konnten wir haben ja im Prinzip bei den noch nicht bearbeiteten wurden eine Zweiteilung 2. eine Zweiklassengesellschaft diejenigen die noch den wird unendlich haben weil sie noch nie berührt worden sind das kann man wenn man will noch im als weiteren und backe zu realisieren oder wie auch immer die haben jetzt in dieser in diesen aber nicht drin und diejenigen die einen endlichen wird haben und die Aussage die hier steht können wir uns noch mal an dem an dem Bild denke ich deutlich machen wenn sie wenn wir uns was sagt dieses diese Beobachtung Nummer 13 jetzt ganz konkret in diesem Bild so wir sind jetzt in einer Iteration in der dieser Knoten ja das ist Frau auf der Folie in der dieser Knoten hier permanent Gerede von den entzogen und wurde zu der Menge aller abgearbeiteten Knoten so und diese Beobachtung sagt etwas aus über die Knoten die noch nicht abgearbeitet sind aber nicht mehr Distanz wird unendlich haben sondern endlich ist dann sagt was heißt das das heißt das ist mindestens eine Karte jeweils hier raus geht unter Umständen mehr als eine Kante zu jedem dieser Knoten ja über diese Knoten sagt diese Beobachtung etwas aus und was sagt sie über diese Knoten aus sie sagt aus das dieser Distanz wert die diese Kloten momentan hat und in der nie wieder überschreiten wird so weil das dann immer Wissens kleiner werden dass diese Distanz wert zu diesem Distanz wird nicht allzu viel größer sein kann nämlich der Unterschied kann höchstens 10 sein bis QSC warum das ist ganz einfach sie ändern sich die folgende Beobachtung war dass die Distanz Werte in aufsteigender Reihenfolge permanent werden so das heißt also der hier dieser Knoten hier hatte wird das habe ihm schon mal gesagt kann höchstens so hohen Distanz haben wieder hier nicht Schüler der hier können kleinere distanziert haben als der oder gleich großen das bedeutet für den Knoten wie ich hier oben wir mit wie es auf der Folie bezeichnet dieser Distanz wird ist kleiner gleich diesen mal plus Länge der kannte höchstens C kommt es genau in dieser Distanz wird hier wenn ich das jetzt hier mit diesem Klon ich hoffe es kann auch sehen ich mache das mal einer anderen Stelle hier ist das Sie hier Knoten und jetzt diese kannte der Distanz wertvoll ist kleiner gleich dem Distanz wird von Frau und der Distanz wertvollen W ist kleiner gleich das ganz wertvollen von plus Länge der kannte warum abgeschätzt sie und damit steht schon da ja ich muss hier nur noch für viele V einsetzen und dann stellt ist da das bedeutet für unsere Implementationen das alles wo wirklich was passiert ein sehr kleiner Abschnitt dieses aber es ist nämlich mit einer Länge die höchstens ich will mich jetzt nicht um 1 vertun um es mit einer Länge die höchstens 10 plus 1 ist ja außerhalb des Bereichs haben noch nicht alle Knoten die außer dieses Bereichs und habe noch in unendlichen mehr das hat diese Beobachtung angewandt auf diese Implementation und weil das so ist weil es nur diesen Abschnitt weil immer zu jedem Zeitpunkt nur so ein kleines Fenster der Länge C plus 1 von diesen ganzen Risiken bei benutzt wird kann man jetzt kommen wir zu 3 zu viel Scheibe kann man sich das Ganze auch diesen ließen aber ja auch sparen und nur ein aber jeder Sänger Zyklus 1 anlegen so und ihnen behandeln mit einer modulo Operation wir haben also die Indizes von 0 nach C das passt wunderbar mit 0 als 1. Index und ihn behandeln als er zyklisch hier Index 0 hier sind C zyklische Behandlung heißt einfach modulo Rechnung ja in dem Moment wie wir wenn wir alles weitergehen wenn wir einen einen Pointer ein 2. setzen dann welche mir immer noch mal modulo c plus 1 müsste man da rechnen Modulor c plus 1 und das bedeutet wenn ein Index am Ende angekommen ist und ein 1. Schritt macht dass er wieder bei 0 und das kann man sich veranschaulichen auf die Art und Weise da Intervention der Wählscheibe sieht irgendwie so ein bisschen so aus das heißt also wir haben hier den Index laufen irgendwo steht jetzt gerade die den ersten Sachen kommen wir kommen hier und wir wissen dass der ganze interessante Bereiche dennoch kommt vor diesem Index dass der hier rechtzeitig ändert weil nur dieses Fenster der Länge C plus 1 überhaupt bestückt ist mit mit in hat Stunde Guide oder kann man sich auch als für andere Zwecke durchaus aber durchaus mal mal merken wann immer es geht sie irgendwie was durchs kennen den das das lässt sich sicherlich aber ich bin mir sicher aber ich weiß lässt sich beispielsweise auch auf der Situation in der Geometrie anwenden wo sie irgendwas von links nach rechts durchs kennen und wo sie immer eben nur ein Fenster von einer gewissen Breite haben und denken Sie genauso modulo rechnen gut damit das ist das noch mal was wir ihm gesagt
haben wir gucken uns noch ein paar Beschleunigungstechnik ihn an alle Termine ethischen ist das einfachste was sich eigentlich von selbst versteht wenn man so dass wir mit dir im Normalfall will man ja nicht sehr wie wie eigentlich extra vorgesehen hat von einem sollen anderen die Distanznahme Normalfall wenn man von einem starten und so einen Zyklus mehr Beispiel na wie Sie wollen von Darmstadt hier irgendwo Karolinenplatz meinetwegen zu fragen sollte einen zu einem Platz dorthin fahren ja und Sie haben jetzt Kartenmaterial in ihrem Navisystem drin das bis nach Wladiwostok bis nach Lissabon bis nach Kapstadt reicht was sie natürlich nicht möchten ist dass der Algorithmus erst einmal dieses gesamte Kartenmaterial durchgeht bis Wladiwostok oder sogar noch weiter da unten Singapur oder so was und so das letzte in das was man trockenen Fußes erreichen kann und Kapstadt dann in südlicher Richtung dass das alles durchlaufen wird wenn sie ja eigentlich nur von Darmstadt nach Frankfurt wo er das will man ja nicht also erinnern wir uns daran wenn wir so eine geometrische Situation haben die beim Navi dann ist die Intuition gar nicht mal so falsch das da extra sich ausbreitet von seinem Staat Knoten aus wieso Wellenfront Erwin Stein man ins Wasser wirft also das soll dir ein bisschen sollte gar nicht so elliptisch sein wie es jetzt aussieht ja und wenn Sie jetzt hier Frankfurt erreicht haben und Frankfurt gehört also der der Punkt in Frankfurt den Sie einstellen möchten und dieser Punkt ist jetzt permanent benebelt gehört zu der Menge der abgearbeiteten können Schluss machen weil sie sämtliche an dann kann der gar interessiert das ist die 1. einfache Beschleunigungstechnik das wir aber in in dem Moment beenden können wenn der Ziele Knoten er fertig abgearbeitet ist ändert natürlich nichts an der an der SGS Komplexität im schlimmsten Fall kann es ja sein dass sie wirklich nach Kapstadt war Singapur wollen und wenn Sie nach Singapur wollen dann müssen Sie schon andere Techniken implementieren damit der ihn nicht auch noch als ganz Afrika bis Kapstadt und damit mit berechnet so wie die Gerichte Besucher ich glaube da gehen wir erst einmal zum Bild damit das
klar wird das ist die normale Suche längst Standard ein bisschen an ausgezeichnet als ich aber im Prinzip dieser man hat so einen werden von diesen Einrichtungen Reich ausbreitet das ist natürlich nur ein Bild was nicht in jeder Situation stimmt aber so im geografischen Anwendungen ist das Bild gehörenden typischerweise gar Auffaltung bidirektionale Suche ist die DEG hier sehen Sie S und T wir gehen von beiden Seiten gleichzeitig immer starten von beiden Seiten eine Suche so was passiert dann die Nummer 1
zurück wir haben wir haben ihn so jetzt das kann ich jetzt eigentlich hier schön zeichnen wie mir es und wir haben jetzt und wir haben hier gleichzeitig also in jeder Iteration von der Xtra einmal links und einmal rechts ein Schritt so kann man sich das vorstellt es ist auch egal sie können auch sagen in jeder Iteration ab zweimal links und einmal rechts oder wie auch immer es kommt aufs selbe raus so und irgendwann treffen wie die beiden sich mal auch machen so so die beiden treffen sich jetzt umso Handlungen Club mal gemeinsam der sowohl von links als auch von rechts permanent geregelt ist und dann hat dieser Algorithmus auf warum hat der jetzt auf oder was was genau passiert dann in dem Moment der Knoten den wir jetzt hier eingezeichnet haben meist auf der Folie W so jetzt ein ganz heißer Kandidat für kürzeste Fahrrad ist natürlich der kürzeste fort von es war W in der ein Summe plus der kürzeste Wort Fahrt von Wien nach des hier aber natürlich alle Kanten rückwärts genommen bei der zweiten suche ich vergessen zu sagen logische kannten alle in umgekehrter Richtung so ein heißer Kandidat für den kürzesten Weg von Essen nach T ist also der kürzeste Weg von Essen nach W in der suche komme getingelt mit den kürzesten Weg von Wien nach T in suche muss aber nicht unbedingt der kürzeste Weg sein es kann auch noch andere Situationen geben das steht hier auf der Folie einer der ich sage 1. Mal bevor ich dazu komme was es noch für eine Situation geben kann was noch der an an an der Küste Verfall ist vielleicht erst einmal was nicht sein kann was kein Christoph Fortner sein kann dazu würde ich mal sagen sollte ich noch mal einen neu ist bezeichnen so wenn wir jetzt von erst starten und die eine Wellenfront haben wir werden das wir wieder und wir haben die anderen Freund beide haben sich jetzt hier berührt was sicherlich keine kürzeste Weg mehr sein kann ist irgendwas was sowie zu Sonnenglut mir vielleicht und hier zu den Knoten der von beiden nicht berührt worden ist und hier lang weitergeht warum kann das kein kürzeste Weg sein weil dieser Knoten nicht immer wie gestrichen einer die Distanz zu S bei dieser Knoten sehr vor wie genommen wurde kann die Distanz von Essen nach wie strich nur größer gleich das ist davon ist noch wie sein und gleichzeitig mit dem selben Argument Wesen der Männer völlig widersinnig 7 Resolution kann dieses dann von strich nach höchsten sogor mindestens sie müssen so groß sein wie die von den 8. weil wir hier wie benommen haben in dieser tration unwichtig ist noch weit draußen und natürlich kann man das weiter argumentieren irdene Situation wo ich hier viele Knoten noch sind außerhalb des Bereichs können alle nicht sein was aber noch sein können und was man tatsächlich nicht ausschließen kann was tatsächlich richtig sein kann ist sind 2 Knoten die hier mit einer Kante verbunden sind diese dieser Bereich hier ja da geht dieses Argument das ich eben gebracht habe ich viel für sich spricht natürlich nicht und das kann auch tatsächlich sein das wir ein Spiel das nicht dass hier das kürzeste ist der Weg über W sondern der Weg über diese kannte von S nach T das macht aber nichts weil wir haben ja diese diese Situation genau in der Hand die er natürlich können wir uns alle kannten angucken deren Start Knoten in der ein suchen Menge drin ist schon abgearbeitet und deren entluden an suche Menge schon abgearbeitet und dann kommen wir uns an ist das hier der kürzeste Weg über über das W oder ist das ist einer von einer von diesen Konstruktion der kürzeste Weg haben wir die regierende müssen die gar nicht groß suchen alle kannten deren deren Staat Noten in der Regenmenge und deren Knoten in der rechten Menge ist sind noch keine Daten und daraus aus aus und das sagt dieser letzte gezeigte dash ist entweder der Pfad von plus den Pfad wie nach die oder ein Fahrrad der über eine Kante vor wenn einzelne kannte von der Linken so Menge zur Rechten so Menge sprengt so auch hier wieder das diese Beschleunigungstechnik aber nicht in Bezug auf asymptotische Komplexität also methodisch komplex ist ist natürlich weiterhin die selber er war das funktioniert natürlich schneller wenn sich das hier ansehen ja was wenn sie nur von einem der beiden Knoten von S 0 losgegangen wären was hätten Sie denn dann den hätten sie einen so großen Bereich abgesucht ja einen viel viel Grün ein zwar nur einen Zirkel hätten sie abgesondert ein Kreis aber der wir viel viel größer gewesen wenn ich wieder dieses Bild beanspruche diese Fläche von diesem einen Kreis wir natürlich viel viel größer als diese beiden Flächen zusammengenommen und deshalb ist es in der Praxis tatsächlich eine gute Beschleunigungstechnik so
zielorientierte Suche ist noch was Interessantes das habe ich hatte ich Energie 2 letztes Semester gebracht aber ich glaube in früheren Semestern wurde wo das behandelt Golduhr da wirkte zur Hadsch der Ziele und jede Suche bei der geht 2 mal nicht oder nicht okay dann als sich das hier so die Intuitionen hier nochmal konzentrische Kreise ja sie werden da Extras wie in Stein in sie werfen und die Wellenfront breitet sich in eine Richtung gleichmäßig aus das Intuition und des Edition hinter zielgerichteter Suche ist mehr sie haben es irgendwo Sie haben hier irgendwo T und Sie wollen jetzt diese Kreise verfälschen sie wollen diese Kreise zuletzt machen das heißt also anstatt hier konzentrisch geht's weiter ich mache Mannesmann wissen doch man die Mitte so anstatt es hier konzentrisch auseinander geht wollen Sie mehr wollen Sie solche ersetzen haben die sich sehr sehr sehr viel langsamer nach links weg von Teddy aus ausbreiten als zu tätigen mit dem offensichtlichen Ergebnis dass sie weniger Knoten wir berühren müssen bearbeiten müssen um zu T zu kommen das Idee was wie kommt man dahin der Gedanke ist der dass man an den Kantenlängen manipuliert sie haben hier irgendwo wieder S sie haben ihren Hotel und sie haben und welche kannten zum Beispiel um dem Grafen eine Kante von Frauen nach wie die Idee ist die kann man so zu manipulieren dass eine kannte die tendenziell in Richtung T zeigt koch gekürzt wird also die Kantenlänge reduziert sich und eine Kante die tendenziell natürlich nicht hundertprozentig genau aber tendenziell in Richtung es zeigt so wie das hier angedeutet habe dass diese Kantenlänge verlängert wird und kannten die neutral sind zum Beispiel die so genau orthogonal zur zum weg von es nach T sind die würden dann auch nur zu da würde sich nichts ändern das ist die Idee die Frage ist wie kriegen wir das hin wie können wir die Kantenlänge so ändern das wir dann da extra hinterher anwenden können nicht vergessen nicht negative Kantenlängen es darf keine Kantenlänge negativ werden durch diese Manipulation und das Ganze macht natürlich nur Sinn wenn wir mit diesen manipulierten Kantenlängen wenn wir dank ausgehen dass das natürlich auch in Kürze ist der Weg für die ursprünglichen Kantenlängen ist er noch natürlich keinen Sinn wenn wir da irgendwie irgendwann völlig anderes Ergebnis rauskriegen so wie kriegen wir das jetzt sehen überraschend einfach wir nehmen wir bereits wieder für jeden Knoten berechnen wir eine untere Schranke für für die Weglänge die man von O bis T braucht das im in geografischen Bereich ganz einfach Seminare der kritische Distanz die Kanten er kürzer kann die Weglänge nicht sein oder wenn sie Fahrminuten hernehmen als als Sekretär und nicht Distanz er nicht nicht geometrische Distanz dann müssen Sie halt gucken wir eine ordentliche untere Schranke dafür wie viele wie viel Minimum 1 1 die Fahne die Fahrt von danach dann kostet ja so indem sie zum Beispiel auch die die in die örtliche distanzieren und sich Tempo 100 und Tempo 130 an also ich stelle sich vor sie haben Autobahn mit Tempo 130 wenn Sie nicht alles einstellen sehr 130 die Geschwindigkeit die dass das Navi zugrunde legt typischerweise wenn sie wenn sie auf der Autobahn fahren nicht mit mit unbeschränkter also ohne Tempolimit Fan also Sinne in dem mag also schon gern in dieses da die die Gewehre der klinische Distanz mit Tempo 130 dann ist das mit Sicherheit Unterschrank immer ganz natürlich noch intelligenter die Unterschale hochtreiben immer man sie hochtreibt um so umso besser funktioniert so aber zum untere Schranke haben wir und wir wollen das dass der voll ist das was hier steht ist letztendlich die Dreiecksungleichung die Sie aus der Mathematik können also natürlich nur eine spezifische Situation der allgemein Gleichung denn was wenn ich diese verschiedene Werte x mal ab trage nehmen wir an den wirklich die die euklidische Distanzen es dann sehr das am einfachsten sichtbar wir haben eine Kante wollen einem Knoten zu einem Knoten V hier Name wird T ja und wir haben die die Streckenlänge die Züge und hier die Streckenlänge der BVT dann sehen Sie und und diese kann dann natürlich die länger C O V unsere vom als abgetragen was in dieser Formel drin ist und Sie sehen natürlich sofort hier dann der 3 Ungleichung das nicht da muss gesagt wird als das diese länger kleiner gleich dieser Länge plus die ist ja also wenn Sie zum Beispiel das hier als geometrische dass sie es wirklich das Verfahren das wirklich ist also wirkliche Distanz als einfachstes Beispiel dann ist das unmittelbar einsichtig so was wir jetzt machen ist es habe ich dieses Bild dummerweise gelöscht ja vielleicht zahle ich das Bild noch mal an was wir machen ist sie ändern sich eben hier ist es jetzt lebt und dem es verschiedene Situationen für die Kanten von Frau nach W und die haben wir die genannt ja man sie von nachfolgenden auf der Folie soll dich konsistent sein einmal so und einmal so von Ihnen noch Frau oder neutral von und nach Frau diese 3 Fälle so diese hier besagt die neue
Neulinge Zielstrich von dieser kannte ist die alte Länge verrechnet mit den beiden Distanzen diesen Wein unterschreibenden B U T und BVT und man sich das mal genau angucken Biotech steht Minus BVT steht im Plus das heißt also wenn die Keimzelle hinzeigt zu C wenn also die Distanz von Frau nach die diese untere Schranke kleiner ist als Distanz von und nach des dann reduziert sich das tatsächlich Horst lesen dann reduziert sich das tatsächlich dieser wird ist größer als der ist die so dass insgesamt negativ wenn hingegen die kann der weg zeigt dann ist der positive Term größer als der negative Terni Kanther bleibt gleich und den neutralen Fall dass beide B Werte gleich sind dann ändert sich nichts es in den neuen kann man die alten kann wenn es genau das erreicht warum ist das jetzt der warum können jetzt damit einfach einschl mit diesen Zielstrich anstelle der C arbeiten warum die also die Behauptung ist wenn ich jetzt die Kantenlängen just Michigan in C durch die neuen kann es nicht durch ersetze und ich krieg dann ist Weg raus dann ist die Weglänge vielleicht noch verkehrt aber der Weg ist der richtige der Weg den ich aus kriege warum ist das so wir betrachten mal irgendein Fahrt von Essen nach nicht mal ganz kurz spielen ob ich diese Formel ja es ist nur es ist nur angedeutet ich würde es mal richtig machen Jugend wir betrachten von Essen nach T es sage ich soll gleich vor sein der 1. Knoten das ist V 2 der zweite Knoten das ist vor 3 der 3. Knoten können beliebiger wechseln sein kann auch Umwege machen ist vollkommen egal vor 5 und so weiter bis zu einem Knoten vorkam minus 1 und dann zum Knoten V ok gleichziehen ja das ist die Wände dieses vor das in Bezug auf die 9 Kantenlänge ich mache das vielleicht ein kleines bisschen wenn der exzentrische und damit man da noch ein bisschen was sehen kann so auf 4 period vor 5 und geht es bis dahin Änderung so was ist die länger dieses vor dass das ist die Summe die gleich 1 bis K minus 1 vor dem Zielstrich neue Wege länger Frau war von 1 V V E plus 1 er ist die neue Weg länger dieses Weges lesen okay ja ich habe einfach über das habe habe ich initiiert Indiz indizierten ich induziert so dass ich das einmal so hinschreiben kann so das kann ich jetzt auseinander dröseln so wie ich die Zielstrich definiert habe gleich 1 bis Graber minus 1 c VII VI plus 1 und da kommt jetzt noch etwas hinzu im Minus ich nochmal gucken wir bundesweit falsch mache erst das 1. Start Knoten also W V I T bloß nicht immer damit das gut aufgenommen werden kann und muss ich das die nächste Zeile bringen sonst klappt das mit der Kamera Bereich nicht so das ist gleich der Summe gleich 1 bis kaum minus 1 wieder von C VIII comma V I plus 1 minus B Frau ihr Ziel bloß W plus 1 Themen ja einfach nur die Definition der neuen könnten den Zielstrich eingesetzt auch nicht richtig so jetzt kommen sich dass man jeder dieser bewährte fast jeder dieser B werde kommt zweimal vor einmal positiv vorzeichnet einmal negatives Vorzeichen das ist grob Sommer falls Sie diesen Begriff in der in der Mathematik gehört haben Teleskop heißt und dass die Liebe zum dahinter ist dass man die ganze Summe er so Riesenteleskop zu einem einzigen Lied zusammen drücken kann und genau das passiert hier das einzige was hier nur einmal vorkommt ist weil es und bald die das heißt dass alles was hier steht reduziert sich auf die gleich 1 bis K A minus 1 von den ursprünglichen kosten werden ja das ist die und das was sie hier steht jetzt ist die ursprüngliche Weglänge nach wurde die Weglänge des Vaters nach den ursprünglichen kosten minus P von Erz Termine plus B die 10 alles andere fallen weg weil jedes andere B geht einmal mit positiven einmal mit er den vorzurechen vorkommt ist dass die Idee einer Teleskop zumal alle diese wieder hier zu einem einzigen sieht zusammengeschoben das hier ist aber konstant das hängt nicht vom Weg ab das entscheidende Punkte sind diese konnte dieser dieser und der Unterschied zwischen der ursprünglichen Frage Farbklänge hier und der neuen falls hier ist dieser Konstante Term den ich von verringern geht das bedeutet ein kürzester Fahrt nach 9 Pferdelängen ist zugleich in Christa Fahrt nach alten Fahrradwegen weil wenn 2. wenn 2 Fall wenn Einfalt hier kleiner als kürzer als andere Fahrt ist es auch hier kürzer als an und Fahrt weil sie bei weil sie sich jeweils nur um diesen konstante unterscheiden und damit haben unser Ziel erreicht haben diese Beschleunigungstechnik fertig so schön oder so die Distanz Werte sind dann haben natürlich etwas anderen wird also die Länge die rauskommt ist nicht korrekt aber Sie sehen ja die Länge der rauskommt hier als Christ sofort länger wenn sie diesen Term davon abziehen kriegen sie ursprüngliche Länge wieder aus so das nächste
Arsch also hier sehen Sie noch mal ne Intuition wie das aussehen kann statt der Xtra wie hier ganz normal möglichst schon in diese Richtung möglichst in die Richtung von Tag gehen
erstellen lassen wir aus das ist ungefähr derselbe nun kleines bisschen
komplizierter brauchen wir jetzt hier nicht zu betrachten zumal er Sternen durch aus in der Literatur unterschiedlich definiert also verschiedene Algorithmen wenn man begriff er Sternen Hand aber noch hier ein interessanter Punkt den man sich auch merken kann bringt versetzt sind ich sage Ihnen einfach mal mit der Zeichnung was sie auf dieser Folie steht oder ein Beispiel dafür was man sich darunter vorstellen kann das eine Möglichkeit wie man da an das auf dieser Folie also Beschleunigungstechnik realisieren kann ist die wir sind jetzt wieder wir bei der Situation das wir von Essen nach die wollen aber wir betrachten jetzt mal die Situation allgemeiner wir haben bekannter die die verlogenen Knoten aus hier ist und wo es und die geht jetzt irgendwo hin und das in diesem Krieg durch das Info ab da rechnen ist eine Knoten in von der wir sicher sind nur kann ohne dieser Knoten nur bei Knoten in dieser Knoten Menge wenn wir die suchen warum diese kann der überhaupt anzufassen also wir sind jetzt in einem Szenario wo nicht eine Suche machen von es zu einem T sondern zu vielen T ist vielleicht nach nach und wir wissen nicht vorher zu welchen Tier das jemals ist so eine Möglichkeit zum Beispiel ist dass wir versuchen den Sinn von die von den dem geografischen Bereich sind wenn wir in einem gehe gegraben weißen dass wir versuchen diesen Sektor hier einen Sektor zu berechnen Vorabend Preprocessing so dass alle Knoten W zu den der kürzeste Weg von vorn nach wie über diese kann läuft in diesem Sektor sind das heißt also alle Knoten hyphen die nicht in diesem Sektor sind von den wissen wir der kürzeste Weg von Frau zu diesem wie Strich wird nicht über diese kann gehen sondern über eine anerkannte es uns egal welche aber definitiv nicht über diese kannte ja das kann man ja leicht brechen wir brechen vorher vorher im Preprocessing alle kürzesten Wege mal und da wissen wir ja von welcher dieser kürzesten Wege die sie kannte benutzen welche die nicht benutze es müssen aufwendig Abend Reprocessing stört das nicht unbedingt Jahr Reprocessing er macht es nicht aus wenn es mal 4 Wochen durchrechnet vorausgesetzt dass dann das dann im im tatsächlichen Ablauf dann wenn es darum geht dann die suchen deutlich beschleunigt werden kann dadurch so das heißt also wenn wir diesen Kloten voraus sind dann gucken wir uns jede kann und wir wollen das wir bei den kürzesten Weg hier wenn das x-te unter strich und wir wollen Christen Wege zu diesem T 4 oder zu irgend nen Knoten finden da kommen wir uns alle Kanten an die von vorausgehen und die Call und zu diese kann da haben wir uns die beiden Winkel gemerkt die dieser Sektor hier in diesem Sektor aufsparen und wenn das die das versuchen in diesem Sektor ist was sehr leicht mit mit dem bisschen Geometrie zu Hause zu bekommen müssen müssen Trigonometrie dann nehmen wir diese kann den zu wenn aber so wie hier dieses Tisch durch Auswahl dieses Sektors ist dann vergessen wir diese Kanther und haben damit die weitere Suche von dieser könnte aus gespart ja welchen period also die Frage war für die Nachwelt die Frage weil viel sieht man das welch der Version gesunken erfolgt und zurück wie man sich diesen Sektor also an jeder ein jeder kann da haben Sie die beiden Winkel als Attribute irgendwie dran ja Sie an die Karte und die Attribute zum Beispiel dran Graf GOG geometrisches ein Beispiel wie wir kommen wie können kommen gleich nur Zufall Meinung wenn es im geometrischen Bereich sind im März auf auf einer Fläche sind auf einer auf einer ebenen wie zum Beispiel der Erdoberfläche okay die das flache ich weiß am Abend wenn wenn wir merken zu dieser kannte die beiden dazu und wenn wir jetzt von T haben auch die Koordinaten der Nicole die
werden von fordern die Kundendaten von T und dann kann man natürlich mit einfachster Schulmathematik berechnen ob die in diesem Sektor drin ist von von Frau als es als Nullpunkt als Referenz period mit diesen beiden mit Winkel oder so wie dieses die Strich ob es nicht drin ist und dementsprechend die Entscheidung so das kann man natürlich auf allgemeinen es schon aber ist die Menge von Knoten die ich eben mir also vielleicht umgekehrt das heißt natürlich nicht das jeder Knoten zu ja das da der kürzeste Weg über diese Kante geht es kann auch Knoten geben C die sind in diesem Sektor aber geht nicht über die Siege in diese Küsse geht nicht über diese erkannte dann haben wir halt so viel Arbeit gemacht ja ich meine dieser Sektor mit aufgespannt hier und wussten Knoten von dem wir wissen dass der kürzeste Weg von Folge sie kannte geht und hier und wussten Knoten von dem wir wissen dass über diese keine geht und man das die beiden extremsten sind dann die wenigen die beiden Sektor doch aber da kann natürlich auch Knoten sein wo der kürzeste Weg anders verläuft so dass wir dann also diese Kante umsonst mit reingenommen haben die Suche so wie es von A ist die Menge aller Knoten so das des in so dass der kürzeste Pfad diese kannte benutzt wiedersehen gezeichnet habe dieses Ziel von dieser Container der es von A enthält das wäre in meinen geometrischen Beispiel hier die Menge aller Knoten die in diesem Sektor drin sind wie gesagt das ist potenzielle echte Obermenge weil auch Knoten in diesem Sektor geben kann für diese nicht wichtig ist aber das kann man nicht ausschließen das Gericht weiter auseinander differenzieren so wir brauchen den Algorithmus nur weiterzuführen von erkannte aber aus in die in die Richtung 10 Knoten wenn der Knoten werden wenn erzielt würden den wir haben wollen in diesem konnte da drin ist der eine Obermenge ist von der Menge der Knoten für die diese kannte er wichtig ist wichtig ist natürlich und dafür war dass es immer ein Beispiel des mehrere Beispiele dass dieses enthalten sein effizient getestet werden kann und dass man die Art und Weise wie meine konnte der Sprecher dass ist nicht so viel Speicherplatz kostet das ist in diesem Falle in dieser konkrete einer konkreten Anwendungsszenario gegeben man kann sehr effizient testen ob die im Sektor oder die steht nicht im Sektor drin ist und der Aufwand und das zu speichern diesen Container das ist einfach für jede kannte diese beiden sinke das gar nicht so hier ist noch eine andere Falle die die Baronin Box von es von also wenn man hier in der diese wieder diese frühe steckt offenbar eine andere Vorstellung als das was ich jetzt hier eben skizziert hatte wie man das machen kann das kann nämlich was hinter der Folie steht ist die Vorstellung sie haben wir die Kante V ja so und wir haben es hier irgendwo die Knoten intensive dem natürlich werden wenn die Krone Menge nicht leer ist die Knoten die wir und Frau aus und diese könnte wichtig ist Anfang des Weges von Forst und kürzesten Weg zu diesem Knoten und was hier vorgeschlagen wird auf der Folie ist dass man hier folgen die Bauern den werden das ist nicht nicht umhin die rechteckige gewonnen wird sondern zum Beispiel die echte bauen in Borgs also die konvexe Hülle oder auch als Bonnie Box ist eigentlich eher die rechtwinklige das kleinste Rechteck was alle diese Knoten fast das es ist natürlich auch ein bisschen unscharf wäre kann natürlich noch irgendwelche Klo sein noch hier können wir die Knoten und sein die nicht diese Kante benötigen aber ist der Preis den man zahlen muss genaue Trennschärfe wird man in der Regel nicht bekommen so und die Auswahl ist wieder dass man da zum ernsthaften Beschleunigung kommen kann empirisch also nicht mehr mathematisch sondern meine Dementis und umgeschaut was passiert so
letzte erst wieder ab wichtiges hier nur angedeutet darüber kann meine ganze Vorlesung halten über dieses Speed ab Techniken wenn Sie die er von irgend Funktionen einer period wollen von Darmstadt beispielsweise sagen wir zu lohnen period in Schleswig-Holstein weit weit weg vielleicht Flensburg oder so oder was auch immer dann ist ja das im Normalfall so das sehe dass sie erst mal mit einer ganz kleinen untergeordneten Straße starten sondern mittlere Straße weiter noch übergeordnete Straße vielleicht schon Autobahnen dann bleiben sie auf der Autobahn bis sie dann kurz vor dem Ziel wieder auf mehr Straße von mittlerer Ordnung Bundesstraße oder so was gehen und dann und dann und dann die kleine sei eine kleine Sackgasse reinfahren wohl wo ihr Ziel Ort ist also eine ganz untergeordnete Straßen nicht so so eine so eine hierarchische zuwege typischerweise hierarchisch sein wenn sie das vielleicht auch im er mit Bahnverkehr betrachten die typische Situation ist sie steigen er sich steigenden Bummelzug 1 dann vielleicht in einer Region was nicht mit der Interregio oder was dann den ICE und dann wieder wieder das ganze zurück stimmt nicht immer eine schöne schlagendes Beispiel ist Paris wo sie an einem Bahnhof ankommen damit der Mittwoch weiter fahren und dann am anderen Ohr aber nur wieder weiterfahren können sie aber auch in Deutschland haben Sie wollen beispielsweise von Damenstart wo wollen wir hin nach Offenburg oder Solf oder Freiburg so etwas dann fahren Sie bis Heidelberg sind viele verbinden die vorgeschlagen werden so bis Heidelberg fand in den ICE dann fahren Sie mit der S-Bahn mit der S 3 nach Karlsruhe und dann fahren Sie mit dem ICE oder IC weder weiter bis Freiburg ja also stimmt nicht ganz aber so ungefähr die die Idee ist dass man das das gesamte Straßennetz oder Bahnnetz oder was auch immer zerlegt in verschiedenen Hierarchiestufen und dass man das man von das man dann versucht solche Wege zu konstruieren erst untergeordnete Wege im lokalen Bereich dann rauf auf die Autobahn und ab bis Flensburg und das in Flensburg wieder runter ja Problematik hier ist wenn Sie hier zum Beispiel den Bereich starten haben Sie mindestens 2 Anschlussstellen einerseits Darmstadt mit ein Ansatz über Stadt und wenn sie im Bereich starten und wie hier könnten Sie noch die dritte hier vielleicht Interesse kann noch interessant sein da oben das ist das da oben ist auch egal sie wissen wir Weiterstadt ja genau oder Sie stellen sich das mit der Bahn vor sich er sich das mit der Bahn vor sie für Sie bitte aber Sie beginnen mit einem Boden erst dem Fußweg als und das geordnete Art der Verbindung dann mit Namen Straßenbahn oder Bus dann mit der DB und an dem Ziel Ort steigen sie wieder in den Nahverkehr um da haben Sie da muss dann der Algorithmus damit klar kommen das auch von Darmstadt aus nicht den einen natürlichen Startbahnhof von DB gibt das kann der Hauptbahnhof sein es kann der Nordbahnhof seines kann Ostbahnhof es kann auch der Südbahnhof sein er alle diese Möglichkeiten gibt es gut da ich jetzt nicht weiter darauf eingehen ich will nur dass Sie das Sie das mal gesehen haben so ist gering und wir ein das
sehen Sie da mal irgendwelche Rechenoperationen sehen hier die die Zeit die CPU-Zeit und hier die Anzahl der Polti-Team Schritte kann also wie schnell die
einzelnen Algorithmen sind hängt natürlich sehr stark von Implementation ab und wie wo und von Qiu Link von der Programmiersprache von der Mondphase und was auch immer so wenn der korrekt dient
also werden muss aber schon mal gesehen die
E Grundoperationen ist dieselbe wie bei der Xtra das ist das ist die gemeinsame Basis von 3 extra beim Antwort von war schon was immer sie mir geht's so gesehen haben dabei sind über alle selber sie gucken sich eine kann an und wenn momentan ist das wert dass sie für uns dieser kann größer ist als momentane Distanz wird der Staat und sie kannte plus Länge der kannte dann setzen sie entsprechend diesen Distanz runter warum das hier ist die Länge eines vor das DEU plus länger der kann von und nach Frau das ist die Länge eines Fahrrades aber offensichtlich Eier nicht der kürzeste nicht die kürzeste Weglänge dass eine kürzere so das vielleicht immer noch nicht die kürzeste aber sie können keine Fehler machen wenn sie diese Distanz von Frau von diesen vor klugen Frau unter setzen auf die Weg auf die Länge des Weges weg von Staat Knoten nach plus länger von und nach vor ich kann man nichts falsch machen hat man die dann schritt er verbrachten mehr in die Richtung zum könne zu den kürzesten Wegen so und hat mir auch schon betrachtet wir setzen alles auf unendlich und es und dieser dieser die letzte kann Dinge des kürzesten Weges da wir noch keine christliche haben setzen sie auf 0 1 also auf freut haben gut Tempel hebelt das haben wir schon bald extra gesehen war in dem Moment wenn zum 1. Mal berührt werden kriegen sind endlich das Leben vorgenommen und öffentliches Leben sind aber nicht permanent geregelt und das ist der Unterschied zum einen Sie da extra hat ich kurz glaube ich ein letztes Mal gesagt der Algorithmus zu Ende ist ist alles nur sind sämtliche will Distanz temporär bei Talkshows anders in die Redaktion wird eine Distanz wird auf fest in Stein gemeißelt gesetzt das ist bei diesen Algorithmen danach werden wenn man vor dem Fall Barschel dazu
nicht der Fall negative Kantenlängen haben beim letzten Mal betrachtet sie welches ist comma weitergehen da extra funktioniert nicht mit negativen Kantenlängen es muss ich mal negative Züge sein es reicht schon negative kann in Sachen musste extra nicht funktioniert so die Idee ist also wer das will das 4. bis zum Ende auf die Distanz Werte wirklich festzusetzen festzuzurren und nicht mehr zu ändern das habe hier ne in der Miliz dreht ist der Distanz Wert der da steht ein Oberfranke ist ist nicht kleiner als die echte kürzeste Distanz von es zu diesem Knoten so das dieses Theorem ist
nochmal vielleicht wenn sich das anschauen und vergleichen ist vielleicht noch eine Rechtfertigung für diesen korrekt Schritt denn
sie haben wenn hier ein größerer steht sorgt man dafür dass kein großer mehr steht
weil dieses Theorien sagt wir haben die Distanz Längen wir haben die Länge von gewissen Pfaden DV ist die Länge eines gewiss und eines Falles von Essen nach vorn muss nicht der kürzeste Weg sein hier ist eine Äquivalenz alle diese DV wird alle für alle Knoten V zusammengenommen sind die Christen Wege das Tanzen für alle diese Noten genau dann wenn diese dass diese Bedingung für jede Kante gilt warum ist das so die Einrichtung meistens ist es ja so dass die Einrichtung nicht gar nicht allzu kompliziert ist werden wenn das wenn die die aus alle tatsächlich kürzesten Wege Distanzen sind na ja was steht denn die vor wir haben die irgendwo S wir irgendwo und wir irgendwo Frau und die Länge eines kürzesten Weges voran wir werden also wir sagen jetzt dass Idee Werte tatsächlich die Länge von Küssen Wege sind das heißt hier das hier länger des kürzesten Weges von nach von nach das ist hier die EU und die Länge eines kürzesten Weges wir meine aussehen mag ist die Frau von US nach V so dann ist natürlich klar dass die kleiner gleich DU plus länger Frau sein muss der ein die Frau ist die Länge eines kürzesten Weges und das hier was hier steht ist die Länge eines anderen Weges davon es noch Frau und eines Weges könnte so würde ich auch ist der Weg sein dann damals mit gleicher der fühlt es keine Gesichter Weges ist nicht ungleich aber sind weil sie kleiner gleich so oder so das heißt diese Richtung ist ganz einfach wenn die die alle kürzeste Distanz Lebens sind dann gilt für jede Karte UV diese Gleichung so jetzt kommen uns mal die eine Richtung an Rechnung jetzt gehen wir davon aus das dass die Distanz Label dieser die mit irgendwelchen Knoten sind nicht eine das kürzeste es von also die Frau es von Frau Fahrradläden ja das ist die genaue Negation die Idee ist die die eine Richtung ist die dies und aller allesamt Farbklängen kürzeste Wege von es zudem ein in Knoten und die Negation das umgekehrte ist es sind nicht alle davon kürzeste Vater des legen so und das wird zu zeigen haben es gibt eine in Frau für die das nicht Geld wo also tatsächlich der von V echt größer die von bloß Länge von nach V ist ja sie ändern sich das Theorem was das besagt die geht es sind genau daran alle kürzeste Weg Länge von es zu den Armen sind loten genau dann wenn für jede Kante wieder Insel könnte Geld das ist die ungleichen so rum ist des verkleinert Nächtigungsplus Kantenlänge so weit ich jetzt die Einrichtung in diese Richtung wenn das alles Christen sowie klingelt gilt dann ist das so dann gilt diese und gelten alle zum gleichen Falle kann das habe eben gesehen jetzt in der anderen Richtung genau anders herum wenn das nicht alles kürzeste Wege sind dann gibt es mindestens eine keine für die das nicht gilt das exakte logische Umkehrung sowohl die konstruieren wir und das ist in diese Kante UV indem wir sagen ab ob immer weniger Wasser drin dem teil das vielleicht doch noch mal nachladen diese kannte konstruieren wir uns wir haben hier irgendwo wir irgendwo V und der Frau in den Wehen also wir wo er noch eine weitere noch im weiteren Knoten und wir suchen uns ein die raus so das DIW ist nicht kürzeste länger von S von erst nach will ja so mir diese zu werden das gar die andere das mindestens so was gibt dann gucken wir uns den kürzesten Weg an von nach irgendwo gibt es dann eine Situation V wo hier ist DEU ist tatsächlich ist gleich ich kürze das man ab kürzeste Pfad Länge von von erst nach und des von Frau ist nicht gleich kürzeste Pfordt Länge von es noch Frau ab irgendwo muss es mal passieren so das heißt es gibt hier einen kürzesten Pfad einen kürzeren vor Ort hier lang dass der kürzeste Weg von Frau es nicht der ihr und das heißt für diese kannte kann das dann nicht mehr er habe ich es richtig und gedacht genau für diese kann der kann das nicht mehr gelten weil das ist dann echt größer die von Frau ist echt größer muss ich größer sein als die Länge eines Fahrrades ist genau und deshalb dieses die ist die kürzeste länger das ist die Länge das ist die Länge eines allenfalls der größer ist richtig und das muss insgesamt ein größerer rauskommen habe ich es richtig überlegt ich glaube schon schön und genau das ist der das ist der Pfad der der DV konstituiert genau jetzt genau nach der wichtige Punkt dabei jetzt weiß ich wieder dass es den kürzesten Weg von wie so dass ist auch ein Christerweg von Es noch vor seinem muss das war noch der Bund ich vergessen hatte und dann dann geht's auf period aus der Stelle so alles nicht auf die vor geschrieben hat nicht was ich mehr aber du 10 ich weiß ich werde bezahlt dafür was ich mir trotzdem als aber Dozent soll so überlegen muss mehr
so gerne Label korrekt in Erben ist dann einfach auf dieser Basis kommen sich das 1 kommt Ihnen bekannt vor alles nicht wir wollen wir wollen von es aufwiesen dennoch Situation diese nicht Albers sondern auch das Situation von es aus in einem die Grafen endlich den Grafen des mit Kantenlängen C von es aus allen anderen Knoten Wege Kiste Fahrt legen zu berechnen sowie fahren wie üblich an alle Knoten aus war es enthalten plus und erhalten plus unendlich als als Distanz ist in erhält wie üblich 0 Tanz ins da jetzt noch keine keine keine Pfade gefunden haben Sie die entsprechenden Pointer wie üblich erst mal wollt so oder machen einfach folgendes solange es noch eine Kante gibt am Anfang gibt es natürlich viele solcher kannten aber solange es noch so eine Kante gibt solange setzen wir die auch solange korrigieren will das Setzen der in den Wert Frau auf die er auf der linken Seite auf den wird hier die plus Länge Frau auf der rechten Seite und in dem Moment wenn diese Schleife abbricht ist ist die Bedingung erfüllt es gibt keine solche könnte mehr also bei allen steht statt größer kleiner gleich und die den gesehen haben in dem Theorien der Tat ist das gleichbedeutend damit dass die Distanz hatte eine kürzeste Klängen sind so schön oder so die Frage ist natürlich ob das terminiert ob diese Schleife terminiert und wenn ja wie viel Laufzeit die kostet und beziehungsweise was man tun kann wir haben hier alle großen Freiheitsgrad rennen wir haben nicht gesagt in welcher Reihenfolge wir diese kann dann durchsuchen wollen und da steckt natürlich dann die Intelligenz Tränen in verschiedenen Reihen vor mit verschiedenen Reihenfolgen kriegt man verschiedene Laufzeiten aus teilweise also methodisch verschiedene Laufzeiten teilweise nur empirische Verbesserungen beschleunigen sowie so
erst mal macht man sich klar dieser Algorithmus terminiert in einer endlichen Anzahl von
Iterationen warum weil wir eben schon gesagt haben und das lässt sich leicht noch mal mit Verschiedenes nachvollziehen jeder Distanz wird ist immer die Länge eines gewissen Fares von es zu diesem Knoten ja am Anfang ist das so solange solange des also sobald es dann wird nicht mehr plus unendlich ist das gilt in der zu uns Anfang es gilt für S die 0 ist die länger eines gewissen sogar eines großen vor das von Essen und sowie ein Knoten endlich würde hier hier in der Schleife sowie ein sowie links DVU plus unendlich steht und der wird endlich nach Induktion Voraussetzung ist die von immer die Länge eines Weges von S nach dann ist natürlich die von Plus der Kantenlänge die Länge eines gewissen Weges von S nach V das heißt also wenn wir die von vor auf die rechte Seite ersetzen ist das wieder die Länge eines gewissen Weges es kann aber nur endlich viele Ricklingen einem endlichen Grafen kleben von ist noch Frau und und und die Distanzen die werden immer kleiner Schritt für Schritt echt kleiner in jedem Update das heißt also keine Weglänge von es nach Frau wird zweimal durchlaufen da zügelt nichts sie werden einmal im Jahr in absteigender echt absteigender Reihenfolge durchlaufen die möglichen Distanz und als endlich viele Wege gibt vor es noch Frau kann endlich viel Unterschiedliches dann Sie Werte gehen nach endlich vielen Schritten terminiert der Algorithmus ist noch nicht so prickelnd also nach endlich vielen Schritten terminiert aber immerhin besser als nichts es geht weiter
man kann Beispiele konstruieren das müssen wir jetzt hier nicht machen wo die Laufzeit des Algorithmus tatsächlich exponentiell würde wenn man es wenn man die Auswahl der kalten ungeschickt macht oder bei bei dabei in die bei ganzzahligen kann man kann man wieder argumentieren na ja jede jeder Pfad länger ist irgendwo zwischen 0 und n x C das hat mir am Anfang dieser vor heute schon mal ja C über die obere Schranke für alle Fahrten in und müsse und Ende sowohl Schranke für die Anzahl der Kanten auf einem Fahrrad das heißt also für einen für ein Knoten von er die Pfade von es nach V ist kann nur einmal C unterschiedliche Fragen geben bei ganzzahligen könnten werden könnten wenn werden und viele der zweite Faktor in kommt daher dass das natürlich für jeden ein sind wurden sein kann so oft kann Update Schritt dem für jeden Knoten kann es einmal C viele Update Schritte maximal geben was natürlich niemals aber zu sein aber theoretisch kann man das nicht besser beschränken multipliziert mit der Anzahl der Klonkriege ein Quadrat mal 10 aus ist aber noch nicht kleckern der also daher sind davon da ist war eigentlich das es gewöhnt nicht so wenn wir wenn wir jetzt erst einmal das ganz einfach so machen immer alle kannten durchgehen erinnerndes zu halten und mal gucken ob es irgendeine kannte gibt diese Bedingungen die Optimalität bedienen verletzt das natürlich sehr auf und Kost natürlich sehr viel Laufzeit weil wir dann im gesamten könnten potenziell durch den müssen gesamte könntest du durchgelesen diesen Fakt müssen wir noch hier drauf multiplizieren und die gesagt in die war Laufzeit zu haben ist also alles ist wirklich nicht sehr glücklich so jetzt kann weitergehen wir speichern und eine nicht eine Liste der anerkannten sondern wir speichern uns eine Liste von Knoten mit der Eigenschaft das wenn eine könnte diese Bedingungen Fall verletzt dann ist dieser Knoten Dateien enthalten in dieser Geste und damit haben den Faktor bitte ich n eingespart und wir haben das alles nicht so
prickelnd nicht wir sind wir sind hier in Laufzeiten würden die jenseits von Gut und Böse sind zumindest was die asymptotische Komplexität angeht das noch mal dieselbe Idee eben eben hatten in ihren Code gegossen dass wir eben eine Liste der von Knoten und nicht eines davon Kanten haben und für jeden Knoten eine Liste der von kannten die raus Hausgenossen sind wurden und die diese belegen verletzen der wir sind wir immer noch
weit weg von dem was wir uns eigentlich auf 100 Rollen würden von Laufzeiten kann ich also müssen uns Star immer anstrengend das wird heute natürlich nicht
weil zu viele gehen haben 1. offensichtlich einfacher Verbesserung ist die dass wir die Kanten wer warten Sie gemeint
ja genau eine ganz primitive für Verbesserung ist die man wahrscheinlich schon implementiert bevor ohne daran zu denken ist das wir die Kanten in einer festen beliebige aber festen Ordnung speichern und in dieser Ordnung zusammen in runden durchlaufen eine Runde es einmal durchlaufen alle kannten Insel ist und für viele kannte die diese Eigenschaft hat die die noch die Optimalität Bedingung verletzt machen wir den Korrektur Schritt dass wir den den die wir wir Ärztin ist das 4. sieglose runtersetzen auf des Grenzwertes starten uns plus länger erkannte und die Wartung ist wenn wir das so machen nach der Karten Iterationen nach dem Karten passt durch die ganze letzte das ist das Ergebnis was jetzt momentan in Distanz werden steht am kürzesten Weg ein Küsse ist sofort von Know-how ist vom Staat Knoten zu jedem anderen Knoten mit höchstens Car kannten ich glaube nicht dass das Lemma exakt stimmt das würde ich beim nächsten Mal erklären warum ich das nicht glaube darauf bin ich gekommen als sich Energie die 2 wenn man fort worauf das hinauslaufen würde erklärt habe und jemand der entweder schon im Zwischenruf oder später dann zu mir gekommen ist und gesagt hat da ist irgendwas nicht ganz koscher das würde ich dann beim nächsten Mal hier erklären was ich meine ist aber ich meine es ist ein Weg es ist die Länge eines Weges der nicht länger ist als das was hier steht es kann es kann mehr als kann aber keinen enthalten aber es auf keinen Fall länger als ein kürzeste Weg mit K oder weniger Kanten lassen Sie das mal kurz absagten also nicht absacken sondern das was ich eben gesagt habe absacken vielleicht Einwilligung die 1. 5 Vorträge hier sind sind sind jetzt gerendert und sind 1 gegeben dass die das dort einen hängen nicht habe ich warte jetzt nur dass sich die URL mal bekomme wo die Eingänge sind dass das an sie weiterleiten kann so wir haben pünktlich angefangen Sie sehen ich bin dann zum routinierten Aufbau und wir können es aber auch pünktlich aufhören ich danke Ihnen für dieses Mal
Loading...
Feedback
hidden