Shortest Paths II
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| 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 | |
| Identifiers | 10.5446/21473 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
2
3
4
5
7
8
9
10
11
12
13
14
00:00
PermanentLengthKantePriority queueSet (mathematics)ZahlTrailReal numberMetreRound-off errorUmrechnungSupremumWavefrontCloningLaufzeitCanonical ensembleQueue (abstract data type)Stress (mechanics)Haar measureComputer animation
09:35
Maxima and minimaPermanentLengthDistanceLaufzeitIndexVertex (graph theory)LengthAdditionSet (mathematics)QuotePolygon meshLink (knot theory)MetreStreckeZahlPhysical quantityIterationKanteComputer animation
19:00
Radical (chemistry)MathematicsDistribution (mathematics)Standard deviationKanteLengthIndexSet (mathematics)Direction (geometry)CalculationGeometryMoment (mathematics)WavefrontComputer animation
28:25
PermanentDirection (geometry)KanteIterationSet (mathematics)Interface (chemistry)Konstruktion <Mathematik>WavefrontStructural equation modelingCompass (drafting)SurfaceEllipseSummationLink (knot theory)Moment (mathematics)EnergieComputer animation
37:50
ConsistencyEuklidischer RaumPlane (geometry)Untere SchrankeTerm (mathematics)KanteTrailLengthDreiecksungleichungDesire pathGreatest elementMathematicsDirection (geometry)VelocityStress (mechanics)EquationSummationInequality (mathematics)Negative number
47:14
Distribution (mathematics)Standard deviationFunction (mathematics)Keilförmige AnordnungGreen's functionIterationMathematical optimizationDependent and independent variablesDirected graphSubgraphPlane (geometry)Graph (mathematics)SummationTerm (mathematics)Logical constantLengthMathematicsKanteTrigonometrySign (mathematics)Hausdorff spaceSet (mathematics)GeometryDirection (geometry)AngleInterface (chemistry)Negative numberMathematics
56:39
Dependent and independent variablesDirected graphSubgraphPlane (geometry)Graph (mathematics)HierarchyShortest path problemBinary fileKeilförmige AnordnungAlgebraic structureStandard deviationForestKanteSelectivity (electronic)SchulmathematikCoordinate systemRectangleSet (mathematics)AngleVertex (graph theory)Direction (geometry)Shortest path problemConvex hullTrailLink (knot theory)Function (mathematics)Computer animation
01:06:04
Graph (mathematics)Military operationKeilförmige AnordnungDistanceIterationOperations researchTheoremDirected graphCondition numberLengthDirection (geometry)KanteEquationTheoryIterationPhysical quantityEquivalence relationDesire pathTrailSupremumChain complexStress (mechanics)Negative numberMoment (mathematics)Computer animation
01:13:57
Directed graphLengthVertex (graph theory)Function (mathematics)IterationInfinityLaufzeitDesire pathLengthDegrees of freedom (physics and chemistry)TheoryInversion (music)Moment (mathematics)Shortest path problemDirection (geometry)KanteIterationComplete metric spaceInequality (mathematics)Computer animation
01:21:51
IterationInfinityKeilförmige AnordnungINTEGRALElement (mathematics)Shortest path problemDirected graphKanteFactorizationLaufzeitTrailOptimalitätsbedingungLengthSquareSuspension (chemistry)Shortest path problemSupremumDesire pathRoundingEnergieIterationRollbewegungLimit of a functionOptimumComputer animation
01:29:44
Computer animation
Transcript: German(auto-generated)
00:01
präsentiert von Open Learnware, die Plattform für 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 mitten im Thema Kürzeste Wege, ein Thema, das Ihnen ja aus der GDI 2 auf jeden Fall bekannt vorkommen sollte.
00:25
Auch teilweise die speziellen Themen, die wir hatten. Wir haben nochmal kurz beispielsweise den Algorithmus von Dijkstra uns angeschaut. Wir sind noch nicht fertig ganz mit dem Algorithmus von Dijkstra. Hier nochmal eine interessante Implementation der Priority Queue.
00:40
Sie erinnern sich aus der GDI 2 und auch hier vom letzten Mal, dass die Priority Queue bei Dijkstra ein sehr wichtiges Thema ist. Wichtig für die Laufzeit, weil Sie ja in jedem Schritt immer den Knoten finden müssen, dessen aktuelles Label, dessen aktuelles Distanzwert der Kürzeste ist von allen Knoten,
01:02
die bisher noch nicht behandelt worden sind. Und da gibt es verschiedene Möglichkeiten. Sie haben in der GDI 2 die Möglichkeit kennengelernt mit einem Heap. Wir haben hier andere Möglichkeiten übersprungen, die dann natürlich auch nicht prüfungsrelevant sind. Was allerdings sicherlich nochmal interessant und einsichtsreich ist, ist diese Implementation, diese Priority Queue, die sich Dial Implementation nennt.
01:26
Dial, das hat zu tun mit dem englischen Wort zu Dial. Im Sinne von Telefon wählen oder Dial heißt auch die Wählscheibe. Da kommen wir noch dazu, was hinter dieser Intuition steckt. Aber zum nächsten Mal machen wir uns klar, was hier steht in dieser Beobachtung.
01:44
Sie erinnern sich. In Dijkstra nehmen wir in jedem Schritt einen Knoten hinzu, den wir vollständig abarbeiten und hinterher hat er den richtigen Distanzwert. Und dieser Distanzwert wird dementsprechend auch nie wieder verändert.
02:02
Was wir uns klar machen müssen hier ist, dass diese Distanzwerte, die wir permanent setzen, indem wir einen Knoten aus der Priority Queue rausnehmen und dann nie wieder anfassen, sein Distanzwert nie wieder ändern, dass diese Distanzwerte non-decreasing, also nicht absteigend,
02:23
immer permanent aufsteigend oder mal zufällig gleichbleibend sind. Warum? Sie erinnern sich an die schönen Bilderchen, die wir gezeichnet hatten. Ich glaube, da muss man noch ein bisschen Flüssigkeit wegnehmen.
02:42
Das ist wie üblich unser Graf. Irgendwo in der Mitte vielleicht oder wo auch immer ist unser Startknoten. Und wir haben jetzt schon eine ganze Menge von Knoten. Wir sind irgendwo mittendrin. Wir haben eine ganze Menge von Knoten endgültig abgearbeitet.
03:01
Die sind hier, alle drin, in dieser Menge. Und jetzt nehmen wir einen neuen Knoten irgendwo hinzu. Mal gucken, ob das eigentlich gut aufgenommen werden. Nehmen wir einen neuen Knoten hinzu.
03:20
Und was ist die Aussage dieser Beobachtung? Die Aussage dieser Beobachtung ist letztendlich, wenn ich diesen neuen Knoten hinzunehme, ich hoffe, das war jetzt nicht aufgenommen worden, wenn ich jetzt diesen neuen Knoten hinzunehme, dann ist sein Label nicht kleiner als irgendeines dieser Labels, die vorher schon hinzugenommen worden sind, die vorher schon endgültig abgearbeitet worden sind.
03:43
Das ist die Aussage dieser Beobachtung. Letztendlich niedergebrochen auf den Verlauf des Algorithmus. Und warum ist das so? Naja, wenn irgendein Knoten hier drin, wie z.B. der hier, einen größeren Distanzwert als der hier hätte,
04:03
den wir jetzt hier über irgendeine Kante hinzunehmen, naja, dann ist das ein Widerspruch letztendlich zum Fortgang des Algorithmus. Dann wäre der hier viel früher genommen worden als dieser Knoten hier.
04:20
Die Situation wäre gar nicht da, dass dieser Knoten schon bearbeitet worden ist und der hier noch nicht, denn wir nehmen ja in jedem Schritt immer das kleinste Element. Die Wellenfront hätte erst den hier erreicht, bevor sie den hier erreicht hätte. Also es kann nicht sein, und das heißt, dass dieser Distanzwert hier, von diesem neuen Knoten hinzunehmen,
04:42
mindestens so groß sein muss, wie der Distanzwert von jedem anderen Knoten. Das machen wir uns erst mal klar, dass diese Distanzwerte, diese Schlüsselwerte der Priority Queue, wie wir die Elemente nacheinander rausholen, dass die in aufsteigender Reihenfolge sind. So, was bringt uns das jetzt für die Implementation der Prioritätswarteschlange?
05:07
Wir betrachten einen sicherlich nicht ganz unrealistischen Fall, dass die Kantenlängen ganzzahlig sind. Also ganzzahlig. Das ist beispielsweise ja bei einem Navi der Fall.
05:22
Nicht ganzzahlige Kilometer, aber ganzzahlige Vielfacher von 100 Metern. Ja, damit rechnet so ein Navi oder vielleicht sei es auf einen Meter genau, ist ja auch egal. Selbst wenn es auf einen Zentimeter genau rechnen würde, sind wir noch ganzzahlige Vielfacher einer Basis-Einheit. Das heißt, bei einem Navi haben wir immer diese Situation gegeben. Denken Sie sich andere Situationen, also wenn wir jetzt Kilometer rechnen,
05:43
wenn wir jetzt beispielsweise Zeit rechnen, haben wir natürlich ganzzahlige Vielfacher der Einheit Sekunde oder wenn Sie an eine andere Situation denken, wie beispielsweise im Bahnverkehr, da haben Sie ganzzahlige Vielfacher der Basis-Einheit Minute. Ja, also es ist jetzt keine wirkliche Einschränkung davon auszugehen, dass die Kantenlängen ganzzahlig sind.
06:04
Selbst wenn Sie das nicht haben, selbst wenn Sie irgendeine Anwendung haben, in der Sie wirklich Double-Werte haben, wo Sie wirklich den ausnutzen, dass Sie mit Double theoretisch reelle Zahlen modellieren können,
06:20
können Sie, wenn Sie unbedingt wollen, natürlich mit einem ganz kleinen Rundungsfehler alle diese reellen Zahlen auch in ganzzahlige Vielfacher einer sehr kleinen Einheitszahl umrechnen. Das geht natürlich also immer, also es ist praktisch keine Einschränkung. So, das ist jetzt die erste Variante.
06:43
Ja, diese erste Variante erklärt noch nicht, warum das Ganze was mit einer Wählscheibe zu tun hat, aber die brauchen wir erst mal als Vorbereitung für die zweite, die eigentliche Variante. Was hier steht ist, die Parity-Q ist letztendlich ein Array einer gewissen Länge, die beginnt mit 0.
07:07
Das soll eine Null sein und kein Osterei und endet mit einem Wert N mal C. Was ist C? Das ist der größte Wert, der vorkommen kann.
07:20
Ja, denken Sie sich wieder bei einem Navi, denken Sie sich die Weglänge als ganzzahlige Vielfache von 100 Metern. Was könnte der längste Straßenabschnitt sein, der in so einem Navi vorkommt? Wie lang könnte der sein? Gut, es gibt wahrscheinlich irgendwo in den Alpen, wenn wir jetzt in Europa sind, irgendwo in den Alpen oder sonst irgendwo
07:44
lange Wegstrecken ohne Gabelung, ohne Kreuzungen, die vielleicht auch mal wirklich, weiß ich nicht, 20, 30 Kilometer lang sind vielleicht auch noch ein bisschen mehr. Nehmen wir mal an 50. Es gibt keine Wegstrecke, die länger ist als 50 Kilometer, ohne dass dazwischen mal eine Kreuzung oder irgendwas ist. Dann wäre 500, also 50 Kilometer gleich 500 mal 100 Meter, wäre 500 eine geeignete Zahl groß C.
08:16
Und wichtig ist, dass die Distanzlabels, die vorkommen können, die Länge von kürzesten Faden
08:25
oder überhaupt die Länge von Faden, muss ja nicht mal kürzeste sein, dass die Längen von Faden nicht größer sein können als N mal C. Warum? Naja, so ein Fad kann ja höchstens N minus eins Kanten haben, wenn er keine Zügeleinheit hat.
08:43
Ja, so wie er mehr als N minus eins Kanten hat, muss er irgendwo eine Zügeleinheit haben, N die Anzahl der Knoten. C ist eine Oberschranke auf der Länge einer Kante. N ist eine Oberschranke für die Anzahl Kanten in einem Weg. Also ist N mal C eine Oberschranke insgesamt für die Länge eines Weges.
09:03
Das heißt also, wir wissen von vornherein, ohne weiter nachzudenken, dass unsere Distanzwerte irgendwo in diesem Bereich 0 bis N mal C sein werden. Und genau da tragen wir sie immer ab. Wir tragen sie immer, wenn wir hier irgendeinen Distanzwert Delta haben.
09:20
Oder ich nehme mal einen anderen Wert K. Delta war ja die Abkürzung für die Distanzwerte der Anzahl Knoten. Da speichern wir in einer Liste beispielsweise in irgendeiner Datenstruktur, wo wir leicht immer ein beliebiges Element rausnehmen können, wie zum Beispiel eine Liste, wo wir immer das Kopfelement sofort rausnehmen können oder am Kopf sofort was reinspeichern können.
09:45
Da speichern wir in jeder Datenstruktur diejenigen ab, wo die Distanzwerte Delta des jeweiligen Knotens gleich K ist. Ja, das machen wir. Immer dann, wenn wir bei einem Knoten-Distanzwert setzen,
10:04
updaten, schieben wir diesen Knoten von der Liste von seinem alten Distanzwert. Ja, wir haben einen Knoten abgedatet von einem K zu einem K-Strich. Das heißt, diesen Knoten schieben wir von der jetzigen Liste, wo er drin ist, bei K zu der Liste von K-Strich, was sein neuer Distanzwert ist.
10:30
Und da die Labels, da die Labels, die wir permanent setzen, die Labels, also von den Knoten, die wir aus der Priority-Q rausnehmen wollen,
10:42
da die non-decreasing sind, wie diese Beobachtung sagt, da sie monoton wachsend ist, das besagt, wir können einmal in einem Scan von links nach rechts, von 0 bis maximal n mal c, einmal durch alle Slots durchgehen, die Knoten, die da drin sind, abarbeiten,
11:03
zum nächsten Slot gehen und fertig und nie wieder zurückkehren. Das heißt also, wir haben gar nicht diese ganze Problematik, sie erinnern sich mit Heap-Daten-Struktur als Priority-Q, mit dem ganzen Umorganisieren in logarithmischer Zeit und so weiter,
11:22
sondern wir gehen ein einziges Mal durch die Priority-Q, die Knoten, die Elemente sind hier gespeichert in diesen Listen. Und wenn wir einmal über einen bestimmten Slot einen bestimmten Index verlassen haben, die Knoten, die da drin sind, die fassen wir nie wieder an, die haben die richtigen Werte.
11:43
Das ist die Idee dieser Implementation, die Grundidee. Gehen wir weiter, das in a doubly linked list, das ist, glaube ich, Geschmackssache, man könnte auch eine singly linked list näher nehmen und immer am Anfang der Liste einspeichern,
12:02
wenn ein Knoten dahin gehört und das nächste Element vom Anfang der Liste hernehmen. Ich glaube, das macht keinen Unterschied. Dass das eine Oberschank ist, haben wir gesehen, habe ich eben gesagt. Und das ist nochmal genau präziser von dem, was ich gesagt habe, wir gehen einmal von links nach rechts durch,
12:22
to scan im Englischen, wir scannen das einmal durch. Und wann immer wir, wir fangen mit Null an, wann immer wir auf einen leeren Bucket stoßen, leere Liste, gehen wir natürlich weiter. Es gibt dann keinen Knoten, der dieses Label enthält, der diesen Distanzwert enthält.
12:40
Also gehen wir weiter so lange, bis wir einen Distanzwert, einen Index finden, der nicht leer ist, wo Knoten sind, die diesen Distanzwert aktuell haben. Und darauf auf irgendeinen Knoten, der in diesem Bucket drin ist, wenn wir dann die nächste Iteration von Dykes ranholen, raus aus der Priority Queue und bearbeiten auf die übliche Art und Weise.
13:01
Ja, es geht immer natürlich, der Algorithmus von Dykes ist immer derselbe. Es geht nur darum, zu organisieren, wie wir immer an den nächsten Knoten rankommen. Frage? Ja, Vorsicht, Vorsicht.
13:20
Ich glaube, ich muss die Illustration, das ist mir aufgefallen, als ich das gezeichnet habe, dass diese Frage kommen könnte. Aber ich habe mal abgewartet, ob die Frage kommt. Ich glaube, ich muss diese Illustration nochmal ein bisschen anders gestalten, um das deutlicher zu machen, was hier die Rolle der einzelnen Buckets, der einzelnen Knoten sind.
13:48
Wir stehen jetzt gerade auf diesem Bucket hier. Und er ist nicht leer. Da haben wir mindestens einen Knoten zum Abarbeiten.
14:01
Den nehmen wir her. Was machen wir jetzt? Was wir jetzt machen, ist, wir gucken uns alle seine Nachfolger an. Ja, wir gucken uns seine Nachfolger. Einer seiner Nachfolger... Warten Sie mal, ich muss das noch ein bisschen deutlicher zeichen. Einer seiner Nachfolger hat zum Beispiel diese Länge, diese Distanzwert K.
14:23
Ja? So, was machen wir mit dem Nachfolger? Gegebenenfalls, unter gewissen Bedingungen, ändern wir, reduzieren wir diesen Distanzwert von diesem Nachfolger zu einem etwas kürzeren Distanzwert K'.
14:40
Ups. Sodass wir also hier, jetzt vervollständige ich das Bild wieder, was wir eben hatten. So, Sie sehen, hier sind wir gerade. Das ist der Wert des aktuellen Knotens aus der Particule raus. Das ist der Wert eines Knotens, der Nachfolger ist von dem aktuellen Knoten.
15:03
Und von dem ändern wir den Distanzwert von K auf K'. Ich glaube, jetzt wird das Bild etwas klarer. Genau, ein Knoten... Vielleicht sollte ich das noch mal ein bisschen anders zeichnen. Ein Knoten, der Nachfolger ist von dem aktuellen Knoten, den fügen wir hinten an.
15:25
Frage? So wie ich es jetzt gezeichnet habe, brauchen wir doppelt verlinkte Listen. Ach so, ja, stimmt, Sie haben recht. Es hat schon seinen Sinn, warum es doppelt verkettete Listen sind,
15:41
damit wir nämlich hier aus dieser Liste sehr bequem das entfernen können. Stimmt, das ist ein guter Hinweis. Also, ich korrigiere das, was ich gesagt habe. Doppelt verkettete Listen sind essenziell für die Laufzeit dieser Implementation. Vielen Dank dafür. Ich sage ja, warum mache ich die Vorlesung?
16:00
Stellen Sie sich nicht heran hin. Genau, weil Sie nicht bezahlt werden dafür. Ja, für die Nachwelt wird das alles aufgenommen. Gut. Gibt es ganz konkret hier noch weitere Fragen? Wenn nicht, dann kommen wir jetzt zu der eigentlichen Update-Operation.
16:23
Also zunächst noch mal, was wir eben gesagt haben, wann immer sich ein Distanzwert ändert. Ich habe es hier KK' genannt. Hier auf der Folie ist es von D1 nach D2 genannt. So, die Laufzeit muss man sich noch mal überlegen. Wir fassen jede Kante einmal an.
16:43
Wir fassen natürlich jeden Knoten einmal an. Aber die Laufzeit, um jeden einzelnen Knoten anzufassen, ist natürlich in dem N mal C, in den zweiten Summanden drin. Das brauchen wir nicht noch mal extra aufzuschreiben. Und wir gehen einmal diesen Bucket durch,
17:04
dessen Länge asymptotisch N mal C ist. Das ist die Laufzeit dafür. Ist vorteilhaft, wenn das Groß C keinen allzu großen Wert enthält, sodass N mal C vielleicht gegenüber dem M nicht allzu groß ins Gesicht fällt. Idealerweise sogar kleiner ist als die Zahl M.
17:23
Beziehungsweise es eben überschaubar. Ja, wir hatten eben 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 Streckennetz als Grafen hat.
17:43
So, jetzt gehen wir einen Schritt weiter. Die nächste Beobachtung. Wir haben ja im Prinzip bei den noch nicht bearbeiteten Knoten eine Zweiteilung.
18:03
Eine Zweiklassengesellschaft. Diejenigen, die noch den Wert unendlich haben, weil sie noch nie berührt worden sind, das kann man, wenn man will, noch als weiteren Bucket realisieren oder wie auch immer. Die haben wir jetzt in diesem Array nicht drin. Und diejenigen, die einen endlichen Wert haben.
18:21
Und die Aussage, die hier steht, können wir uns nochmal an dem Bild denke ich deutlich machen, wenn wir uns, was sagt diese Beobachtung, Nummer 13 jetzt ganz konkret in diesem Bild.
18:42
So, wir sind jetzt in einer Iteration, in der dieser Knoten hier, das ist V auf der Folie, in der dieser Knoten hier permanent gelabelt wurde. Der hinzugenommen wurde zu der Menge aller abgearbeiteten Knoten. So, und diese Beobachtung sagt etwas aus über die Knoten,
19:02
die noch nicht abgearbeitet sind, aber nicht mehr Distanzwert unendlich haben, sondern einen endlichen Distanzwert haben. Was heißt das? Das heißt, dass es mindestens eine Kante jeweils hier raus gibt, unter Umständen mehr als eine Kante zu jedem dieser Knoten.
19:21
Ja, über diese Knoten sagt diese Beobachtung etwas aus. Und was sagt sie über diese Knoten aus? Sie sagt aus, dass dieser Distanzwert, die diese Knoten momentan hat, und den er nie wieder überschreiten wird, weil Distanzwerte immer höchstens kleiner werden, dass dieser Distanzwert zu diesem Distanzwert nicht allzu viel größer sein kann,
19:42
nämlich der Unterschied kann höchstens C sein, dieses Groß C. Warum? Das ist ganz einfach. Sie erinnern sich, die vorhergehende Beobachtung war, dass die Distanzwerte in aufsteigender Reihenfolge permanent werden.
20:01
So, das heißt also, der hier, dieser Knoten hier, das haben wir eben schon mal gesagt, kann höchstens so hohen Distanzwert haben wie der hier. Nicht höher. Der hier kann einen kleineren Distanzwert haben als der, oder gleichgroßen. Das bedeutet für den Knoten W hier oben,
20:22
mit W ist er auf der Folie bezeichnet, dieser Distanzwert ist kleinerer als diesen, plus Länge der Kante, höchstens C, kommt es genau hin, dieser Distanzwert hier, wenn ich das jetzt hier mit diesem Knoten,
20:42
ich hoffe, das kann man auch sehen, ich mach das mal an einer anderen Stelle, hier ist das W, hier ist ein Knoten U, und hier ist diese Kante. Der Distanzwert von U ist kleiner gleich dem Distanzwert von V, und der Distanzwert von W ist kleiner gleich
21:05
Distanzwert von U plus Länge der Kante, nach oben abgeschätzt C, und damit steht es schon da. Ja, ich muss hier nur noch für U V einsetzen,
21:23
und dann steht es da. Das bedeutet, für unsere Implementation, dass alles, wo wirklich was passiert, ein sehr kleiner Abschnitt dieses Arrays ist,
21:42
nämlich mit einer Länge, die höchstens, ich will mich jetzt nicht um eins vertun, mit einer Länge, die höchstens C plus eins ist. Ja, außerhalb dieses Bereichs haben wir noch nicht. Alle Knoten, die außerhalb dieses Bereichs sind, haben noch eine unendliche Länge.
22:01
Das sagt 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 eins von diesem ganzen riesigen Array benutzt wird, kann man, jetzt kommen wir zu Dial, zur Wählscheibe,
22:23
kann man sich das Ganze auch, diesen riesen Array auch sparen und nur ein Array der Länge C plus eins anlegen,
22:56
so, und ihn behandeln mit einer Modulo-Operation.
23:03
Wir haben also die Indizes von Null nach C, das passt wunderbar, mit Null als ersten Index, und ihn behandeln, als wäre er zyklisch. Hier ist Index Null, hier ist Index C.
23:27
Zyklische Behandlung heißt einfach Modulo-Rechnung. In dem Moment, wenn wir eins weitergehen, wenn wir einen Pointer eins weiter setzen, dann rechnen wir immer noch mal Modulo C plus eins, müsste man da rechnen, Modulo C plus eins,
23:47
und das bedeutet, wenn ein Index am Ende angekommen ist und einen nächsten Schritt macht, ist er wieder bei Null. Und das kann man sich veranschaulichen auf die Art und Weise, und daher kommt die Intervention der Wählscheibe. Sieht ja irgendwie so ein bisschen so aus.
24:02
Das heißt also, wir haben hier den Index laufen, irgendwo steht ja jetzt gerade, die nächsten Sachen kommen hier, und wir wissen, dass der ganze interessante Bereich,
24:21
der noch kommt vor diesem Index, dass der hier rechtzeitig endet. Weil nur dieses Fenster der Länge C plus eins überhaupt bestückt ist mit Inhalt. Ist doch eine gute Idee, oder? Kann man sich auch als, für andere Zwecke, durchaus mal merken, wann immer sie irgendwie
24:45
irgendwas durchscannen denken, das lässt sich sicherlich, ich bin mir sicher, ich weiß, das lässt sich beispielsweise auch auf Situationen in der Geometrie anwenden, wo sie irgendwas von links nach rechts durchscannen und wo sie immer eben nur ein Fenster
25:00
von einer gewissen Breite haben, und dann können sie genauso Modulo rechnen. Gut, damit, das ist das nochmal, was wir eben gesagt haben. Wir gucken uns noch ein paar Beschleunigungstechniken an.
25:21
Early Termination ist das einfachste, was sich eigentlich von selbst versteht, wenn man so etwas implementiert. Im Normalfall will man ja nicht, wie es eigentlich da extra vorgesehen hat, von einem Knoten zu allen anderen, die Distanzen haben. Im Normalfall will man von einem Startknoten zu einem Zielknoten. Beispiel Navi, sie wollen von Darmstadt,
25:42
hier irgendwo Karolinenplatz, meinetwegen, zu Frankfurt Main, zu irgendeinem Platz dorthin fahren. Ja, und sie haben jetzt Kartenmaterial in ihrem Navi-System drin, das bis nach Vladivostok, bis nach Lissabon, bis nach Kappstadt reicht. Was sie natürlich nicht möchten, ist, dass der Algorithmus
26:01
erst einmal dieses gesamte Kartenmaterial durchgeht, bis Vladivostok, sogar noch weiter, da unten Singapur oder so, was so das letzte Ende ist, was man trockenen Fußes erreichen kann, und Kappstadt dann in südlicher Richtung, dass das alles durchlaufen wird, wenn sie ja eigentlich nur von Darmstadt nach Frankfurt wollen. Ja, das will man ja nicht.
26:22
Also, erinnern wir uns daran, wenn wir so eine geometrische Situation haben, wie beim Navi, dann ist die Intuition gar nicht mal so falsch,
26:42
dass Dijkstra sich ausbreitet von seinem Startknoten aus, wie so eine Wellenfront, wie ein Stein, den man ins Wasser wirft. Also, das sollte jetzt ein bisschen, sollte gar nicht so elliptisch sein, wie es jetzt aussieht. Und wenn Sie jetzt hier Frankfurt erreicht haben, und Frankfurt gehört,
27:01
also der Punkt in Frankfurt, den Sie ansteuern möchten, und dieser Punkt ist jetzt permanent gelabelt, gehört zu der Menge der Abgearbeiten, können Sie Schluss machen, weil Sie sämtliche anderen Knoten ja gar nicht interessiert. Das ist die erste, einfache Beschleunigungstechnik, dass wir in dem Moment beenden können,
27:21
wenn der Zielknoten fertig abgearbeitet ist. Ändert natürlich nichts an der Worst-Case-Komplexität, denn im schlimmsten Fall kann es ja sein, dass Sie wirklich nach Kapstadt und nach Singapur wollen. Und wenn Sie nach Singapur wollen, dann müssen Sie schon andere Techniken implementieren, damit er Ihnen nicht auch noch ganz Afrika bis Kapstadt runter mitberechnet.
27:47
So, wie die gerichtete Suche? Ich glaube, da gehen wir erst einmal zu einem Bild hin, damit das klarer wird. Das ist die normale Suche. Links, Standard, ein bisschen anders gezeichnet als ich,
28:00
aber im Prinzip dieselbe Idee. Man hat so eine Wellenfront, die sich in einer Richtung gleich ausbreitet. Ist natürlich nur ein Bild, was nicht in jeder Situation stimmt, aber so in geografischen Anwendungen ist das Bild typischerweise gar nicht so falsch. Und bidirektionale Suche ist die Idee. Hier sehen Sie S und T. Wir gehen von beiden Seiten gleichzeitig los. Wir starten von beiden Seiten eine Suche.
28:24
So, was passiert dann? Gehen wir mal zurück. Wir haben jetzt, das kann ich ja jetzt eigentlich hier schön reinzeichnen, wir haben hier S
28:41
und wir haben hier T und wir haben hier gleichzeitig, also in jeder Iteration von Dijkstra einmal links und einmal rechts ein Schritt. So kann man sich das vorstellen. Ist aber auch egal. Sie können auch sagen, in jeder Iteration zweimal links und einmal rechts oder wie auch immer. Es kommt auf selber raus.
29:02
So und irgendwann treffen sie, die beiden sich mal, machen wir es mal so. Die beiden treffen sich jetzt irgendwo, haben irgendeinen Knut mal gemeinsam, der sowohl von links als auch von rechts permanent gelabelt ist. Und dann hört dieser Algorithmus auf.
29:23
Warum hört der jetzt auf? Oder was genau passiert dann in dem Moment? Der Knoten, den wir jetzt hier eingezeichnet haben, heißt auf der Folie W. So, jetzt ein ganz heißer Kandidat
29:42
für den kürzeste Fahrt ist natürlich der kürzeste Fahrt von S nach W in der einen Suche plus der kürzeste Fahrt von W nach D. Hier haben wir natürlich alle Kanten rückwärts genommen. Bei der zweiten Suche, hatte ich vergessen zu sagen. Logisch, wir gehen die Kanten alle in die umgekehrte Richtung. So, ein heißer Kandidat
30:02
für den kürzesten Weg von S nach T ist also der kürzeste Weg von S nach W in der einen Suche konkretiniert mit dem kürzesten Weg von W nach T in der anderen Suche. Muss aber nicht unbedingt der kürzeste Weg sein. Es kann auch noch andere Situationen geben.
30:20
Das steht hier auf der Folie. Aber ich sag Ihnen erst einmal, bevor ich dazu komme, was es noch für andere Situationen geben kann, was noch der andere kürzeste Fahrt ist, sag ich Ihnen erst einmal, was nicht sein kann. Was kein kürzester Fahrt mehr sein kann.
30:42
Dazu würde ich mal sagen, sollte ich nochmal ein neues Bild zeichnen.
31:04
Wenn wir jetzt von S startend die eine Wellenfront haben und wir haben das W wieder und wir haben die andere Wellenfront. Beide haben sich jetzt hier berührt. Was sicherlich kein kürzester Weg
31:21
mehr sein kann, ist irgendwas, was so geht, zu so einem Knoten hier vielleicht und hier zu einem Knoten, der von beiden nicht berührt worden ist und hier lang weitergeht. Warum kann das kein kürzester Weg sein?
31:43
Weil dieser Knoten, wenn ich den mal W Strich nenne, die Distanz zu S, weil dieser Knoten W vor W Strich genommen wurde, kann die Distanz von S nach W Strich nur größer gleich der Distanz von S nach W sein und gleichzeitig, mit dem selben Argument, wir sind ja in einer völlig spiegelsymmetrischen
32:01
Situation, kann die Distanz von W Strich nach T höchstens so muss sie mindestens so groß sein, wie die von W nach T, weil wir ja W genommen haben in dieser Iteration und W Strich ist noch weit draußen. Und natürlich kann man das weiter argumentieren, in irgendeiner Situation, wo hier viele Knoten noch
32:22
sind außerhalb des Bereichs, können alle nicht sein. Was aber noch sein kann und was man tatsächlich nicht ausschließen kann, was tatsächlich richtig sein kann, ist, sind zwei Knoten, die hier mit einer Kante verbunden sind.
32:43
Dieser Bereich hier, ja, da gilt dieses Argument, das ich eben gebracht habe, hier für das W Strich, natürlich nicht. Und das kann auch tatsächlich sein, dass wir, dass nicht das hier das Kürzeste ist, der Weg über W, sondern der Weg über diese Kante von S nach T.
33:02
Macht aber nichts, weil wir haben ja diese Situation genau in der Hand. Natürlich können wir uns alle Kanten angucken, deren Startknoten in der einen Suchmenge drin ist, schon abgearbeitet, und deren Endknoten in der anderen Suchmenge ist schon abgearbeitet. Und dann gucken wir uns an,
33:21
ist das hier der kürzeste Weg über das W oder ist einer von diesen Konstruktionen der kürzeste Weg? Wir haben die ja direkt in der Hand, wir müssen die gar nicht groß suchen. Alle Kanten, deren Startknoten in der linken Menge und deren Endknoten in der rechten Menge ist, sind noch Kandidaten.
33:40
Und daraus wählen wir was aus. Und das sagt dieser letzte gezeigte Spiegelstrich hier. Ist entweder der Pfad von S nach W plus dem Pfad von W nach T. Oder ein Pfad, der über eine Kante, über eine einzelne Kante, von der linken Suchmenge
34:00
zur rechten Suchmenge springt. So auch hier wieder, das ist eine Beschleunigungstechnik, aber nicht in Bezug auf asymptotische Komplexität. Asymptotische Komplexität ist natürlich weiterhin dieselbe, aber das funktioniert natürlich schneller,
34:21
wenn Sie sich das hier ansehen. Wenn Sie nur von einem der beiden Knoten von S nur losgegangen wären, was hätten Sie denn dann? Dann hätten Sie einen so großen Bereich abgesucht. Zwar nur einen Zirkel hätten Sie abgesucht, nur einen Kreis, aber der wäre viel, viel größer gewesen.
34:41
Wenn ich wieder dieses Bild, diese Intuition beanspruche, diese Fläche von diesem einen Kreis wäre natürlich viel, viel größer, als diese beiden Flächen zusammengenommen. Und deshalb ist es in der Praxis tatsächlich eine gute Beschleunigungstechnik.
35:03
Zielorientierte Suche ist noch was Interessantes. Das hatte ich in der GDE2 letztes Semester gebracht, aber ich glaube, in früheren Semestern wurde das behandelt. Goal or directed search, Zielorientierte Suche. Bitte?
35:23
In der GDE2 meine ich. Okay, dann erzähle ich das hier. So, die Intuition, hier nochmal, konzentrische Kreise. Die Deichstraße wie ein Stein in den See reinwerfen und die Wellenfront breitet sich in alle Richtungen gleichmäßig aus.
35:43
Das ist die Intuition. Und die Intuition hinter Zielgerichteter Suche ist, sie haben hier
36:06
S irgendwo, sie haben hier irgendwo T und sie wollen jetzt diese Kreise verfälschen. Sie wollen diese Kreise zu Ellipsen machen. Das heißt also, anstatt hier konzentrisch geht es weiter, ich mache mal
36:21
ein bisschen mehr in die Mitte, so. Anstatt dass es hier konzentrisch auseinander geht, wollen sie naja, wollen sie solche Ellipsen haben, die sich sehr, sehr, sehr viel langsamer nach links, weg von T, ausbreiten
36:42
als zu T hin. Mit dem offensichtlichen Ergebnis, dass sie weniger Knoten berühren müssen, bearbeiten müssen, um zu T zu kommen. Das ist die Idee. Was, wie kommt man da hin?
37:01
Der Gedanke ist der, dass man an den Kantenlängen manipuliert.
37:27
Sie haben hier irgendwo wieder S, sie haben hier irgendwo T und sie haben irgendwelche Kanten. Zum Beispiel irgendwo im Grafen eine Kante von
37:40
V nach W. Die Idee ist, die Kantenlängen so zu manipulieren, dass eine Kante, die tendenziell in Richtung T zeigt, gekürzt wird, also die Kantenlänge reduziert sich und eine Kante, die tendenziell, natürlich nicht 100% genau, aber tendenziell in Richtung
38:02
S zeigt, so wie ich das hier angedeutet habe, dass diese Kantenlänge verlängert wird. Und Kanten, die neutral sind, zum Beispiel, die so genau orthogonal zum Weg von S nach T sind, die würden dann auch, da würde sich nichts ändern.
38:21
Das ist die Idee. Die Frage ist, wie kriegen wir das hin? Wie können wir die Kantenlängen so ändern, dass 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
38:41
manipulierten Kantenlängen, wenn wir da einen kürzesten Weg rauskriegen, dass das natürlich auch ein kürzester Weg für die ursprünglichen Kantenlängen ist. Es macht natürlich keinen Sinn, wenn wir da ein völlig anderes Ergebnis rauskriegen. So, wie kriegen wir das jetzt hin? Überraschend einfach.
39:02
Wir nehmen, wir für jeden Knoten U, berechnen wir eine untere Schranke für die Weglänge, die man von U bis T braucht. Das ist in einem geografischen Bereich ganz einfach. Sie nehmen einfach die euklidische Distanz. Die kann, kürzer, kann die echte Weglänge nicht sein.
39:21
Oder wenn Sie Fahrminuten hernehmen als Zielkriterium und nicht Distanz, nicht geometrische Distanz, dann müssen Sie halt gucken, eine ordentliche untere Schranke dafür, wie viel Minimum die Fahrt von da nach da kostet. Ja, also indem Sie zum Beispiel auch die euklidische Distanz hernehmen
39:41
und sich Tempo 130 annehmen. Also stellen Sie sich vor, Sie haben eine Autobahn mit Tempo 130. Wenn Sie nichts anderes einstellen, ist 130 die Geschwindigkeit, die das Navi zugrunde legt, typischerweise, wenn Sie auf der Autobahn fahren, ohne Tempolimit fahren.
40:01
Also Sie nehmen, man kann das untere Schranke hernehmen, die euklidische Distanz mit Tempo 130. Dann ist das mit Sicherheit eine untere Schranke. Man kann es natürlich auch noch intelligenter die untere Schranke hochtreiben. Je mehr man sie hochtreibt, umso besser funktioniert es. So, aber irgendeine untere Schranke
40:20
haben wir. Und wir wollen, dass das der Fall ist. Das, was hier steht, ist letztendlich die Dreiecksungleichung, die Sie aus der Mathematik kennen. Also natürlich nur eine spezifische Situation der allgemeinen
40:42
Dreiecksungleichung. Denn, wenn ich diese
41:04
verschiedenen Werte mal abtrage, nehmen wir mal an, wir nehmen wirklich die euklidische Distanz. Ja, wir nehmen Distanz näher. Da wird es am einfachsten sichtbar. Wir haben eine Kante von einem Knoten U zu einem
41:21
Knoten V. Hier hinten haben wir irgendwo T. Und wir haben die die Streckenlänge B U T. Und hier die Streckenlänge B V T. Dann sehen Sie unmittelbar und diese Kante hat natürlich
41:41
die Länge C U V. So, jetzt haben wir alles abgetragen, was in dieser Formel drin ist. Und Sie sehen natürlich sofort, hier dank der Dreiecksungleichung, dass nichts anderes gesagt wird, als dass diese Länge kleiner gleich dieser Länge plus dieser Länge ist.
42:01
Ja, also wenn Sie zum Beispiel das hier als geometrische, das hier als euklidische Distanz haben, das euklidische Distanz, das euklidische Distanz als einfachstes Beispiel, dann ist das unmittelbar einsichtig. So, was wir jetzt machen ist,
42:20
jetzt habe ich dieses Bild dummerweise gelöscht. Vielleicht zeichne ich das Bild nochmal an.
42:42
Was wir jetzt machen ist, Sie erinnern sich eben, hier ist S, hier ist T und wir haben jetzt verschiedene Situationen für die Kanten. Von V nach W, oder wie haben wir hier die genannt? Hier haben wir sie von U nach V genannt auf der Folie, sollte ich konsistent sein. Einmal so rum, oder einmal so rum
43:02
von U nach V, oder neutral von U nach V, diese drei Fälle. So, diese Formel hier besagt die neue Länge, C' von dieser Kante, ist die alte Länge
43:21
verrechnet mit den beiden Distanzen, diesen beiden Unterschranken B, U, T und B, V, T. Und wenn Sie sich das mal genau angucken, B, U, T steht im Minus, B, V, T steht im Plus, das heißt also, wenn die Kante hin zeigt zu T, wenn also die Distanz von V nach T,
43:42
diese untere Schranke, kleiner ist als die Distanz von U nach T, dann reduziert sich das tatsächlich. Kann man das lesen? Dann reduziert sich das tatsächlich, dieser Wert ist größer als der, das ist insgesamt negativ. Wenn hingegen die Kante
44:00
weg zeigt, dann ist der positive Term größer als der negative Term, die Kante bleibt gleich. Und wenn im neutralen Fall, dass beide B-Werte gleich sind, ändert sich nichts. Es sind die neuen Kantenlänge, die alten Kantenlänge. Genau das erreicht. Warum ist das jetzt, warum können wir jetzt damit einfach
44:21
mit diesen C' anstelle der C arbeiten? Warum, also die Behauptung ist, wenn ich jetzt die Kantenlängen, die ursprünglichen Kantenlängen C durch die neuen Kantenlängen C Strich ersetze, und ich kriege dann kürzester Weg raus, dann ist die Weglänge vielleicht noch verkehrt, aber der Weg ist der richtige.
44:42
Der Weg, den ich da rauskriege. Warum ist das so? Wir betrachten mal, irgendeinen Fahrt von S nach T. Jetzt muss ich mal ganz kurz spülunzen, ob nicht diese Formel,
45:03
ja, es ist nur, es ist nur angedeutet, ich will es mal richtig machen. Wir betrachten irgendeinen Weg von S nach T.
45:21
S, sage ich, soll gleich V1 sein, der erste Knoten, das ist V2, der zweite Knoten, das ist V3, der dritte Knoten, kann ja ein beliebiger Weg sein, kann auch Umwege machen, ist vollkommen egal, V5 und so weiter, bis zu einem Knoten Vk-1
45:40
und dann zum Knoten Vk, gleich T. Ja? Was ist die Länge dieses Pfades in Bezug auf die neuen Kantenlängen?
46:01
Ich mache das vielleicht ein kleines bisschen weniger exzentrisch hier runter, damit man da noch ein bisschen was sehen kann. So, V4, V5 und dann geht es bis dahin.
46:39
So, was ist die Länge dieses
46:40
Pfades? Das ist die Summe, I gleich 1 bis K minus 1 von C Strich, neue Weglänge, Vk, nein, Vi, Vi plus 1.
47:00
Ja, das ist die neue Weglänge, dieses Weges. Kann man das lesen? Okay. Ja, ich habe einfach über, deshalb habe ich die induziert, indiziert, nicht induziert, sodass ich das einfach so hinschreiben kann. So, das kann ich jetzt auseinanderdröseln, so wie ich die C Strich definiert habe.
47:21
I gleich 1 bis K minus 1, C Vi, Vi plus 1 und da kommt jetzt noch was hinzu. Minus, jetzt muss ich nochmal abgucken,
47:41
wie rum das war, damit ich nichts falsch mache. Erst das erste Startknoten, also B Vi, T plus, ne, damit das gut aufgenommen werden kann, muss ich das auf die nächste Zeile bringen, sonst
48:01
klappt das mit der Kamerabereiche nicht. So, das ist gleich Summe, I gleich 1 bis K minus 1, wieder von C Vi,
48:20
Vi plus 1 minus B Vi, T plus B Vi plus 1, T. Ja, einfach nur die Definition der neuen Kantenlängen, C Strich eingesetzt.
48:41
Hoffentlich richtig. So, jetzt gucken Sie sich das mal an, jeder dieser B-Werte, fast jeder dieser B-Werte kommt zweimal vor. Einmal Positiv-Vorzeichen und einmal Negatives Vorzeichen. Das ist eine Teleskopsumme, falls Sie diesen Begriff in der Mathematik gehört
49:01
haben. Teleskopsumme heißt, dass die Individuition dahinter ist, dass man die ganze Summe sowie so ein Teleskop zu einem einzigen Lied zusammen drücken kann. Und genau das passiert hier. Das was hier nur einmal vorkommt, ist
49:20
bei S und bei T. Das heißt, dass alles, was hier steht, reduziert sich auf I 1 bis K minus 1 von den ursprünglichen Kostenwerten. Ja, das, was hier steht jetzt, ist die ursprüngliche Weglänge
49:41
oder die Weglänge desselben Fahrt nach den ursprünglichen Kosten minus B von S T plus B von T T. Alles andere fallen weg, weil jedes andere B Glied einmal mit Positiven und einmal mit Negativen Vorzeichen vorkommt.
50:02
Das ist die Idee einer Teleskopsumme. Alle diese Glieder hier zu einem einzigen Glied zusammengeschoben. Das hier ist aber konstant. Hängt nicht vom Weg ab. Das ist der entscheidende Punkt. Der Unterschied
50:20
zwischen der ursprünglichen Fahrtlänge hier und der neuen Fahrtlänge hier, ist dieser konstante Term, der nicht von einem Fahrtlänge angeht. Das bedeutet, ein kürzester Fahrt nach neuen Fahrtlängen ist zugleich ein kürzester Fahrt nach alten Fahrtlängen. Weil, wenn
50:42
ein Fahrt hier kürzer als ein anderer Fahrt ist, ist er auch nach hier kürzer als der andere Fahrt. Weil sie sich jeweils nur um diesen konstanten Term unterscheiden. Und damit haben wir unser Ziel erreicht. Haben wir diese Beschleunigungstechnik fertig. Ist doch schön, oder?
51:08
So, die Distanzwerte haben natürlich einen etwas anderen Wert. Also die Länge, die rauskommt, ist nicht korrekt, aber Sie sehen ja, die Länge, die rauskommt, hier, als kürzester Fahrtlänge, wenn Sie diesen Term davon abziehen,
51:22
kriegen Sie die ursprüngliche Länge wieder raus. So, das nächste, also hier sehen Sie nochmal eine Intuition, wie das aussehen kann. Statt Dijkstra, wie hier, ganz normal, möglichst schon in diese Richtung, möglichst in die Richtung von T gehen. A Stern lassen wir aus, das ist ungefähr
51:42
dasselbe. Nur ein kleines bisschen komplizierter, brauchen wir jetzt hier nicht zu betrachten. Zumal A Stern durchaus in der Literatur unterschiedlich definiert ist. Also verschiedene Algorithmen werden mit dem Begriff A Stern benannt. Aber noch hier ein interessanter Punkt, den man sich auch merken kann,
52:00
Pre-Processing. Ich sag Ihnen einfach mal mit einer Zeichnung, was hier auf dieser Folie steht. Oder ein Beispiel dafür, was man sich darunter vorstellen kann. Eine Möglichkeit,
52:27
wie man das auf dieser Folie, diese Folie, wir sind jetzt wieder
52:40
bei der Situation, dass wir von S nach T wollen. Aber wir betrachten jetzt mal die Situation allgemeiner. Wir haben eine Kante, die geht von irgendeinem Knoten aus. Hier ist irgendwo S und die geht jetzt irgendwo hin.
53:02
Und was wir in diesem Pre-Processing vorab berechnen, ist eine Knotenmenge, von der wir sicher sind, nur Knoten in dieser Knotenmenge, nur bei Knoten in dieser Knotenmenge, wenn wir die suchen, brauchen wir diese Kante überhaupt anzufassen. Also wir sind jetzt in einem
53:21
Szenario, wo wir nicht eine Suche machen von S zu einem T, sondern zu vielen T's vielleicht. Nacheinander. Und wir wissen nicht vorher, zu welchem T das jeweils ist. So, eine Möglichkeit zum Beispiel ist, dass wir versuchen, wenn wir im geografischen Bereich sind,
53:40
wenn wir in einem geografischen Bereich sind, dass wir versuchen diesen Sektor hier, einen Sektor zu berechnen, vorab im Pre-Processing, sodass alle Knoten W, zu denen der kürzeste Weg von V nach W über diese Kante läuft,
54:01
in diesem Sektor sind. Das heißt also, alle Knoten W, die nicht in diesem Sektor sind, von denen wissen wir, der kürzeste Weg von V zu diesem W wird nicht über diese Kante gehen, sondern über irgendeine andere Kante. Ist uns egal, welche, aber definitiv nicht über diese Kante.
54:22
Ja, das kann man ja leicht berechnen. Wir berechnen vorher vorher im Pre-Processing alle kürzesten Wege mal, und dann wissen wir ja, von welcher dieser kürzesten Wege diese Kante benutzen und welche, die nicht benutzen. Ist ein bisschen aufwendig, aber im Pre-Processing stört es nicht unbedingt. Ja, Pre-Processing macht es nicht aus,
54:40
wenn es mal vier Wochen durchrechnet, vorausgesetzt, dass dann im tatsächlichen Ablauf dann, wenn es darum geht, dann die Suche deutlich beschleunigt werden kann dadurch. So, das heißt also, wenn wir an diesem Knoten V sind,
55:01
dann gucken wir uns jede Kante, und wir wollen den kürzesten Weg hier, nennen wir es mal T und T-Strich, und wir wollen den kürzesten Weg jetzt zu diesem T finden oder zu irgendeinem Knoten finden. Dann gucken wir uns alle Kanten an, die von vorausgehen und zu jeder dieser Kante haben wir uns die beiden Winkel gemerkt, die
55:21
diesen Sektor aufspannen und wenn das T, das wir suchen, in diesem Sektor drin ist, was ja leicht mit ein bisschen Geometrie herauszubekommen ist, mit ein bisschen Trigonometrie, dann nehmen wir diese Kante hinzu,
55:40
wenn aber, so wie hier, dieses T-Strich außerhalb dieses Sektors ist, dann vergessen wir diese Kante und haben damit die weitere Suche von dieser Kante aus gespart. Welchen Punkt, also die Frage war, für die Nachwelt die Frage war, wie realisiert man das?
56:01
Welcher Punkt der Realisierung ist unklar? Wie man sieht, diesen Sektor, also an jeder Kante haben Sie die beiden Winkel als Attribute irgendwie dran. Sie haben die Kante in der Hand, und da hängen die Attribute zum Beispiel dran.
56:22
Geometrisch ist ein Beispiel, wir kommen gleich noch zur Verallgemeinerung. Wenn wir jetzt im geometrischen Bereich sind, wenn wir jetzt auf einer Fläche sind, auf einer Ebenen, wie zum Beispiel der Erdoberfläche, okay, die Erde ist flach, ja, ich weiß.
56:41
Wenn, wir merken uns zu dieser Kante die beiden dazu, und wenn wir jetzt von T haben auch die Koordinaten, wir haben die Koordinaten von V, wir haben die Koordinaten von T, und dann können wir natürlich mit einfachster Schulmathematik berechnen, ob T in diesem Sektor drin ist,
57:00
von V als Nullpunkt, als Referenzpunkt, mit diesen beiden Winkeln, oder so wie diese Tstrich, ob es nicht drin ist, und dementsprechend ist die Entscheidung. So, das kann man natürlich auch verallgemeinern. S von A
57:22
ist die Menge von Knoten, die, wie ich eben, ach so, vielleicht umgekehrt. Das heißt natürlich nicht, dass jeder Knoten T dass da der kürzeste Weg über diese Kante geht. Es kann auch Knoten geben T, die sind in diesem Sektor drin,
57:41
aber geht nicht über diese Kante. Dann haben wir halt zu viel Arbeit gemacht. Ja, ich meine, dieser Sektor wird aufgespannt, hier irgendwo ist ein Knoten, von dem wir wissen, dass der kürzeste Weg von V über diese Kante geht, und hier irgendwo ist ein Knoten, von dem wir wissen, dass es über diese Kante geht, und wenn das die beiden extremsten sind,
58:03
dann definieren die beiden den Sektor. Aber da können natürlich auch Knoten sein, wo der kürzeste Weg anders verläuft. Sodass wir dann also diese Kante umsonst mit reingenommen haben in die Suche. So, S von A ist die Menge aller Knoten,
58:21
sodass der kürzeste Pfad diese Kante A benutzt, wie ich das eben gezeichnet habe. Dieses C von A, dieser Container, der S von A enthält, das wäre in meinem geometrischen Beispiel hier die Menge
58:40
aller Knoten, die in diesem Sektor drin sind, wie eben gesagt. Das ist potenziell eine echte Obermenge, weil es auch Knoten in diesem Sektor geben kann, für die diese Kante nicht wichtig ist. Aber das können wir nicht weiter auseinander differenzieren. So, wir brauchen
59:03
den Algorithmus nur weiterzuführen von der Kante A aus in die Richtung Zielknoten, wenn der Knoten, wenn der Zielknoten, den wir haben wollen, in diesem Container drin ist, der eine Obermenge ist von der Menge der Knoten,
59:22
für die diese Kante A wichtig ist. Wichtig ist natürlich, und dafür war das jetzt eben ein Beispiel, dieses geometrische Beispiel, dass dieses Enthaltensein effizient getestet werden kann. Und, dass man die Art und Weise, wie man den Container speichert, dass das nicht zu viel Speicherplatz kostet.
59:41
Und das ist in diesem Fall, in diesem konkreten Anwendungsszenario gegeben. Man kann sehr effizient testen, ob T im Sektor drin ist, oder T' nicht im Sektor drin ist. Und der Aufwand, um das zu speichern, diesen Container, das ist einfach für jede Kante diese beiden Winkel. Das ist gar nichts.
01:00:06
So, hier ist noch ein anderer Fall, die Bounding Box von S von A, also wenn man hier hinter dieser Folie steckt offenbar eine andere Vorstellung als das, was ich jetzt hier eben skizziert hatte, wie man das machen kann, nämlich was hier hinter der Folie steht, ist die Vorstellung, sie haben wieder die Kante V, ja, so.
01:00:36
Und sie haben jetzt hier irgendwo die Knoten, inklusive dem natürlich, wenn die Knotenmenge nicht leer ist, die Knoten, die
01:00:48
von V aus, wo diese Kante wichtig ist, anfangsweg ist von V aus so einen kürzesten Weg zu diesen Knoten. Und was hier vorgeschlagen wird auf der Folie ist, dass man hier von die Bounding, ja, das ist
01:01:03
es nicht, nicht unbedingt die rechteckige Bounding Box, sondern zum Beispiel die echte Bounding Box, also die konvexe Hülle, oder auch als Bounding Box ist eigentlich eher die rechtwinklige, das kleinste Rechteck, was alle diese Knoten umfasst.
01:01:22
Das ist natürlich auch ein bisschen unscharf, ja, da können natürlich noch irgendwelche Knoten drin sein, auch hier können irgendwelche Knoten drin sein, die nicht diese Kante benötigen, aber das ist der Preis, den man zahlen muss. Genaue Trennschärfe wird man in der Regel nicht bekommen.
01:01:41
So, und die Aussage ist wieder, dass man da zu einer ernsthaften Beschleunigung kommen kann, empirisch, also nicht mehr mathematisch, sondern man implementiert es und schaut, was passiert. So, letzte Speed-Up-Technik ist hier nur angedeutet, darüber kann man eine ganze Vorlesung halten, über diese Speed-Up-Techniken, wenn Sie von irgendeinem Punkt zu irgendeinem anderen Punkt wollen.
01:02:08
Also von Darmstadt beispielsweise sagen wir ja zu irgendeinem Punkt in Schleswig-Holstein, weit weg vielleicht, Flensburg oder so, oder was auch immer.
01:02:20
Dann ist ja das im Normalfall so, dass Sie erstmal mit einer ganz kleinen untergeordneten Straße starten, so eine mittlere Straße weiter, noch eine übergeordnete Straße, vielleicht schon Autobahn, dann bleiben Sie auf der Autobahn, bis Sie dann kurz vor einem Ziel wieder auf eine Straße von mittlerer Ordnung, vielleicht
01:02:43
eine Bundesstraße oder sowas, gehen und dann in die kleine Sackgasse reinfahren, wo Ihr Zielort ist, also eine ganz untergeordnete Straße. So ein Weg wird typischerweise hierarchisch sein und wenn Sie das vielleicht auch mit Bahnverkehr betrachten, die typische Situation ist, Sie
01:03:03
steigen in einen Bummelzug ein, dann vielleicht in der Region oder was, dann in die CE und dann wieder das Ganze zurück. Stimmt nicht immer. Ein schönes Schlagendes Beispiel ist Paris, wo Sie an einem Bahnhof ankommen, dann mit der Metro weiterfahren und dann am anderen Bahnhof wieder weiterfahren.
01:03:23
Können Sie aber auch in Deutschland haben. Sie wollen beispielsweise von Darmstadt, wo wollen wir hin, nach Offenburg oder Freiburg, dann fahren Sie bis Heidelberg, viele Verbindungen die vorgeschlagen werden sind so, bis Heidelberg fahren Sie mit dem IC, dann fahren Sie mit der S-Bahn, mit der S3 nach Karlsruhe und dann fahren Sie mit dem ICE oder IC wieder weiter bis Freiburg.
01:03:44
Ja, also stimmt nicht ganz, aber es ist ungefähr die Intuition und die Idee ist, dass man das gesamte Straßennetz oder Bahnnetz oder was auch immer zerlegt in verschiedene Hierarchiestufen und dass man versucht solche Wege zu konstruieren,
01:04:07
erst untergeordnete Wege im lokalen Bereich, dann rauf auf die Autobahn und ab bis Flensburg und erst in Flensburg wieder runter. Problematik hier ist, wenn Sie hier zum Beispiel in dem Bereich starten, haben Sie mindestens
01:04:27
zwei Anschlussstellen, einerseits Darmstadt-Mitte, einerseits Eberstadt oder wenn Sie hier in dem Bereich starten, vielleicht irgendwie hier, könnten Sie noch die dritte hier vielleicht interessant sein, da oben, was ist das, da oben,
01:04:41
ist ja auch egal, Sie wissen, weiter Stadt, ja genau, oder Sie stellen sich das mit der Bahn vor, Sie stellen sich das mit der Bahn vor, Sie beginnen erst mit einem Fußweg als untergeordnete Art der Verbindung, dann mit einer Straßenbahn oder Bus, dann mit der DB und an Ihrem Zielort steigen Sie wieder in den Nahverkehr um.
01:05:07
Da muss dann der Algorithmus damit klarkommen, dass es auch von Darmstadt aus nicht den einen natürlichen Startbahnhof von DB gibt. Es kann der Hauptbahnhof sein, es kann der Nordbahnhof sein, es kann der Ostbahnhof, es kann auch der Südbahnhof sein. Ja, alle diese Möglichkeiten gibt es.
01:05:27
Gut, da will ich jetzt nicht weiter drauf eingehen, ich will nur, dass Sie das mal gesehen haben. So, what is going on behind the scenes, wieder mal irgendwelche Rechenoperationen, Sie sehen hier die Zeit, die CPU-Zeit und hier die Anzahl der Priority-Q-Schritte.
01:05:50
Wie schnell die einzelnen Algorithmen sind, hängt natürlich auch sehr stark von der Implementation ab und vom Tuning, von der Programmiersprache, von der Mondphase und was auch immer.
01:06:05
So, Label-Correcting-Algorithms, haben wir schon mal gesehen. Die Grundoperation ist dieselbe wie bei Dijkstra, das ist die gemeinsame Basis von
01:06:21
Dijkstra, Bellman-Ford, Flaut-Warschel, was immer Sie in der GDE2 gesehen haben. Da passiert überall dasselbe. Sie gucken sich eine Kante an und wenn der momentane Distanzwert des Zielknots dieser Kante größer ist als momentaner Distanzwert des Startknots dieser Kante plus Länge der Kante, dann setzen Sie entsprechend diesen Distanzwert runter. Warum? Das hier ist die Länge eines Pfades, du plus Länge der Kante von u nach v.
01:06:49
Das ist die Länge eines Pfades, aber offensichtlich nicht die kürzeste Weglänge. Das ist jetzt eine kürzere. So, das ist vielleicht immer noch nicht die kürzeste, aber Sie können keine Fehler machen, wenn Sie diese Distanz von v, von diesem Knoten v,
01:07:03
runter setzen auf die Länge des Weges. Weg von Startknoten nach u plus Länge von u nach v. Kann man nichts falsch machen. Hat man wieder einen Schritt vollbracht näher in die Richtung zu den kürzesten Wegen.
01:07:21
So, und hatten wir auch schon betrachtet, wir setzen alles auf unendlich und die letzte Kante hier des kürzesten Weges, da wir noch keine kürzesten Wege haben, setzen wir sich auf null alle, also auf void. Gut, Temporal Labeled, das haben wir ja schon bei Dykstra gesehen.
01:07:44
In dem Moment, wenn sie zum ersten Mal berührt werden, kriegen sie ein endliches Label, vorher noch ein unendliches Label, sind aber nicht permanent gelabelt und das ist der Unterschied zu einem Algorithmus wie Dykstra, hat ich kurz, glaube ich, letztes Mal gesagt, bis der Algorithmus zu Ende ist, sind sämtliche Distanzwerte temporär.
01:08:05
Bei Dykstra ist es anders. In jeder Iteration wird ein Distanzwert auf Fest in Stein gemeißelt gesetzt. Das ist bei diesen Algorithmen, da gehören Bellman-Ford und Floyd Warschall dazu, nicht der Fall. Negative Kantenlängen haben wir beim letzten Mal betrachtet, werde ich jetzt dieses Beispiel nicht weitergehen.
01:08:24
Dykstra funktioniert nicht mit negativen Kantenlängen. Es muss nicht mal ein negativer Zykel sein, es reicht schon, negative Kantenlängen zu haben, dass Dykstra nicht funktioniert. So, die Idee ist also, dass wir uns bis zum Ende aufsparen, die Distanzwerte wirklich festzusetzen, festzuzurren und nicht mehr zu ändern.
01:08:51
Deshalb hier, at any intermediate stage, ist der Distanzwert, der da steht, eine Oberschranke. Es ist nicht kleiner als die echt kürzeste Distanz von S zu diesem Knoten.
01:09:09
So, dieses Theorien ist noch mal vielleicht, wenn Sie sich das anschauen im Vergleichen, ist vielleicht noch mal eine Rechtfertigung für diesen Korrekt-Schritt, den Sie hier haben. Wenn hier ein Größer steht, sorgt man dafür, dass kein Größer mehr steht, weil dieses Theorien sagt,
01:09:33
wir haben die Distanzlängen, wir haben die Längen von gewissen Pfaden.
01:09:41
dV ist die Länge eines Gewiss, irgendeines Pfades von S nach V muss nicht der kürzeste Weg sein. Hier ist eine Äquivalenz. Alle diese dV-Werte, alle, für alle Knoten V zusammengenommen, sind die kürzesten Wege-Distanzen für alle diese Knoten, genau dann, wenn diese Bedingung für jede Kante gilt.
01:10:03
Warum ist das so? Die Einrichtung, meistens ist es ja so, dass die Einrichtung nicht allzu kompliziert ist, wenn die dVs alle tatsächlich kürzeste Wege-Distanzen sind,
01:10:20
naja, was steht denn da?
01:10:43
Wir haben hier irgendwo S, wir haben hier irgendwo U und wir haben hier irgendwo V und die Länge eines kürzesten Weges von, also wir sagen jetzt, dass die d-Werte tatsächlich die Länge eines kürzesten Weges sind, das heißt hier, das hier, die Länge eines kürzesten Weges von S nach U,
01:11:06
ist hier dU und die Länge eines kürzesten Weges, wie immer der aussehen mag, ist dV, von S nach V, so. Dann ist natürlich klar, dass dV kleiner gleich dU plus Länge uV sein muss,
01:11:30
denn dV ist die Länge eines kürzesten Weges und das hier, was hier steht, ist die Länge eines anderen Weges von S nach V, irgendeines Weges. Könnte zufällig auch ein kürzester Weg sein, dann haben wir das mit Gleichheit erfüllt.
01:11:43
Wenn es kein kürzester Weg ist, ist es eine echte Ungleichheit. Aber jedenfalls ein kleiner Gleich, so oder so. Das heißt, diese Richtung ist ganz einfach. Wenn die ds alle kürzeste Distanzlabels sind, dann gilt für jede Kante uV diese Gleichung.
01:12:02
So, jetzt gucken wir uns mal die andere Richtung an.
01:12:33
Jetzt gehen wir davon aus, dass die Distanzlabel, diese d, mit irgendwelchen Knoten,
01:12:56
sind nicht alle kürzeste S von, also dV, S von V Fahrtlängen.
01:13:17
Ja, das ist die genaue Negation. Die ds, die eine Richtung ist, die ds sind alle, allesamt Fahrtlängen, kürzeste Wege von S zu den einzelnen Knoten.
01:13:29
Und die Negation, das Umgekehrte ist, es sind nicht alle davon kürzeste Fahrtlängen. So, und was wir zu zeigen haben, es gibt eine Kante uV, für die das nicht gilt.
01:13:56
Wo also tatsächlich d von V echt größer d von u plus Länge von u nach V ist.
01:14:09
Ja, Sie erinnern sich das Theorem, was das besagt. Die ds sind genau dann, allesamt kürzeste Weglängen von S zu den einzelnen Knoten, genau dann, wenn für jede Kante, für jede einzelne Kante gilt, dass die Ungleichung so herum ist.
01:14:25
dV kleiner gleich die u plus Kantenlänge. So, wenn ich jetzt die andere Richtung, diese Richtung, wenn das alles kürzeste Weglänge gilt, dann ist das so. Dann gelten alle diese Ungleichungen für alle Kanten, das haben wir eben gesehen. Jetzt sind wir in einer anderen Richtung, genau andersherum.
01:14:40
Wenn das nicht alles kürzeste Wege sind, dann gibt es mindestens eine Kante, für die das nicht gilt. Das ist die exakte logische Umkehrung. So, und die konstruieren wir uns. Das ist diese Kante uV, indem wir sagen, immer weniger Wasser drin in dem Teil.
01:15:20
Ich muss vielleicht doch nochmal nachladen.
01:15:41
Diese Kante konstruieren wir uns. Wir haben hier irgendwo S. Wir haben hier irgendwo V. Und wir nehmen W, also noch einen weiteren Knoten.
01:16:05
Und wir suchen uns ein D raus, sodass dV nicht die kürzeste Fahrtlänge von S nach W ist.
01:16:23
Ja, so haben wir die Annahme, dass es mindestens sowas gibt. Dann gucken wir uns den kürzesten Weg an, von S nach T. Irgendwo gibt es dann eine Situation V, u, wo hier D u ist tatsächlich, ist gleich.
01:16:56
Ich kürze das mal ab, kürzeste Fahrtlänge von S nach u.
01:17:08
Und D von V ist nicht gleich kürzeste Fahrtlänge von S nach V. Irgendwo muss das mal passieren.
01:17:21
So, das heißt, es gibt hier einen kürzesten Fahrt, einen kürzeren Fahrt hier lang. Das ist der kürzeste Weg von S nach V, ist nicht der hier. Und das heißt, für diese Kante kann das dann nicht mehr, habe ich das jetzt richtig herum gedacht?
01:17:45
Genau, für diese Kante kann das nicht mehr gelten, weil das ist dann echt größer. D von V ist echt größer, muss echt größer sein, weil es die Länge eines Fahrtes ist.
01:18:05
Genau, und deshalb, dieses D u ist die kürzeste Länge, das ist die Länge eines anderen Fahrtes, der größer ist. Richtig? Und deshalb muss insgesamt ein größer dabei rauskommen.
01:18:21
Habe ich mir das richtig überlegt? Ich glaube schon. Entschuldigung? Genau, das ist der Fahrt, der D von V konstituiert. Genau, jetzt noch der wichtige Punkt dabei. Jetzt weiß ich wieder, das ist ein kürzester Weg von S nach V.
01:18:41
Sodass das auch ein kürzester Weg von S nach V sein muss. Das war noch der Punkt, den ich vergessen hatte. Und dann geht es auf. Was der Hersteller so alles nicht auf die Folien geschrieben hat. Was ich mir, armer Dozent, ich weiß, ich werde bezahlt dafür, was ich mir trotzdem als armer Dozent so alles noch überlegen muss.
01:19:07
So, Generic Label Correcting Algorithm ist dann einfach auf dieser Basis. Gucken Sie sich das an, kommt Ihnen bekannt vor alles, nicht? Wir wollen von S auf, wir sind immer noch in der Situation, wir sind nicht All Pairs,
01:19:21
wir sind immer noch in der Situation von S aus in einem D-Grafen, einem Gericht in Grafen D mit Kantenlängen C von S aus zu allen anderen Knoten, Wege, kürzeste Fahrtlängen zu berechnen. So, wir fangen wie üblich an. Alle Knoten außer S erhalten plus unendlich als Distanz.
01:19:43
S erhält wie üblich Null als Distanz. Und da wir jetzt noch keine Pfade gefunden haben, sind die entsprechenden Pointer wie üblich erst mal void. So, und dann machen wir einfach Folgendes. Solange es noch eine Kante gibt, am Anfang gibt es natürlich viele solcher Kanten,
01:20:03
aber solange es noch so eine Kante gibt, solange korrigieren wir das, setzen den Wert V auf der linken Seite auf den Wert hier du plus Länge uv auf der rechten Seite.
01:20:21
Und in dem Moment, wenn diese Schleife abbricht, ist die Bedingung erfüllt. Es gibt keine solche Kante mehr, also bei allen steht hier statt größer kleiner gleich. Und wie wir eben gesehen haben in dem Theorem, ist das gleichbedeutend damit, dass die Distanzwerte alle kürzeste Weglängen sind. Ist doch schön, oder?
01:20:42
So, die Frage ist natürlich, ob das terminiert, ob diese Schleife terminiert, und wenn ja, wie viel Laufzeit die kostet, bzw. was man tun kann. Wir haben hier einen großen Freiheitsgrad drin. Wir haben hier nicht gesagt, in welcher Reihenfolge wir diese Kanten durchsuchen wollen. Und da steckt natürlich dann die Intelligenz drin.
01:21:04
Mit verschiedenen Reihenfolgen kriegt man verschiedene Laufzeiten raus. Teilweise asymptotisch verschiedene Laufzeiten, teilweise nur empirische Verbesserungen, Beschleunigungen, so wie eben. So, erstmal macht man sich klar, dieser Algorithmus terminiert in einer endlichen Anzahl von Iterationen.
01:21:25
Warum? Weil, wie wir eben schon gesagt haben, und das lässt sich leicht nochmal mit Vollständigkeit nachvollziehen, jeder Distanzwert ist immer die Länge eines gewissen Fahrtes von S zu diesem Knoten.
01:21:40
Ja, am Anfang ist das so, solange der Distanzwert nicht mehr plus unendlich ist. Das gilt für Induktionsanfang, es gilt für S. Null ist die Länge eines gewissen, sogar eines kürzesten Fahrtes von S nach S. Und so wie ein Knoten endlich wird, hier in der Schleife, so wie hier links D, V plus unendlich steht,
01:22:05
und er wird endlich, nach Induktionsvoraussetzung ist D von U immer die Länge eines Weges von S nach U. Dann ist natürlich D von U plus der Kantenlänge die Länge eines gewissen Weges von S nach V. Das heißt also, wenn wir D von V auf die rechte Seite hier setzen, ist das wieder die Länge eines gewissen Weges.
01:22:24
Es kann aber nur endlich viele Weglänge in einem endlichen Grafen greben von S nach V. Und die Distanzen werden immer kleiner, Schritt für Schritt echt kleiner in jedem Update. Das heißt also, keine Weglänge von S nach V wird zweimal durchlaufen.
01:22:44
Da zykelt nichts, sie werden einmal linear in echt absteigender Reihenfolge durchlaufen, die möglichen Distanzwerte. Und weil es nur endlich viele Wege gibt von S nach V, kann es nur endlich viele unterschiedliche Distanzwerte geben, nach endlich vielen Schritten terminiert der Algorithmus.
01:23:00
Ist noch nicht so prickelnd, dass er nach endlich vielen Schritten terminiert, aber immerhin besser als nichts. Jetzt geht's weiter. Man kann Beispiele konstruieren, das müssen wir jetzt hier nicht machen, wo die Laufzeit des Algorithmus tatsächlich exponentiell wird, wenn man die Auswahl der Kanten ungeschickt macht,
01:23:23
oder bei ganz dreiligen Kantenlängen kann man wieder argumentieren, naja, jede Pfadlänge ist irgendwo zwischen 0 und N mal C, das hatten wir am Anfang dieser Vorlesung heute schon mal.
01:23:40
Ja, C war die obere Schranke für alle Pfadlängen und N ist eine obere Schranke für die Anzahl der Kanten auf einem Pfad. Das heißt also, für einen Knoten V, die Pfade von S nach V, es kann nur N mal C unterschiedliche Pfadlängen geben, bei ganz zahligen Kantenlängenwerten.
01:24:05
Und der zweite Faktor N kommt daher, dass das natürlich für jeden einzelnen Knoten sein kann. So oft kann es einen Updateschritt geben. Für jeden Knoten kann es N mal C viele Updateschritte maximal geben, das wird natürlich niemals in der Praxis sein, aber theoretisch können wir das nicht besser beschränken.
01:24:21
Multipliziert mit der Anzahl der Knoten kriegen wir N Quadrat mal C raus. Ist aber immer noch nicht prickelnd, da sind wir von Dykstra eigentlich Besseres gewöhnt. So, wenn wir jetzt erst einmal das ganz einfach so machen, immer alle Kanten durchgehen,
01:24:45
in eine Liste halten und mal gucken, ob es irgendeine Kante gibt, die diese Bedingung, diese Optimalitätsbedingung verletzt. Das kostet natürlich sehr viel Laufzeit, weil wir dann die gesamten Kanten potentiell durchgehen müssen, die gesamte Kantenliste durchgehen müssen. Diesen Faktor M müssen wir noch hier drauf multiplizieren,
01:25:04
um die wahre Laufzeit zu haben. Ist also alles wirklich nicht sehr glücklich. So, jetzt können wir weitergehen. Wir speichern uns nicht eine Liste aller Kanten,
01:25:23
sondern wir speichern uns eine Liste von Knoten mit der Eigenschaft, dass wenn eine Kante diese Bedingung verletzt, dann ist dieser Knoten darin enthalten in dieser Liste und damit haben wir ein Faktor M geteilt durch N eingespart.
01:25:53
Das ist alles nicht so prickelnd. Wir sind hier in Laufzeiten drin, die jenseits von Gut und Böse sind,
01:26:02
zumindest was die asymptotische Komplexität angeht. Das ist nochmal dieselbe Idee, die wir jetzt eben hatten in Code gegossen, dass wir eben eine Liste von Knoten und nicht eine Liste von Kanten haben. Für jeden Knoten eine Liste von Kanten, die rausgehen aus diesem Knoten und diese Bedingung verletzen.
01:26:24
Aber wir sind immer noch weit weg von dem, was wir uns eigentlich erhoffen und erträumen würden von Laufzeiten her. Also wir müssen uns da ein bisschen anstrengen. Das wird heute natürlich nicht mehr allzu viel gehen.
01:26:43
Erste offensichtliche einfache Verbesserung ist die, dass wir die Kanten,
01:27:01
eine ganz primitive Verbesserung ist, die man wahrscheinlich schon implementiert ohne daran zu denken, ist, dass wir die Kanten in einer festen, beliebigen aber festen Ordnung speichern. Und in dieser Ordnung sozusagen in Runden durchlaufen, eine Runde ist einmal durchlaufen, alle Kanten in dieser Liste.
01:27:22
Und für jede Kante, die diese Eigenschaft hat, die noch die Optimalitätsbedingung verletzt, machen wir den Korrekturschritt, dass wir den Distanzwert des Siegnotens runtersetzen auf Distanzwert des Startnotens plus Länge der Kante.
01:27:42
Und die Behauptung ist, wenn wir das so machen, nach der Karten iteration, nach dem Kartenpass durch die ganze Liste, dann ist das Ergebnis, was jetzt momentan in den Distanzwerten steht, ein kürzester
01:28:02
Weg, ein kürzester Pfad vom Startnoten zu jedem anderen Knoten mit höchstens K-Kanten. Ich glaube nicht, dass das Lämmer exakt stimmt. Das werde ich beim nächsten Mal erklären, warum ich das nicht glaube.
01:28:23
Darauf bin ich gekommen, als ich in der GDE 2 Bellman Ford, worauf das hinauslaufen wird, erklärt habe und jemand entweder schon im Zwischenruf oder später dann zu mir gekommen ist und gesagt hat, da ist irgendwas nicht ganz kosher. Das werde ich dann beim nächsten Mal hier erklären.
01:28:41
Was ich meine ist, 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 mehr als K-Kanten enthalten, aber es ist auf keinen Fall länger als ein kürzester Weg mit K oder weniger Kanten.
01:29:06
Lassen Sie das mal kurz absacken, also nicht sich absacken, sondern das, was ich eben gesagt habe, absacken. Vielleicht nur Ankündigung, die ersten fünf Vorträge hier sind jetzt gerendert und sind ans ELC gegeben, dass die das dort einhängen.
01:29:25
Ich warte jetzt nur, dass ich die URL mal bekomme, wo die eingehängt sind, dass ich das an sie weiterleiten kann. So, wir haben pünktlich angefangen. Sie sehen, ich bin langsam routiniert mit dem Aufbau und wir können deshalb auch pünktlich aufhören. Ich danke Ihnen für dieses Mal.