Shortest Paths III / Network Flows
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 | 8 | |
| 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/21472 (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
Element (mathematics)LengthKanteMoment (mathematics)Desire pathIterationVertex (graph theory)EmbeddingMathematicsInvariant (mathematics)OptimalitätsbedingungTrailOptimumMathematisches ZeichenShortest path problemDirected graphComputer animation
08:37
Connected spaceDirected graphDistanceIterationShortest path problemOptimumKanteLengthZahlMoment (mathematics)SupremumScalar potentialInequality (mathematics)OptimalitätsbedingungDesire pathKantenmengeComputer animation
17:02
Directed graphDistanceMathematicsNegative numberLengthQuoteLengthMatrix (mathematics)Vertex (graph theory)OptimumTrailSummationKanteStress (mechanics)TheoryLogical constantOrder of magnitudeCompass (drafting)IterationInvariant (mathematics)OptimalitätsbedingungComputer animation
25:28
IterationPartition (number theory)Military operationKanteQuoteContent (media)Computer animation
28:39
Ideal (ethics)Algebraic structureElement (mathematics)Exponential functionNegative numberGraph (mathematics)Directed graphAbsolute valueInvariant (mathematics)Moment (mathematics)SummationStress (mechanics)Total S.A.Content (media)Absolute valueReduction of orderLengthOptimumCompass (drafting)Chain complexEnde <Graphentheorie>OptimalitätsbedingungNegative numberKanteComputer animation
38:00
Negative numberKeilförmige AnordnungSign (mathematics)Directed graphLengthBellman equationINTEGRALOperations researchOptimalitätsbedingungLengthKanteChain complexNumberTrailNummerierungInvariant (mathematics)IterationMatrix (mathematics)LaufzeitIndexSummationDiagonalNegative numberSupremumInequality (mathematics)Stress (mechanics)RandOptimumSquareEquationComputer animation
47:22
Operations researchINTEGRALTerm (mathematics)Vertex (graph theory)SubsetMatrix (mathematics)Negative numberDiagonalGroup actionKeilförmige AnordnungWeightSign (mathematics)LengthTransformation (genetics)Algebraic closureDesire pathShortest path problemSet (mathematics)IterationNegative numberLengthState of matterList of anatomical isthmiKanteMatrix (mathematics)SquareZusammenhang <Mathematik>Stress (mechanics)SummationInvariant (mathematics)NumberComputer animation
56:44
Keilförmige AnordnungWeightSign (mathematics)LengthTransformation (genetics)Universe (mathematics)Binary fileSummationKanteLengthDesire pathChain complexZahlOptimumProfessional network serviceEquationState of matterSet (mathematics)List of anatomical isthmiPhysical quantityComputer animation
01:06:05
Graph (mathematics)Model theoryMass flow rateKanteNetzwerkflussMaxima and minimaSpring (hydrology)ParallelenMaß <Mathematik>FluxUntere SchrankeQuoteSupremumBoom barrierComputer animation
01:13:14
Constraint (mathematics)Matrix (mathematics)Compact spaceVector graphicsDynamic rangeKanteMatrix (mathematics)RandPolymorphism (materials science)Product (category theory)EquationConnected spaceIncidence algebraEuclidean vectorVertex (graph theory)Nichtlineares GleichungssystemNumber theoryMultiplicationMathematicsMatrix (mathematics)SummationMaß <Mathematik>SupremumZahlAdditionFluxComputer animation
01:20:11
Constraint (mathematics)Matrix (mathematics)Feasibility studyCompact spaceInfinityAutomatonBoom barrierRoundingZahlOrder of magnitudeCompass (drafting)SummationKapazität <Mathematik>Maß <Mathematik>SurfaceEquationStrömungNumber theoryUntere SchrankeRound-off errorFactorizationComputer animation
01:27:09
Graph (mathematics)
Transcript: German(auto-generated)
00:01
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, hier waren wir beim letzten Mal stehen geblieben, wir sind immer noch beim Thema, was sie ja schon aus der GDI 2 alles im Prinzip kennen,
00:21
kürzeste Wege, was wir noch mal ein bisschen in mehr in einen etwas allgemeineren Blickwinkel einbetten. Sie kennen Algorithmen wie Dijkstra, das hatten wir beim letzten mal auch noch mal wiederholt. Wir werden heute noch mal kurz auf Bellman-Ford und Floyd Warshall zu sprechen kommen, jetzt eingebettet in die Theorie, die wir im letzten Mal entwickelt haben und dann
00:43
werden wir hoffentlich endlich die Themen verlassen, kürzeste Wege und ähnliches und uns zu weiterführenden Themen dann hin bewegen. So, hier sehen Sie noch mal den allgemeinen Algorithmus. Sie erinnern sich,
01:01
Dijkstra hat in jeder Iteration ein Distanzwert endgültig gesetzt und der Korrektheitsbeweis bedeutet im Prinzip zu beweisen, dass der Wert, den diese Distanzvariabel für diesen einen Knoten hat, tatsächlich der reale Distanzwert dieses Knotens ist, also die Länge eines kürzesten Fahrtes
01:22
vom Startknoten zu diesem Knoten. Wir haben aber ein anderes Konzept kennengelernt, das haben Sie auch schon in der GDI 2 kennengelernt, Bellman-Ford, Floyd Warshall, wo erst ganz zum Schluss nach der allerletzten Iteration sämtliche Distanzwerte endgültig fest sind in jeder einzelnen Zwischen iteration, in jedem einzelnen Schritt des
01:44
Algorithmus. Hinterher haben wir immer noch ein Zwischenergebnis, was zufällig bei einzelnen Knoten das korrekte Endergebnis ist und dann auch nicht mehr geändert wird, aber im Allgemeinen ist kein einziger dieser Distanzwerte von allen Knoten tatsächlich schon der korrekte bis zum
02:02
allerletzten Schluss. So, hier ist noch mal der allgemeine Algorithmus, der ist das allgemeine algorithmische Schema, wie man, wir sind wieder bei der Situation, gegeben ist ein gerichteter Graf mit Kantenlängen, Startknoten S und wir wollen die Distanzen zu allen anderen Knoten haben. Sie kennen das ja schon, es ist immer
02:23
dasselbe Bild, wir haben den Distanzwert von S gleich Null, da können wir nichts falsch machen, wenn wir den auf Null setzen, ja da brauchen wir nicht groß nachzudenken und alle anderen Distanzwerte setzen wir auf plus unendlich, weil wir immer haben wollen, dass der Wert, der da steht in
02:41
einem für einen Knoten V, der Wert dV für einen Knoten V ist entweder plus unendlich oder die Länge irgendeines Fades von S nach V. Natürlich mit der Zielsetzung, dass es am Ende die Länge eines kürzesten Fades ist, zwischendurch ist es immer die Länge irgendeines Fades oder eben solange
03:02
dieser Knoten noch nicht berührt worden ist unendlich, so dass wir keinen Fehler machen, wenn wir den Distanzwert auch immer wieder nur reduzieren, ja wir haben eine neue Möglichkeit entdeckt zu diesem Knoten über eine andere Kante, haben den Distanzwert zum Startknoten dieser Kante,
03:22
Sie erinnern sich, hier ist der Startknoten insgesamt, wir haben hier eine Kante, die zu diesem Knoten V reinführt, gucken jetzt von einem Knoten U dahin, wir haben einen U Wert, wir haben ein D Wert für diesen Knoten U
03:43
und wenn in dem Moment gerade der Distanzwert von V größer als der Distanzwert von U plus der Länge von U nach V ist, hier ist es mit C abgekürzt nicht mit L, ich sollte da konsistent bleiben, so wenn das der Fall ist, das
04:03
ist die, rechts ist die Länge eines gewissen Weges von S nach V, nämlich das Weges für den D U steht von S nach U plus der Kante von U nach V, links ist die Länge irgendeines Weges oder ist unendlich, wenn V noch nie angefasst worden ist und wir können nichts falsch machen, wenn wir sagen, also die
04:26
Invariante ist D von V ist die Länge eines irgendeines Weges von S nach V, wir können nichts falsch machen, wenn wir jetzt setzen D von V, also ich finde hier mathematische Notation, Doppelpunkt gleich, das was hier rechts
04:42
steht, die Länge dieses Weges, ja das ist das Grundprinzip, ist genauso eigentlich auch in Dijkstra das Grundprinzip, es ist immer wieder dasselbe eine Baustein, wie man den Distanzwert korrigiert und dabei auf der sicheren Seite ist, so was machen wir
05:03
jetzt hier, ja, also es kann sein, dass da irgendwas nicht aufgenommen wird, das kann sein, ich habe aber keine Ahnung, wie ich das jetzt korrigieren kann, müssen
05:21
wir dann sehen, dann müssen sie das halt mit dem Folienausdruck irgendwie vergleichen, weil sie jetzt auch nicht wie das kommt, gut wir können überrascht sein, es ist, also sie sehen, man kann auch noch so oft damit arbeiten, das ist immer wieder für Überraschung gut, so, wir setzen die reingehende Kante jedes Knotens wie immer auf null am Anfang, weil wir eben
05:45
jedes Knoten der Distanz unendlich hat, weil wir eben noch keinen einzigen Pfad haben, bei dem wir hier sitzen, so hier wäre es etwa so in dem Moment, wenn wir das setzen, würden wir auch zugleich noch Pi von
06:01
die Kante von U nach V setzen, als die aktuelle letzte Kante eines Pfades oder andersrum gesagt, als die letzte Kante des aktuellen Pfades von S nach V, so und dann gehen wir einfach durch, wir erhalten eine Liste von Knoten, die
06:25
momentan Kandidaten sind, nehmen uns immer in jedem Schritt einen Element raus, gucken uns die einzelnen Kanten an, die aus dem rausführen und führen jetzt diesen Schritt aus, den ich an der Tafel hatte, korrigieren gegebenenfalls,
06:42
wenn die Distanzwerte so sind, wie sie hier an der Tafel gerade stehen in der ersten Zeile, dann wird eben diese Setzung da unten gemacht, so und dann gucken wir uns noch an, wenn hier wirklich was passiert ist mit dieser Kante, wenn dieser Distanzwert tatsächlich durch diesen Correct Schritt verändert worden ist und das gerade jetzt dieser Knoten nicht in der
07:03
Liste ist, dann fügen wir in die Liste ein, weil wenn sie, wenn sie diesen Knoten V jetzt so behandeln von U ausgehend, dass sie die Distanz hier
07:28
verändern, dass sie die Distanz von V, den Distanzwert von V verändern, es kann durchaus sein, dass bis dahin, bis zu diesem Moment hier, dass alles
07:44
gestimmt hat, diese Distanzwerte hier gestimmt haben, durch das V nicht beeinflusst worden sind oder über das V gehen und in dem Moment, wenn sie Distanzwert hier verändern, dann kann es sein, dass über diese Kanten die Optimalitätsbedingungen nicht mehr erfüllt ist, dann müssen die also wieder rein, die rein heißt, den Knoten V rein, diese Kanten reinzubringen,
08:06
heißt den Knoten V reinzubringen, deshalb ist es eine Knotenliste, keine Kantenliste, dass wir jeden Knoten dann jeweils nochmal, weil wir sowieso alle rausgehenden Kanten eines Knoten dann betrachten müssen, noch mal irgendwann, muss nicht gleich sein, irgendwann vielleicht später, fügen
08:21
den zur Liste an und machen so lange, bis die Liste leer ist, wir fügen ja immer nur ein Element in die Liste ein, nur ein Knoten in die Liste ein, wenn potenziell von diesem Knoten ausgehend die Optimalitätsbedingungen auf mindestens einer Kante verletzt sein könnte, wenn die Liste leer ist,
08:45
dann haben wir keinen einzigen Knoten mehr, bei dessen rausgehenden Kanten die Optimalitätsbedingungen verletzt sein könnte und dann sind wir fertig, denn wir haben beim letzten Mal gesehen, wenn die Optimalitätsbedingung für alle Kanten erfüllt ist, nämlich gerade das,
09:00
was hier zur Veränderung geführt hat, die Optimalitätsbedingung ist gerade die Bedingung für jede Kante uv, dass d von v kleiner gleich d von u plus Länge von u nach v ist, wenn das für alle Kanten
09:22
gilt, genau dann sind die Distanzwerte allesamt korrekt, hatten wir beim letzten Mal bewiesen und diese Tatsache, dass das genau dann, wenn diese Ungleichung für jede Kante gilt, dass genau dann alle Distanzwerte korrekt sind, das ist die Rechtfertigung für diesen
09:41
Korrektschritt in jeder Iteration, dass wir genau dann, wenn es irgendwo verletzt ist, auf einer Kante dafür sorgen, dass es dann wieder erfüllt ist mit Gleichheit und rechtfertigen dafür in dem Moment, wenn wir keine Kandidaten mehr haben, wo diese Optimalitätsbedingung verletzt sein könnte, dass wir dann die Schleife beenden.
10:08
So, FIFO, zum Beispiel, wir haben nicht gesagt, wie die Liste aussehen sollte, zum Beispiel kann das eine FIFO-Q sein, Sie wissen, was eine FIFO-Q ist, vorne holt man raus, hinten steckt man rein, wir gehen durch die Kanten durch
10:31
und jede Kante, jede einzelne Kante prüfen wir auf die Art und Weise. Also wir machen jetzt hier in dieser Reihenfolge, wenn das eine FIFO-Q ist,
10:43
dann läuft das darauf hinaus, dass wir immer wieder durch alle Kanten, die noch potenziell in Frage kommen, also nicht mehr unbedingt durch alle Kanten, aber alle Kanten, die noch vielleicht die Optimalitätsbedingung aktuell verletzen könnten, gehen wir immer durch.
11:04
Also es ist weiterhin eine Knoten-Q, eine Q von Knoten, aber für jeden Knoten gucken wir uns ja alle Kanten an, immer am besten in derselben Reihenfolge und gehen auf die Art und Weise immer durch alle potenziellen Kanten in der
11:21
selben Reihenfolge durch. So, und das ist nicht überraschend, FIFO hat sehr viel mit Breitensuche zu tun, nach jedem, nach dem Karten-Durchlauf, also nachdem wir Kamal durch die ganze Kantenmenge durchgekommen sind, ist
11:42
etwas, ich glaube nicht, dass das, hatte ich letzt mal gesagt, ich glaube nicht, dass diese Aussage wirklich genau korrekt ist, aber sie ist, die echte Aussage ist sogar noch ein klein wenig, wie soll ich sagen, besser, zumindest komplizierter, aber hat dieselbe Garantie. So, was steht erstmal hier als
12:04
Aussage? Nach K durchläufen steht in jedem Distanzwert die Länge eines kürzesten Fades, der höchstens K-Kanten hat. Das kennen Sie von, das ist nichts
12:23
anderes als der Bellman-Ford-Algorithmus, was Sie hier sehen, jetzt nicht als All-Pairs-Version, sondern als Version von einem Knoten zu allen anderen. Warum? Schauen Sie, wir sind hier in dieser
12:45
Situation im Kartenschritt. So, nach Induktionsvoraussetzung ist das hier die
13:07
Länge eines kürzesten Weges, diese Distanz hier, oder das hier, was ich angedeutet habe, ist ein kürzester Weg mit maximal K-1-Kanten von S nach U. Und das hier ist auch die Länge eines kürzesten Weges mit maximal K-1-Kanten
13:24
von S nach U. Unter allen Wegen, die höchstens K-1-Kanten haben, ist das bzw. das jeweils ein kürzester Weg. Und diese Kantenzahl, die die obere Schranke ist, für die Länge im Sinne von Anzahl Kanten, die wächst von Iteration zu Iteration und nach N-1-Schritten haben
13:44
sie alle Pfade drin. Kein Pfad kann mehr als N-1-Kanten enthalten, unmöglich. Nach N-1-Schritten sind sie garantiert mit dem Algorithmus durch. So, wenn das hier der kürzeste Weg, wenn sie hier diese
14:02
Update machen, oder andersrum, es gibt zwei Möglichkeiten. Entweder sie machen diesen Update nicht, dann bleibt es bei dieser Länge, dann bleibt es hinterher, dass sich nichts ändert. Das ist weiterhin die Länge für V, die Länge eines kürzesten Weges mit maximal K-1-Kanten. Das ist
14:24
natürlich auch ein kürzester Weg mit maximal K-Kanten dann. So, wenn sich aber hier was ändert, weil wir nur eine Kante hinzufügen, kommen wir von K-1 nach K. Das heißt, wenn wir tatsächlich ein oder vielleicht sogar mehrere Update-Schritte machen mit verschiedenen Kanten, das kann ja sein, dass wir nicht nur
14:43
einmal diesen Update-Schritt machen in diesem Kartenpass, sondern mehrfach mit verschiedenen Kanten. Aber wie man es auch dreht und wendet, der Distanzwert der Startnoten dieser allen Kanten, war immer die Länge eines kürzesten Weges mit maximal K-1-Kanten. Eine Kante dazu ist jetzt die Länge eines kürzesten Weges mit maximal K-Kanten. So, warum
15:03
bin ich mir nicht sicher, dass die Aussage so jetzt kompliziert genug ist, weil ich, oder ist es das doch? Genau, was noch, was passieren kann in so einem Pass ist zufälligerweise meines Erachtens, wir können es ja gerne mal
15:31
kurz diskutieren, dann können Sie mir wieder vielleicht sagen, dass das, was ich mir überlegt habe, falsch ist, dass es doch so ist, wie es richtig ist. Dann frage ich wieder, ob nicht jemand anders die Vorlesung übernehmen will
15:42
und dann kriege ich wieder dieselbe Antwort, weil ich derjenige bin, der bezahlt wird. Das wird so langsam zum Running Gag. Die Bezahlung könnte man vielleicht auch als Running Gag bezeichnen.
16:02
So, es kann ja zufällig sein, wenn wir so ein Pass durchmachen, dass wir vielleicht jetzt eine Kante erwischen und zufällig ist später dann die später, ist die hier später, ist die hier später, ist die hier später, ist die
16:23
hier später zu irgendeinem Knoten V. Nehmen Sie an, wir sind in dem allerersten Pass. Da war ursprünglich hier noch alles unendlich und zufällig ist, dass die erste Kante, die angefasst wurde, da wurde dieser Wert entsprechend runtergesetzt, dann im selben Pass diese Kante als zweites
16:41
zufällig, die als drittes, viertes, fünftes, sechstes. Das heißt also, wir haben tatsächlich einen Wert hier als Distanzwert von V, der garantiert nicht größer ist als die Länge eines kürzesten Fahrtes mit maximal einer
17:01
Kante, aber potenziell sogar kleiner ist als das, was hier in dem steht. Es ist die Länge eines kürzesten Weges, wir könnten ja vielleicht das Beispiel noch fortführen, wir könnten zum Beispiel sagen, es gibt tatsächlich noch eine Kante hier, dann wäre diese eine Kante, dann wäre die
17:24
Länge dieser Kante die Länge eines kürzesten Weges mit maximal einer Kante. Logisch, es gibt ja nur diesen einen Weg, aber es kann doch durchaus sein, dass in einem Pass das hier alles in nacheinander gemacht wird und wenn die Länge dieses Weges kleiner ist als die Länge dieser Kante,
17:44
dann würde diese Länge dieses Weges herauskommen, das ist aber nicht die Länge eines kürzesten Weges mit maximal einer Kante, sondern möglicherweise etwas Kürzeres. Deshalb ist der Gedanke dann irgendwie klar geworden, deshalb bin ich der Meinung, dass das Theorem etwas zu
18:01
kompliziert formuliert wurde, dass da noch eine kleine Komplikation drin ist. Er würde den finden, aber es könnte ja sein, dass diese, das ist richtig, der Algorithmus würde diesen einen Schritt finden, aber es könnte ja sein, dass diese Kante länger ist als dieser ganze Weg hier unten, ja. Also wir
18:37
haben doch hier A, B, C, D, E und V, nenne ich die jetzt mal, ja. Wir setzen
18:43
zufällig in der folgenden Reihenfolge, darf ich das kurz sagen, D von A gesetzt, D von S plus Länge SA, in dieser Reihenfolge D von B gesetzt, D von A plus Länge AB und so weiter bis am Ende D von V gesetzt, D von E plus
19:14
Länge EV, ja. Und wenn das kürzer ist hier, vielleicht haben wir den vorher gefunden oder vielleicht auch hinterher, ist eigentlich egal, aber wenn diese
19:23
gesamte Länge hier unten, die Summe der einzelnen Kantenlängen, kürzer ist als die die Länge dieser Kante, ja, die haben alle Länge eins und der hat ja eine Million der pro Ohre, dann würde ja nicht eine Million rauskommen, nicht, zufälligerweise, sondern es würde diese 1, 2, 3, 4, 5, 6, die
19:42
als Distanzwert rauskommen. Das heißt also, das ist der Grund, warum ich der Meinung bin, dass das Lämmer noch unterkomplex ist. Es müsste noch etwas genau formuliert werden, dass der tatsächliche Distanzwert, der dran und drin steht, nicht größer ist, sondern höchstens kleiner oder gleich ist
20:03
zur Länge eines kürzesten Weges von K oder weniger Kanten. Of K of also in der ersten iteration von höchstens einer Kante. Die Länge eines
20:22
kürzesten Wegs von höchstens einer Kante. Das wäre in unserem Beispiel dann korrekt im Lämmer, wenn da eine Million rauskäme, wenn die oberen Kanten eine Million Länge hat. Warum? Nicht? Also das Lämmer sagt was, nicht der
20:44
Algorithmus. Er sagt nach einem, ich setze für K gleich 1 ein und er sagt nach einem Schritt hat er die Länge eines kürzesten Weges mit höchstens
21:03
einer Kante gefunden. Das heißt also damit, mit dieser Formulierung ist dieses Beispiel, was ich mir da überlegt habe, ausgeschlossen.
21:21
Okay, dank dieser Formulierung, ich glaube das ist wahrscheinlich nicht mal absichtlich gewesen, man hatte nur diesen Fall unendlich ausschließen wollen mit dieser Formulierung, aber sie haben dank dieser Formulierung ist mein Beispiel auch ausgeschlossen. Gut, wieder was dazu gelernt. Wäre eine interessante Diskussion zur Prüfung. Ist ja alles
21:44
aufgenommen. So Inuktion, Anzahl der Schritte, das habe ich eben angedeutet, wie diese Inuktion ausgeht, wie viele Schritte sind notwendig, da jeder Pfad höchstens n-1 Kanten haben kann, also jeder Pfad, der keine Züge enthält, sind wir nach n-1 durchläufend durch und für jede Kante kostet das
22:07
eine Operation, eine konstante Operation. Wir kriegen n Durchläufe Größenordnung und m Kanten in jedem Durchlauf, das ergibt dann n mal m. So
22:24
das kann man noch ein bisschen besser machen, die Kanten in der Kantenliste. Ach so, warum beschäftigt man sich damit? Ein Grund warum man sich damit beschäftigt, jetzt ich meine die Frage ist warum beschäftigt man sich, wenn es doch der Algorithm von Dijkstra gibt. Ein Grund warum man sich damit beschäftigt
22:41
oder der Grund ist, dass der Algorithm von Dijkstra nicht mit negativen Kanten umgehen kann. Hier klappt das. So, wenn wir das ganze noch ein bisschen anders ordnen, was wir eigentlich ursprünglich gemacht haben, als wir
23:01
Knotenlisten hatten, dann können wir wieder zurückgehen zu ersten Implementation und Knoten statt Kanten speichern und kriegt dasselbe dann dann wieder raus. Ist alles also nicht so so viel anders. Es bleibt dabei n mal m ist
23:23
der Aufwand und das ist das beste was man weiß bis momentan. Wenn negative Kantenligen erlaubt sind aber noch keine negativen Züge. Wir werden noch negative Züge noch mal zu besprechen haben. So was wir da haben ist Bellman-Ford. Sie haben Bellman-Ford und in weiß ich nicht in der
23:42
GD2 entweder kennengelernt wie hier als ein Algorithmus für kürzeste Wege von einem Knoten zu allen anderen oder zum Beispiel bei mir kennengelernt für all pairs. Also alle wir wollen eine Matrix haben von jedem Knoten zu jedem Knoten den Distanzwert. Beide Problemstellungen
24:03
beider Problemvarianten kennen sie ja aus der GD2. Ich weiß nicht was sie da jetzt jeweils kennengelernt haben. Woran ich das aufgezogen habe als all pairs, was letztendlich ja das gleiche ist, nur dass man eben nicht von einem Knoten ausgeht, sondern sie wissen das von man hat
24:22
eine Matrix und da werden die Werte abgedatet. Aber hier gilt es auch. Das ist das was was hier so ein bisschen im Beweis drin steckt. Die Invariante ist, was jetzt dieses Lämmer war das wir so diskutiert haben, nach so zu vielen Schritten, nach K-Schritten ist das die Länge eines kürzesten
24:41
Weges mit maximal K-Kanten. So wir gehen das Beispiel jetzt hier nicht weiter durch. Das können sie verwenden um sich das noch mal klar zu machen. Gut, was sagt das hier? Diese No Distance Labels in P-Points might be
25:02
incompatible until termination. Warum? Es wird doch immer, ach so incompatible kann ja das bedeutet jetzt nicht, das habe ich mich jetzt verlesen, das bedeutet jetzt nicht, dass zu einem Knoten der Distanz Label dieses Knotens und der und der P-Point da miteinander incompatibel sind, sondern das bedeutet
25:21
das für verschiedene Knoten die Distanz Label, dass eben die Optimalitätsbedingungen bis zum Ende für kein einzige Kante erfüllt sein muss. So hier das hat mich in der Vorbereitung einiges an Zeit gekostet bis ich dann endlich vom Herrn Stille den Forumseintrag dazu gelesen habe,
25:42
der die Sache dann klar gemacht hat. Was hier passiert ist folgendes, wir die N-Variante, das ist nun eine heuristische Beschleunigungstechnik, das bedeutet nicht die asymptotische Komplexität wird besser dadurch, es
26:00
bleibt bei dem N mal N, aber potenziell in der Praxis die wirkliche Anzahl der Schritte, die notwendig sind, kann damit drastisch reduziert werden. Es geht um die Problematik,
26:29
das ist jetzt hier die Variation, jetzt muss ich noch mal ganz genau nachdenken, es geht um die Problematik, oder machen wir mal umgekehrt, wir haben
26:51
sämtliche Knoten nummeriert und diese N-Variante sagt, mal gucken welche
27:00
Reihenfolge, zuerst so herum und zuerst dann da rum, jede Kante geht natürlich entweder so herum, nach rechts, wenn wir die Knoten so in irgendeine Reihenfolge gebracht haben, oder sie geht nach links und die Aussage ist, dass die Updateschritte immer zuerst von rechts nach links
27:22
gemacht werden und danach alle von rechts nach links und danach alle Updateschritte von links nach rechts in einem Pass. So jetzt muss ich mir noch mal vergegenwärtigen, was jetzt der der genaue Vorteil von dieser Variante war, aber ich glaube da muss ich noch mal nachschlagen,
27:51
die Vorbereitung ist jetzt leider ein Schritt etwas zu lang, muss ich noch mal nachschlagen, trage ich dann beim nächsten Mal nach, sorry, aber
28:04
das was jetzt hier steht, das ist falsch, das hat mich wie gesagt eine ganze Weile gekostet, ich habe erstmal im Internet rumrecherchiert, Variante, habe nirgendwo dieses ein halbe gefunden, habe ich dann zufällig
28:22
per Google auf diesen besagten Forumseintrag gestoßen, wo Herr Stille der der Autor dieser Folie dann gemeint hat, ja wahrscheinlich stimmt das nicht, muss ich halt korrigieren, scheint nicht gemacht worden zu sein. Gut, zweite Variante ist folgende, wir hatten es zuerst mit
28:48
einer FIFO-Q, also vorne rausnehmen Knoten, hinten rein tun, was wir hier machen ist eine etwas andere Regel, das steht hier, wenn ein Knoten schon mal da war in der Liste, wenn er schon mal in der Liste war, dann wird er
29:05
wieder vorne aufgehängt, angehängt, ansonsten wird er hinten angehängt. Der Gedanke dahinter ist, jetzt stimmt dieses Bild da wieder, wenn
29:37
ich diesen Knoten hier rausgenommen habe und hier update, dann packe ich
29:43
diesen Knoten wieder an den Anfang, dass er möglichst bald wieder benutzt wird. Warum? Stellen Sie folgende Situation her, wir nehmen diesen Knoten hier, korrigieren darauf hin diese ganzen Knoten-Distanzen, weil wir
30:02
diesen Knoten betrachtet haben, von hier aus korrigieren wir die alle, jetzt korrigieren wir die weiter, weil sie vielleicht als nächstes kommen, so wie bisher, werden die als nächstes gekommen, jetzt kommen wir in dem nächsten Pass wieder hier hin, dass wir den runter korrigieren und müssen wieder die alle runter korrigieren. Der Gedanke ist der, heuristischer Gedanke,
30:25
also es lässt sich nicht in eine verbesserte asymptotische Komplexität umwinzen, der Gedanke ist der, wenn wir diesen Knoten gleich wieder behandeln, dann ist die Wahrscheinlichkeit sehr groß, dass es mehrere Reduktionen hier gibt und erst später, weil diese Knoten weiter hinten in der Q sind, erst später müssen einmal diese Knoten
30:47
reduziert werden und nicht jedes mal, wenn dieser Knoten reduziert wird. Wenn wir einfach immer in derselben Reihenfolge durchgehen, wie bisher vorgeschlagen, ist es immer so, dieser Knoten wird reduziert, potenziell durch irgendwelche Kanten, dann später diese Knoten reduziert, dann wird
31:03
wieder, im nächsten Pass vielleicht dieser Knoten reduziert, dann müssen die wieder reduziert werden und so weiter, aufgrund der reduzierten Distanz hier. Wenn wir das so machen, dass der mit größerer Wahrscheinlichkeit baldmöglichst wieder noch vor denen weiter behandelt wird und genau das sagt diese Regel mit den zwei Enden oder genau das
31:23
versucht diese Regel mit den zwei Enden zu verwirklichen, dann ist die Wahrscheinlichkeit sehr groß, dass erst mal mehrfach dieser Knoten hier weiterhin reduziert wird, bis die einmal dann reduziert werden müssen. Das ist der Hintergedanke hinter dieser heuristischen Beschleunigungstechnik. Das was hier Intuitive Justification dann genannt wird. Wir haben also eine
31:48
Deque oder Deck, spricht man es häufig heraus, eine Que wo man von beiden Seiten, also in diesem Fall von zwei Seiten einfügen und von einer Seite löschen, aber allgemein spricht man von einer Deck oder Deque, wenn
32:02
man von beiden Seiten einfügen und löschen kann. So wenn man das so macht, auf diese Art und Weise hat man zwar in der Praxis eine Verbesserung, aber in der Theorie sogar eine Verschlimmbesserung. Nämlich, das will
32:23
ich jetzt hier nicht ausführen, wenn sie nicht stur von vorne nach hinten durchgehen wie bei FIFU, sondern irgendwie auf unkontrollierte Art und Weise vorne hinten vorne hinten einfügen.
32:40
Wenn das so völlig unkontrolliert ist, sie können nicht vorhersehen in welcher was da passiert. Sie könnten es natürlich, wenn sie das haben, schrittweise nachrechnen was da passiert, aber es ist undurchschaubar was da passiert und da kann es dann durchaus sein, dass sich dieses Prinzip gegen sie kehrt, wenn sie ein dummes Beispiel haben
33:01
und das dann viel viel mehr Anschritten zu tun ist als mit den Algorithmen, die wir bisher betrachtet haben. Ein Beispiel, das es öfters mal gibt in der Algorithmik, praktisch besser als die Standardvariante, aber theoretisch schlechter. Ja, in Ihrem Kopf, warte drauf zu Papier
33:25
gebracht zu werden. Wenn Sie das Beispiel mitnehmen in die Prüfung und wir reden dann darüber, soll es nicht zu Ihrem Schaden sein, wenn das Gespräch von Ihrer Seite aus konstruktiv dann ist. Suchen Sie einfach in Google nach dieser Variante, da wird
33:44
bestimmt irgendwo leicht ein Beispiel zu finden sein. Ich glaube auch nicht, dass es schwer ist, das zu konstruieren, aber ich kann es jetzt nicht sofort aus dem Ärmel schütteln. Negative Zykel, das hatten wir schon mal. Das können wir ganz kurz durchgehen, das hatten wir vor
34:03
letzten Termin vielleicht oder spätestens letzten Termin. Wenn wir einen negativen Zykel haben, wenn es mindestens einen negativen Zykel gibt im Grafen, also ein Zykel auf dem die Summe der Kantenlängen
34:22
insgesamt negativ wird, dann bedeutet das, das hatten wir schon mal, will ich jetzt nur wiederholen, will ich nicht noch mal näher drauf eingehen, dann bedeutet das, dass auf irgendeinem Zykel diese Vorgängerkanten tatsächlich zykeln, weil das ist kleiner als das, das ist kleiner als das, die Sistanz ist
34:44
kürzer als die, die Sistanz kürzer als die und so weiter und so fort. Können Sie noch mal in den Aufnahmen dann, sofern diese Aufnahmen dann endlich mal online gestellt werden, können Sie dann, ich glaube vor letzten Termin noch mal nachschlagen, was wir da gesagt hatten. So, das können wir
35:03
natürlich in linearer Zeit in der Anzahl der Knoten checken, ob es so was gibt. Ja, wir nehmen uns für jeden einzelnen Knoten diese Vorgängerpointer her, das heißt, dass er für jeden Knoten nur eine
35:25
einzige Vorgängerkante gibt, haben wir eine O von N viele Kanten in diesem Grafen, er ist sehr dünn besetzt und da können Sie natürlich mit Tiefensuche, das haben wir schon mal ganz am Anfang besprochen, können Sie mit Tiefensuche sehr schnell herausfinden, dass Sie da einen Zykel drin haben.
35:41
Also sehr schnell heißt wirklich in linearer Zeit. Wenn wir das nicht immer machen, sondern hin und wieder mal nach so und so vielen Schritten, vielleicht nach N vielen Schritten oder nach N halbe vielen Schritten oder N viertel Schritten oder zwei N vielen Schritten, egal, dann bleibt es in derselben
36:04
Komplexität natürlich drin. Die asymptotische Komplexität bleibt dieselbe, wenn wir das nicht nach jedem Update Schritt machen, sondern nur alle so und so viel N male. Oder alternativ, wir brauchen gar nichts, uns hier einen abzufrickeln mit diesen Pointeren, wir können auch
36:24
unter Umstellen, wir können auch stoppen, wenn C die längste Kantenlänge ist, der absolute value, der Betrag, der längste Betrag einer
36:40
Kantenlänge ist und wenn dieser Wert kleiner ist als, wenn ein Distanzwert kleiner ist als N mal diese Länge, dann wissen wir diese Länge, dieser Wert, dieser Distanzwert muss von einem negativen Zykel gekommen sein. Irgendwann passiert das ja, weil solange, wenn es
37:04
ein negativer Zykel ist, dann bricht der Algorithmus erst mal nicht von sich selber ab, durch sich selbst ab, weil die Optimalitätsbedingungen nicht hinzukriegen sind. Also die Abbruchbedingungen für den Algorithmus greift nie und das heißt, er sucht sich immer wieder entlang der negativen Zykel, wird immer kleinere, immer
37:26
im negativen und endlichen Ost aufhören würde, wären diese Distanzwerte kleiner als dieser Wert, minus N mal C und in dem Moment wissen wir, können wir aufhören, weil dieser Distanzwert minus N mal C garantiert durch einen negativen Zykel nur entstanden sein kann. Okay, die Frage, warum nicht
38:01
N mal C für die kleinsten, Sie haben auf dem Zykel ja negative und positive Kanten. Sie sind auf jeden Fall auf der sicheren Seite, wenn Sie diesen Wert minus N mal C hernehmen. Ja, also sie meinen nur die
38:21
negativen, wenn sie nur die negativen Kanten hier in das C einfließen lassen. Die kleinste Kante ist minus 1, die größte Kante ist 5.000. Ja, also ich
38:56
glaube, das müssen wir noch mal am Rande, das ist jetzt ein bisschen zu kompliziert. Okay, das ist dann der Bellman-Ford-Algorithmus. Im Prinzip
39:06
genau das, was wir bisher gesagt haben und wenn wir N mal durchgelaufen, oder oder das ist noch eine andere Möglichkeit, wie wir die Zykel finden
39:25
können. Das ist noch die Möglichkeit, zumindest diejenigen, die bei mir die zwei gehört haben, wie ich das negative Zykel finden eingeführt habe, noch eine Variante, nämlich sie führen das ganze N minus 1 mal durch. Ja, das heißt also N minus 1 Iteration nach der Karten-Iteration
39:47
ist jeder Distanzwert die Länge eines kürzesten Weges von S zu diesem Knoten mit maximal K-Kanten. Am Ende, wenn alles mit rechten Dingen zugeht, ist das jeweils der kürzeste Weg. Aber wenn Sie noch
40:01
irgendwo eine Verletzung der Optimalitätsbedingungen haben, dann wissen Sie, Sie haben einen negativen Zykel gefunden, weil eine von dieser Kanten, eine Kante auf diesem negativen Zykel, das haben wir schon mal festgestellt, es geht nicht auf, dass die Optimalitätsbedingungen
40:22
auf jeder Kante erfüllt sind, wenn das ein negativer Zykel ist. Sie erinnern sich, wenn das hier zum Beispiel V1 ist, V2, dann ist
40:40
Optimalitätsbedingungen würde heißen dV2 kleiner gleich dV1 plus Länge von V1 nach V2. Diese Gleichung, wenn die Optimalitätsbedingungen erfüllt wären, würde diese Gleichung, diese Ungleichung für jede einzelne Kante gelten. Jetzt stellen Sie sich vor, Sie
41:03
V3 kleiner gleich dV2 plus C, V2, V3 und so weiter, einmal um den Zykel rum, bis auch diese Kante, die wieder zu V1 führt dazu, dann
41:23
haben Sie, wenn Sie die alle addieren, die linken Seiten addieren und die rechten Seiten addieren für alle diese Kanten auf dem Zykel, dann haben Sie links und rechts dasselbe stehen, nämlich die Summe der Distanzwerte aller Knoten. Können Sie wegstreichen, dann steht hinten links noch ein bleibender Null
41:40
übrig und rechts bleibt die Summe der Kantenlängen übrig. Null kleiner gleich Summe der Kantenlängen, das geht bei einem negativen Zykel nicht. Also es ist völlig unmöglich auf einem negativen Zykel, dass alle Kanten die Optimalitätsbedingungen erfüllen. Und deshalb braucht man bloß zu testen, ob noch irgendwo die
42:02
Optimalitätsbedingungen nicht erfüllt ist. Wenn ja, ist ein negativer Zykel gefunden, weil wenn alles mit rechten Dingen zugehen würde, wenn es keine negativen Zykel gäbe, wären wir nach N-1-Iteration fertig. Hätten wir überall die Optimalitätsbedingungen. Wenn es hingegen nicht mit rechten Dingen zugeht, wenn es da
42:20
einen negativen Zykel gibt, dann macht sich mindestens einer dieser negativen Zykel auf diese Art und Weise, auf mindestens einer dieser Kanten bemerkbar. Und damit haben wir zumindest erstmal entdeckt, dass es einen negativen Zykel gibt. Und mit dieser Strategie, die Nachfolger, die die letzten Kanten, den Grafen der letzten Kanten zu durchsuchen nach Zyklen,
42:43
würden wir auch tatsächlich so einen negativen Zykel in die Hand bekommen. So All Pairs können wir relativ schnell durchgehen. Wir könnten zum Beispiel Dijkstra von jedem Startnoten aus loslaufen lassen. Dann hätten wir natürlich auch All Pairs, dann kriegen wir so eine
43:02
komische Substanz, so eine komische asymptotische Komplexität raus. Bellman-Ford können wir All Pairs machen. Das kennen Sie aus der GDE2, denke ich. Da haben Sie jetzt gleich die Matrix. Dann hat man einen Abwasch. Oder man könnte natürlich auch, wir haben jetzt hier Bellman-Ford für einen
43:21
Startnoten eingeführt. Das könnte man natürlich dann auch für jeden einzelnen Startnoten einmal durchführen. Aber für die Laufzeit ist es dasselbe. So, was ist dieser triviale Algorithmus? Gut, dieser triviale Algorithmus ist im
43:44
Grunde, wir initialisieren die Matrix wie immer mit Plus und Endlich für alle Knoten, beziehungsweise Distanz Null für einen Knoten zu sich selber und setzen schon die All Pairs Shortest Paths. Wir haben die Matrix. Sie sehen jetzt
44:02
Distanz von I nach J, nicht mehr Distanz mit nur einem Index von S, vom Startnoten zu jedem anderen Knoten, sondern wir haben hier eine Matrix von Distanzwerten. Wir initialisieren die alle auf der Diagonal mit Null. Jeder
44:20
Knoten hat Distanz Null zu sich selber am Anfang. Wenn es Distanz Null zu sich selbst, wenn es negative Zykel gibt, gibt es mindestens einen Knoten, der Distanz kleiner Null hat am Ende des Algorithmus, also auf der Diagonal in eine negative Zahl und wir initialisieren erst auf der Diagonal, wie gesagt Null, alle Kantenlängen fügen wir
44:42
ein und da wo es keine Kante gibt, mit unendlich und dann machen wir solange die Korrektur bis es keine
45:01
Hier noch nochmal dasselbe immer, wenn wir obere Schranken haben für die, für die, für die Kanten, wenn die obere Schranke hernehmen für die Kantenlänge, also der Maximalwert sämtlicher Kantenlängen, dann kann höchstens N mal C der höchste Wert sein, der überhaupt vorkommen kann, die Länge eines Weges. Ein Weg kann ja
45:23
höchstens N minus eins Kanten haben, kann, jede Kante kann höchstens Länge groß C haben, also ist die Länge eines Weges höchstens N mal C groß oder höchstens minus N mal C klein, dazwischen sind alle Kantenlängen. Das heißt also, wenn die, wenn sämtliche Kantenlängen
45:41
integral sind, dann heißt es, dass mindestens um einen Zähler immer bei jedem Update die Kantenlänge reduziert wird. Sie kann höchstens von plus N mal C in einer Schritten oder in größeren Sprüngen bis minus N mal C reduziert werden und daher kommt es, dass wir höchstens zwei mal N mal C schritten für
46:04
jede einzelne Distanz. Wir haben N-Quadrat-Distanzen, wir können höchstens zwei mal N mal C schritten, haben wir die Distanz von einem zum anderen richtig berechnet. So Floyd Varshall, das will ich, hab ich mir angesehen
46:23
hier, das will ich so einführen, wie ich es auch selber eingeführt habe, nämlich über die Invariante. Ich sag das vielleicht ganz gut oder was wir hier haben bei Floyd Varshall ist eine Numerierung der Knoten von
46:57
V1, V2, ich mach das mal V3, irgendein VK minus eins
47:04
in der Mitte, ein VK, ein VK plus eins in der Mitte, Sie sehen, wir gucken uns wieder mal eine Situation in der Mitte an, irgendwie durchnummeriert. Und die Invariante bei Floyd Varshall ist, dass nach K-Schritten
47:22
jeder Distanzwert die Länge eines kürzesten Fades ist von diesem Startnoten hier, wir sind all pairs, also von irgendeinem beliebigen Startnoten zu irgendeinem Lieblingszielknoten. Erinnern Sie sich, bei Ben Manfort ist die Invariante nach K-Schritten ist es die Länge
47:41
eines kürzesten Weges mit maximal K-Kanten. Das heißt, da wachsen die Pfade schrittweise, sozusagen in der Länge im Sinne von Kantenzahl. Hier ist die Invariante, die nach K-Schritten sind sämtliche inneren Knoten hier, aus der Menge V1 bis VK, also aus diesem Bereich
48:07
hier. Am Ende nach N Iterationen haben Sie natürlich den ganzen Bereich, das heißt, jeder beliebige Fahrt ist möglich und damit haben Sie dann tatsächlich
48:21
wieder die Länge eines beliebigen kürzesten Fades ganz am Ende bekommen. Und diese Formulierung, wie ich jetzt hier als Invariante habe, denke ich, macht sofort klar, wie eine Iteration aussehen muss. Nämlich, für jede
48:40
Sistanz schauen wir uns her, gibt es eine Möglichkeit, das zeichne ich immer vielleicht nochmal neu. So,
49:17
in der Karten Iteration, da haben wir von einem
49:27
irgendwelchen Startknoten hier zu irgendeinem Zirknoten hier, haben wir einen Weg aktuell, dessen innere Knoten alle aus V1 bis VK minus eins sind. Ja, das sagt die
49:44
Invariante. Also, am Anfang der Karten Iteration ist das das Bild. Jetzt haben wir irgendwo außerhalb den Knoten VK. Wir haben einen Weg berechnet hier und
50:04
ein Weg hier, die dieselbe Eigenschaft haben, nämlich alle inneren Knoten aus V1 bis VK minus eins. Ja, das gilt ja schließlich mit diesem Element aus V1 bis VK minus eins, gilt es nicht nur für dieses Paar Startknoten, Zirknoten, sondern für jedes Paar. Also
50:21
auch wenn VK der Zirknoten, wie hier, oder der Startknoten, wie hier ist. So, das heißt also, alles, was wir in dieser Iteration machen müssen für dieses Paar aus Startknoten, Zirknoten ist, wir gucken uns an
50:41
diesen Wert plus diesen Wert. Was gibt das? Und vergleichen das mit diesem Wert. Und wenn das hier diese Summe kleiner ist als dieser Wert, dann daten wir ab entsprechend. Dann wird diese Länge plus diese Länge unsere neue Weglänge geben. Das heißt also, wir prüfen nach, ist ein Pfad, der bringt uns VK etwas? Ja,
51:05
ist ein Pfad, der über VK läuft und wir wissen, welches der beste ist, weil wir ja vorher schon diese beiden Pfade berechnet haben, ist der Pfad, der über VK läuft, besser als der Pfad, der nicht über VK läuft, sondern nur über V1 bis VK minus eins, ohne VK. Wenn ja, wenn er besser ist, dann nehmen wir
51:22
den, wenn nicht, bleiben wir bei dem Alten. Und das Ich denke, das ist recht intuitiv anschaulich, wie das funktioniert. Und Sie sehen wieder, wenn man von der Invariante ausgeht, das versuche ich den Studierenden im in der GDE 2 zu erklären, wenn man von der Invariante ausgeht, wird alles plötzlich, es ist keine Schikane des Dozenten und auch keine keine
51:43
Liebhaberei des Dozenten, die ja unbedingt die Studierenden rein drücken will, sondern es wird plötzlich alles, wenn man von daher ausgeht, sehr viel einfacher und klarer und lässt sich ohne großen Lernaufwand auch gut im Kopf behalten, bilde ich mir ein. Aber wie ich das den
52:03
Studierenden der GDE 2 wirklich verklickern soll, das habe ich noch nicht verstanden. Da bin ich auf Anregungen sehr dankbar. Was kann man tun, damit die Studierenden der GDE 2 nicht nur die kleine Minderheit, die es ganz gut gepackt hat, sondern die große Mehrheit, dass
52:21
sie diesen einfachen Gedanken, mit dem man sicher das Lernen leichter macht und die Note ja nur verbessern kann, diesen einfachen Gedanken dann tatsächlich zu verinnerlichen und anzuwenden. So, das ist das, was wir eben gesagt haben, was ich eben auch noch mal gezeichnet habe, brauchen wir nicht noch mal durchzugehen. Das macht
52:48
jetzt eigentlich wenig Sinn, das nehmen wir aus dem Prüfungsstoff raus, diese Sache ist noch rekursiv. Und Floyd Varshel ist noch mal, was ich eben gesagt habe, können
53:02
Sie noch mal sich diese Folie ansehen hinterher und noch mal gegenchecken, dass das, was ich hier an der Tafel gemacht habe und mündig erzählt habe, dass das dem entspricht, hoffentlich, was hier steht. So, warum ist das jetzt plötzlich nur noch N hoch drei, Bellmann-Ford war N hoch vier? Ja, weil wir in jeder einzelnen
53:23
iteration für jedes Paar aus Start- und Zielknoten nur zwei Längen miteinander zu vergleichen haben. Die, die für dieses Paar berechnet worden ist und die Länge, die sich aus diesen beiden Zahlen ergibt. Ja, in jeder einzelnen iteration ist für jeden einzelnen Paar eine konstante Aufwand da. Das ergibt
53:41
insgesamt N hoch drei. N iteration, N Quadrat Paare. So, ach so, man sollte vielleicht auch Dozenten von Algorithmen Veranstaltungen sagen, wie einfach das alles wird, wenn man alles immer an der Invariante aufhängt. So, dass man
54:06
das als eine Matrix speichern kann, das haben Sie in der GDI 2 gesehen. Das ist noch mal der Punkt, den ich mündlich angesprochen hatte vorhin. Sie können hinterher, das war im Zusammenhang mit Bellmann-Ford, Sie können hinterher die negativen Zyklen auf der
54:21
regionale ablesen. Alle, genau die Knoten, bei denen auf der regionale ein Wert kleiner Null ist, genau die sind einen negativen Zyklen drin. Diesen Alternativen-Check haben wir eben auch schon mal gesehen, das ist auch nichts Neues. Müssen wir uns das, ja gut, das
54:43
sollten wir uns ansehen. Transitive Hölle ist ein wichtiges Thema. Wir vergessen mal, dass es jetzt Distanzen gibt, dass es um kürzeste Wege gibt. Was zuweilen sehr wichtig ist, ist
55:00
die Information zu berechnen, zwischen welchen zwei Knoten es überhaupt eine Kante gibt. Entschuldigung nicht eine Kante, sondern ein Pfad. Ja und das kann man, das nennt man die transitive Hölle. Also Sie haben, das sind die echten Kanten vielleicht, ein paar echte Kanten, der Graf ist natürlich
55:21
viel größer und es gibt einen Pfad, da bilden Sie, das sind die transitiven Kanten, die Sie rein bilden können, das sind die Pfade. So haben wir noch das und so. Ja, wenn Sie immer transitiven Schritt machen, zwei Kanten
55:41
hernehmen und überbrücken, wenn Sie das oft genug machen, dann haben Sie eine Kante drin für jedes paar von Knoten, wo Sie eigentlich nur einen Pfad im ursprünglichen Grafen drin haben. Das ist die transitive Hölle oder das transitive Abschluss eines Grafen und was hier steht ist nichts anderes als die Bemerkung mit
56:00
den Algorithmen, die wir jetzt hier, eigentlich egal mit welchem, mit den Algorithmen, die wir jetzt hier hatten, können Sie immer, Sie nehmen einfach Kantenlänge 1 her, also neutrale Kantenlängen, können Sie immer die transitive Hölle berechnen. Überall da, wo ein endlicher Wert am Ende in der Matrix steht, da gibt es eine solche
56:21
Kante und der Wert, der darin steht, zum Beispiel für diese Kante hier, wäre dann 4, wenn Sie die Kantenlänge alle einsetzen. So, Johnsons Algorithmus ist noch mal eine sehr interessante Sache, die wollen wir nicht auslassen,
56:42
hat ein bisschen Ähnlichkeit mit dem Thema zielgerichtete Suche und A-Stern-Algorithmus, die wir beim letzten Mal betrachtet haben. Da geht es genau um solche Knotenwerte auch. Die Idee ist folgende, sie ändern sich,
57:02
wenn wir solche Knotenwerte haben, und wir ändern die Kanten nach so einem Schema ab, dass die neue Kantenlänge gleich der alten Kantenlänge plus der einen Knotenwert vom Startknoten minus dem Knotenwert vom Zielknoten ist,
57:22
dann werden kürzeste Wege in kürzeste Wege überführt. Die Weglänge ändern sich natürlich, aber das Verhältnis zwischen zwei Wegen vom selben Startknoten und dem Zielknoten bleibt dasselbe. Wenn einer von den beiden vorher kürzer war, mit den ursprünglichen C-Werten, ist das liegt einfach daran, dass diese
57:40
F-Werte, sie ändern sich oder sie können es dann auch noch mal, wenn sie wollen, nachschlagen. Für jeden internen Knoten des Fades kommt der F-Wert einmal positiv, einmal negativ vor in der Summe der Kantenlänge gemäß C-Strich hebt sich weg. Es
58:02
bleibt übrig, die bei diesen ganzen gegenseitigen Wegheben der F-Wert vom Startknoten und der F-Wert vom Zielknoten. Die sind natürlich für alle Pfade vom selben Startknoten und vom selben Zielknoten identisch. Also ändert sich nichts, wenn wir das so umsetzen. Nur was für Werte nehmen
58:22
wir her als F-Werte. Die Idee ist, wir machen einmal, wir machen einmal einen Bellmann-Ford, der ein bisschen anders ist, auf einem etwas anderen
58:42
Graf. Und zwar will ich denn skizzieren, wie dieser etwas andere Graf aussieht. Wobei es geht sogar, ich kenne eigentlich die Variante, wie das es im selben Grafen mit einem beliebigen Startknoten geht. Aber ich halte mich jetzt hier an die
59:01
Folie und füge einen neuen künstlichen Startknoten hinzu. So wir haben jetzt, das hier ist wie
59:23
üblich unser Graf. Den nennen wir hier D. Für die Graf, für gerichteten Graf, nicht wie es sonst immer geht. Und wir haben einen künstlichen neuen Startknoten. Wir sind ja beim Old Pairs eigentlich. Da haben wir keine einzelnen Startknoten. Aber jetzt fügen wir einen
59:40
rein und jeweils mit Länge 0 ziehen wir eine Kante von diesem Startknoten zu jedem echten Knoten hin. jeweils Länge 0. Jetzt führen wir Bellmann-Ford einmal aus.
01:00:00
wenn wir negative zykel drin haben dann sind sie natürlich in dem ursprünglichen die grafen drin klar Dann wie immer haben wir dann verloren aber Jetzt setzen wir Diese f-werte die sich jetzt magischerweise zu h-werten Gemausert haben dass das selbe was wir eben auf der letzten folie als f-werte hatten setzen wir als die berechnete distanz her
01:00:28
und der grund dafür warum wir das machen Wir setzen jetzt die die kantenlängen entsprechend sowie bis so wie wir es eben gesagt haben entsprechend um der grund warum wir das machen steht hier
01:00:44
Wenn wir mit diesen Wenn wir mit diesen werten mit diesen so berechneten werten diese Die kosten die die die länge modifizieren dann sind diese länge alle größer gleich null
01:01:00
Warum sind die alle größer gleich null Ja weil Setzen wir ein
01:01:31
C strich von uv wir wollen zeigen dass das größer gleich null ist das ist noch mal c uv das denkt gar nicht daran größer gleich null zu sein
01:01:42
plus Der in diesem künstlichen grafen berechnete distanz wert jetzt mit delta bezeichnet s u Was ist zuerst es nach u minus delta von s nach v so
01:02:00
und Die optimalitätsbedingung besagt gerade Dass die kürzeste weglänge von s nach v Natürlich nicht kürzer sein natürlich nicht größer sein kann als die kürzeste von s nach u plus dem weg plus der kante von u nach v Ja das ist der kürzeste weg links ist hier die kürzeste weg von s nach v und rechts ist die länge von
01:02:21
Irgend einen gewissen weg von s nach v nämlich kürzeres weg von s nach u plus kante von u nach v So und dann steht es aber schon da ich setze diese gleichung ein diese ungleichung schuldigung Und dann steht es schon da und jetzt
01:02:41
Wenn die kanten den größer gleich null ist trara Da können sie für alle weiteren für alle weiteren startknoten da extra verwendet auf diesen auf diesen modifizierten kantenlängen kriegen die richtigen kürzesten wege raus Sind nicht mehr die richtigen kantenlängen nicht mehr die richtigen fahrtlängen
01:03:03
Also die distanzwerte stimmt nicht aber die können sie dann das haben wir beim letzten vorletzten mal gesehen können sie dann wieder zurück rechnen indem sie Diese delta werte vom start und vom zielknoten das eine abziehen und das andere drauf artieren und fertigen haben sie auch die richtigen distanzwerte Haben wir schon mal betrachtet letztes oder vorletztes mal
01:03:20
Brauchen wir nicht noch mal hier zu betrachten das ist der grund warum wir das das ist und das ist das interessante was ich bei den schanzen algorithmus finde was sie machen ist Einmal anstatt bellmann fort mit jedem startknoten einmal sie können nicht einfach wie hergehen und da extra mit jedem startknoten einmal machen sie negativer kantenlängen da extra funktioniert nicht leider
01:03:41
Einmal bellmann fort auf einem hilfsgrafen auf der basis kriegen sie Kriegen sie modifizierte kantenlängen die größer gleich null sind können jetzt für jeden startknoten da extra aufrufen viel schneller als alles andere da extra schlägt nichts Und haben die richtigen wege müssen nur die die die distanzen entsprechend adjustieren wie wir schon mal beim letzten mal gesehen haben
01:04:08
Das ist eine das ist ein praktischer trick dabei nicht dass man also im prinzip schon da extra verwenden kann von jedem startknoten einmal um old pairs zu berechnen
01:04:22
Auch wenn die kantenlängen ursprünglich negativ sind die Modifizierten kantenlängen also teilweise negativ sein können die modifizierten kantenlängen sind nicht negativ So das ergibt dann natürlich eine entsprechend viel bessere zeit komplexität Je nachdem was sie da einsetzen brauchen wir nicht weiter zu diskutieren
01:04:45
Und auf sparse graphs das heißt wo die kantenzahl jetzt nicht viel krass größer ist als die knotenzahl Ich glaube ich hatte schon mal ganz zu anfang gesagt wenn sie beispielsweise planaren grafen haben einen grafen den sie kreuzungsfrei In die emene einbetten können
01:05:03
so zum beispiel So Dann ist die kantenzahl Höchstens 3n minus 6 die knotenzahl in die knotenzahl Betrachten wir hier und heute jetzt nicht warum das so ist dass es nun beispiel dafür
01:05:22
Ein geografisches netzwerk zum beispiel autobahnnetz und so weiter ist kein planar graf sondern hat brücken und tunnel Aber das sind jetzt nicht so viele das heißt also es bleibt noch dabei dass die dass die kantenzahl Linear einer größe der knotenzahl ist auch bei einem autobahnnetzwerk mit einer sehr kleinen konstante davor
01:05:47
das heißt also Auf autobahnnetzwerken wäre diese variante für all pairs falls man all pairs schottest pass auf autobahnnetzwerken machen will Wer diese variante dann schneller als flotwaser die asymptotische komplexität
01:06:02
So Endlich vorbei mit kürzesten wegen wir können die restliche zeit nutzen Um ins nächste thema einzusteigen Netzwerkflüsse kennen sie das aus der gd2
01:06:21
Bitte aus dem kindergarten ja ok das bild vielleicht Aber aber nicht unbedingt das thema haben sie netzwerkflüsse in der gd2 gesehen oder wer nicht Ok, dann können wir ja vieles auch wieder noch schnell machen bevor wir die dinge diese aus der gd2 kennen Sie wissen wir haben jetzt immer mit gerichteten grafen zu tun wir haben einen
01:06:45
Kostenwert auf jeder kante wir haben eine untere schranke für flusswert auf jeder kante eine oberschranke auf dem flusswert jeder kante für den flusswert jeder kante Wir haben einen balanswert Für jeden knoten ich weiß nicht ob sie es so allgemein eingeführt haben mit balanswerten b oder so etwas
01:07:05
Gut, dann machen wir es vielleicht nicht ganz so schnell so Was ist die situation? Wir haben hier eine situation die wahrscheinlich ein bisschen allgemeiner ist als wie sie es in der gd2 kennengelernt haben Wir haben einen gerichteten grafen wie in der gd2
01:07:23
Wir wissen worauf das hinaus laufen soll es soll flüsse die die kanten sind irgendwie rohre oder kabel oder Informationskanäle oder was auch immer und da sollen einheiten durchgeschickt werden Im allgemeinen gibt es eine obere kapazität man kann nicht zu viel durchschicken Das sind die aber bauens uij
01:07:42
Man kann aber auch durchaus in manchen anwendungsszenarien ist es sinnvoll auch eine untere schranke zu haben das heißt dass man mindestens lj fluss einheiten durchschicken muss durch durch jedes der der einzelnen Der einzelne kanten die rohre sind oder so etwas ich habe letztens gelesen durch die ganzen wassersparmaßnahmen ja
01:08:05
Toilette mit nur halber spülung und und du duschkopf mit mit reduziertem ausstoßen so weiter gibt es teilweise wohl schon gemeinden wo die Wo die wo die wasserversorgungswerte werke durch die durch die abwasser
01:08:22
Kanäle noch zusätzlich frischwasser durchpumpen müssen damit es da nicht nicht irgendwelche Probleme gibt mit dem fehlenden wasser was dadurch damit hat man nicht gerechnet Als man die kanäle gebaut hat oder aus irgendwelchen technischen gründen ist es sehr vorteilhaft dass da immer eine gewisse mindestmenge
01:08:40
Durchfließt das wäre ein fall wo wir solche unteren schranken für den für den fluss haben das mindestens so viel durchfließen muss Wir haben kosten das heißt pro fluss einheit die wir durchschicken Kostet und die durch die kante von i nach j durch schicken Kostet uns jede fluss einheit cij in euro oder was auch immer
01:09:02
so Fluss muss von irgendwo nach irgendwo fließen Ja es gibt quellen und es gibt senken sie haben wahrscheinlich die einfache situation in der Gdj 2 betrachtet es gibt eine quelle von der fließt aller fluss raus und es gibt eine senke in die fließt aller fluss rein Wir betrachten das jetzt etwas allgemeiner wir sagen
01:09:20
Es gibt Quellknoten supply also die die etwas bereitstellen Und zwar was die bereitstellen ist Pro sekunde oder wie auch immer b von v einheiten die werden da reingepumpt ins netz Von diesem knuten aus in seine
01:09:40
Von ihm rausgehenden kanten und von da aus müssen sie dann irgendwie weiter transportiert werden Dann gibt es andere kanten die sind senken die haben bedarf Da wird was reingepumpt also Das ganze hat natürlich jetzt durch die erneuerbaren energien eine eine tatsächlich eine aktualität gewonnen Dass es dass es da dass es da quellknoten gibt die produzieren strom
01:10:04
Egal ob man den braucht aber der muss dann irgendwo ab der muss dann irgendwo weiter getrieben werden Und auf der anderen seite gibt es zielknoten die unter umständen viel weniger brauchen als das was rein Also je nachdem bei prallem sonnenschein im sommer ist das was rein reinkommt vor allen quellknoten
01:10:23
größer als das was abgenommen wird In deutschland ist es ja nicht so weit verbreitet klimaanlagen zu haben sonst wäre das kein problem den ganzen strom abzunehmen Während während im tiefsten winter wo die ganzen solarzellen auf den auf den dächern alle nicht nicht viel bringen
01:10:44
Da da fehlt es dann wieder da muss dann von woanders her der der supply herkommen und transmitnotes das sind einfach zwischenstationen Die haben den b-wert den balanswert null das heißt also genau das was reingeht pro pro zeiteinheit ist auch das was rausgehen soll
01:11:02
pro zeiteinheit wir reden immer von einem stabilen zustand das heißt also von zeiteinheit zur zeiteinheit ändert sich der flusswert auf jeder kante nicht Die variante dass dieser zustand instabil ist wurde auch intensiv in der algorithmik untersucht auf basis von dem was wir hier betrachten Ist natürlich viel komplizierter und wäre eher inhalt einer weiterführenden veranstaltung vielleicht ein seminars
01:11:27
So wir wollen keine Parallelenkanten oder schleifen haben die würden uns eigentlich auch nicht weiter stören aber gut wenn wir die nicht haben wollen warum die Nicht haben die stören uns ja gut die würden uns natürlich hier oben stören die parallelen kanten wenn wir einfach indizieren die kante von i nach j
01:11:41
Ist cej wenn wir zwei parallele kanten haben von i nach j welche von beiden ist das jetzt Aber ansonsten würde uns das eigentlich methodisch nicht stören So das min cost flow problem das haben sie wahrscheinlich nicht in einer gd zu gesehen das ist das allgemeinere problem wir wollen einen fluss Haben in den kanten also die kanten sind wieder rohre kommunikationskanäle oder was auch immer
01:12:04
wir wollen Einen fluss haben einen statischen fluss der sich von zeiteinheit zu zeiteinheit nicht ändert Der kostet uns natürlich etwas und diese kosten wollen wir minimieren Jede fluss einheit die wir durch die kante xi durch die kante j schicken kostet uns cej einheiten an euro
01:12:25
Vielleicht und wenn wir xe j einheiten von i nach j durch die kante j schicken kostet uns das dementsprechend cej mal xj einheiten Und das über alle kanten aufsummiert ist die sind die gesamten kosten die uns das alles kostet
01:12:41
so Was Müssen wir dabei beachten wir müssen die balance an jedem knoten beachten und zwar Dass das etwas komplizierter ist wir haben wir haben wir zuerst eine dreiteilung gehabt Knoten mit b größer null mit b kleiner null mit b gleich null die einen waren die
01:13:02
Quellen die was reingeschickt haben ins netz die anderen die was rausgezogen haben und die dritten wo es immer nur der fluss durchgeht ohne ohne verlust und ohne gewinn So aber natürlich kann es durchaus auch beispielsweise sein dass ein knoten der was reinbringt Ins netz dass der gleichzeitig auch ein transshipment not ist oder nur der was rausbringt aus dem netz
01:13:28
Dass der gleichzeitig auch ein transshipment not ist ja wir haben so einen armen kleinen knoten
01:13:40
Da gehen irgendwelche kanten rein Und irgendwelche kanten gehen raus und Der bringt von hier das ist eine quelle von da kommt was hier nach rechts über diese kanten raus Aber es kann trotzdem sein dass noch hier fluss reingeht der dann auch hier
01:14:02
Fließen muss oder umgekehrt deshalb vereinheitlichen wir das dass wir sagen die summe der raus fließenden flüss einheiten minus der summe der reinen fließenden flüss einheiten ist gleich dieser gesamt balance ja dann Dann haben wir in dieser formulierung ist die möglichkeit drin dass auch selbst in einen quellknoten noch
01:14:26
Noch hinter rücks fluss rein fließen kann und und dass aus einem senken knoten noch hinter rücks fluss raus fließen kann So und das ganze noch unter der bedingung dass der flusswert auf jeder kante zwischen der unteren und der oberen schranke ist
01:14:43
Das ist das problem mit dem wir uns zuvorderst beschäftigen werden Für jede kante haben wir also einen wert wir haben also sowas wie ein vector Dessen komponenten mit den kanten indiziert sind sie können sich das vorstellen die kanten sind durchnummeriert und das sind die
01:15:04
das sind die indiziers des vektors so können man sich das vector vorstellen und wie gesagt ein statischer fluss Statischen klammern weil wenn man in der algorithme vor einem fluss redet meint man in der allgemeinen Statischen fluss wenn man einen nicht statischen fluss meint dann sollte dann redet man meist von einem dynamischen fluss überraschung
01:15:27
ok das erste sind die Flusserhaltungsbedingungen des weiter die kapazitätsbeschränkungen nach oben nach unten
01:15:42
So jetzt noch eine kleine mathematische spielerei am rande Wenn wir eine bestimmte art von matrix hernehmen die knotenkanten inzidenz matrix Was ist das das haben sie mit sicherheit in der gd2 gesehen?
01:16:10
So jetzt muss ich mir überlegen wo sind jetzt am besten die knoten wo sind die kanten das ist eine große matrix Wenn sie so durchgehen gehen sie alle
01:16:24
Anhand eines knotens durch das heißt also Hier haben sie die kanten hier haben sie eine kante vw eine spalte für eine kante vw Hier haben sie irgendwo einen knoten v und einen knoten w also eine zeile für jeden knoten
01:16:46
Und an dieser stelle steht eine eins eine plus eins an dieser stelle eine minus eins und ansonsten steht überall null in dieser spalte Und das machen sie mit jeder spalte das haben sie mit sicherheit schon mal gesehen So das ist diese matrix
01:17:03
Ist sie hier genannt groß n so und was hier steht ist Wenn sie jetzt
01:17:21
das multiplizieren Mit dem diesen besagten vector wo irgendwo mittendrin jetzt xvw steht Ja was steht denn da hier Was steht an der stelle v und was steht an der stelle w
01:17:43
Hier sie gehen hier Ganz normale matrix vector multiplication sie gehen hier die zeile durch in der matrix und gehen den vector durch und Für jede kante die rausgeht aus diesem knoten
01:18:03
Addieren sie das mit plus eins auf Also positiv und für jede kante die raus geht die reingeht ich mache mal hier noch eine kante uv hier steht dann eine Minus eins an dieser stelle für die kante in diesen knoten reingeht
01:18:21
Addieren sie das den x wert auf mit einem minus das heißt sie haben genau das was hier für den knoten v steht wenn sie normale Matrix multiplication machen also matrix vector multiplication ist exakt diese gleichung
01:18:42
einfach in verkürzter matrix schreibweise Hier also halt hier müsste ich das genauer hinschreiben Hier steht jetzt b von v und hier steht jetzt b von w die summe dieser einzelnen produkte hier ist ja fast immer null
01:19:04
Ne ist es nicht also halt für die kanten die nicht vorkommen ist es null Die nicht mit v zu tun haben für die kanten die aus v rausgehen Ist hier in dieser zeile ein eintrag plus eins für die kanten die in v reingehen ist in dieser zeile ein eintrag minus eins Und das heißt für alle die die rausgehen wird der entsprechende x wert
01:19:24
Positiv hinzugezählt für alle die reingehen wird diese entsprechende x wert negativ gezählt und auf der rechten seite setzen wir dann den balanswerte an und das reduziert diese Diesen satz von gleichungen für jeden knoten eine gleichung reduziert das auf diese matrix schreibweise
01:19:43
nx gleich b kleine mathematische spielerei am rande Also sagen sie das nicht weiter dass ich das eine mathematische spielerei nenne dafür wird mir bestimmt diverse leute an die google gehen
01:20:04
Jetzt kommt keine frage von wegen was lassen sie sich das kosten oder so So Eine ein spezialfall der durchaus von einigen praktischen interesse ist ist der fall einer strömung
01:20:20
circulation nämlich das sämtliche knoten transshipments notes sind Also für jeden einzelnen knoten geht die summe rein gleich der summe raus beachten sie dass der nullfluss nicht immer Zulässig ist denn wir haben ja untere schranken Ja wir haben hier Untere schranken und wenn diese untere schranke größer null ist sie kann auch kleiner null oder gleichnull sein
01:20:43
Wenn diese größer null ist ist der nullfluss nicht zulässig der fluss der über jede einzelne kante nulleinheiten fließen lässt so Damit das ganze nur funktioniert macht man sich mal klar Muss man sich mal klar machen dass die summe sämtlicher balanswerte null sein müssen warum
01:21:06
warum ist die summe sämtlicher balanswerte null sein Schauen sie sich diese gleichung hier an noch mal Und bedenken sie dass diese gleichung für jeden knoten einmal vorkommt Stellen sich für jeden knoten diese gleichung jeweils hingeschrieben untereinander
01:21:28
so Wenn sie wenn sie diese gleichung alle addieren links alle linken seiten addieren und alle rechten seiten addieren Was kriegen sie links raus ja sie haben diese gleichung für jeden knoten so untereinander
01:21:47
Schön geschrieben und addieren alle linken seiten mit den summe x iot minus summe x iot die und addieren die rechten seiten Was kriegen sie links raus? Null warum ja energiener erhöhungssatz ist jetzt vielleicht eine etwas
01:22:08
Steile begründung von nichts kommt nichts der das mathematische argument was wird denke ich gleich einsichtig ist und was wir jetzt durchrechnen Müssen ist einfach die jede einzelne kante kommt beim bei seinem bei ihrem
01:22:22
Startnoten Hier vor bei ihm zielknoten hier vor Das heißt der x wert jede einzelne kante kommt einfach einmal positiv und einmal negativ in dieser summe vor hebt sich weg Wenn linke hand die summe alle null ist da muss natürlich damit die gleichung aufgehen rechte hand auch alles null sein Und nichts anderes wird hier behauptet damit das ganze überhaupt lösbar ist muss die summe der balancen null sein das wissen sie von
01:22:47
dem thema erneuerbare energien Also da wird natürlich dafür gesorgt dass die balans immer die balanswerte immer null sind weil es ja irgendwelche senken gibt Dass das ganze irgendwo keine ahnung abgeleitet wird irgendwo hin wo es dann wenigstens kein schaden mehr anrichtet aber auch kein nutz mehr hat
01:23:05
Wobei ich habe jetzt gerade es ist in den in den in den online medien drin einen vorschlag von der rwe Die guten alten nachtspeicher öfen wieder Wieder zu verwenden Nämlich da zu zeiten mit einer etwas anderen automatik ich weiß nicht ob sie das prinzip nachtspeicher öfen kennen
01:23:25
Es gibt im prinzip vom e-werk zwei arten von strom einen teuren und einen billigen und den billigen kriegt man nur Wenn man bestimmtes gerät hat wie nachtspeicherofen wird dann eben billiger abgerechnet billiger nachtstrom eben Und mit einer etwas anderen vorrichtung mit einer anderen automatik
01:23:42
Geht der nachtspeicherofen immer dann an wenn der strom besonders billig ist weil eben gerade viel eingespeist wird Und damit kann man so ein stück weit das speicherproblem lösen dass man ja hat ja mit den erneuerbaren energie Wohin mit dem strom dann wenn man viel braucht kriegt man nicht viel
01:24:02
Dazwischen müssen man speichern und die idee dass die zentral zu speichern mit nachtspeicher öfen mal gucken Sie haben das durchgerechnet also die sind der meinung dass das Funktionieren würde Gut hin und wieder
01:24:20
Gehen wir Schränken wir das von vornherein so ein dass die das sämtliche werte Kosten kapazitäten und b werte alle ganz zahlig sind wir hatten es schon mal dass das keine wirkliche einschränkung der allgemeinheit ist Ja sie können problemlos Wenn wenn sie keine ganz zahligen werte haben wenn sie wenn sie nachkommersstellen haben dann können sie beispielsweise das ja auf
01:24:47
auf ganze tausend tausendstel Runden und haben da keinen großen rundungsfehler drin gemacht also wenn sie es nur ausreichend fein granular machen können sie den rundungsfehler Natürlich beliebig reduzieren und wenn sie es auf tau ganze tausendstel reduzieren
01:25:03
Naja, dann wird alles um den faktor 1000 multipliziert und haben sie es ganz zahlig Ist also wirklich keine einschränkung Ja manchmal möchte man auch sie kennen das von den kürzesten wegen manchmal möchte man auch
01:25:21
unendliche nicht nur unendliche weglegen sondern unendliche kapazität haben wenn es also kanten gibt auf die man über die man beliebig viel rüber schicken kann die keine die keine einschränkung haben Ja das ist das ist diese bemerkung ist etwas was eigentlich auch schon für kürzeste wege natürlich gilt
01:25:47
Aber hier vielleicht noch ein bisschen stärker zuschlägt Wenn sie werte addieren Dann kann es natürlich immer sein dass sie über den maximalen wert
01:26:01
hinausgehen der ist bei Der ist bei beim datentyp entwei in java mit 32 bitt gar nicht mal so groß ich glaube der ist so Größenordnung vier bis fünf milliarden wenn ich mich recht entsinne ist lange her Okay zwei milliarden also der gesamtbereich von minus bis plus ist dann 4, irgendwas milliarden Also wenn sie das mal vergleichen mit den staatsschulden dann ist das eine lächerliche zahl
01:26:26
Also sie können ganz schnell machen sich immer bewusst Zum ist mit datentyp short und int können sie ganz schnell selbst in Ganz natürlichen größenordnungen zu einem overflow kommen mit long wird schon ein bisschen schwieriger da
01:26:41
Dafür dürfte ist die wahrscheinlichkeit groß dass sie bei long halt Beim datentyp long das ist halt nicht der standard typ Der der typischer weise unterstützt wird von der architektur so dass alles vielleicht ein bisschen langsamer geht aber das ist kaffesatzleserei Was jetzt schnell und was langsam geht sollte ich lieber nicht machen So jetzt gehen wir in den technischen details und das heben wir uns dann aber auf bis zum nächsten mal das macht überhaupt
01:27:05
Keinen sinn dass wir jetzt hier mittendrin dann In der einfnung der technischen details dann aufhören gut dann Danke, ich ihn für heute und wir sind am ende