Shortest Paths III / Network Flows

Video thumbnail (Frame 0) Video thumbnail (Frame 15101) Video thumbnail (Frame 24338) Video thumbnail (Frame 32807) Video thumbnail (Frame 34762) Video thumbnail (Frame 37619) Video thumbnail (Frame 42967) Video thumbnail (Frame 48629) Video thumbnail (Frame 50672) Video thumbnail (Frame 58516) Video thumbnail (Frame 64212) Video thumbnail (Frame 67272) Video thumbnail (Frame 78797) Video thumbnail (Frame 80759) Video thumbnail (Frame 84759) Video thumbnail (Frame 87564) Video thumbnail (Frame 96786) Video thumbnail (Frame 99131) Video thumbnail (Frame 107654) Video thumbnail (Frame 120024) Video thumbnail (Frame 121712) Video thumbnail (Frame 124029) Video thumbnail (Frame 126351) Video thumbnail (Frame 130432)
Video in TIB AV-Portal: Shortest Paths III / Network Flows

Formal Metadata

Title
Shortest Paths III / Network Flows
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 license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Kante Shortest path problem Trail Moment (mathematics) Mathematisches Zeichen Vertex (graph theory) Iteration Optimum Length Inequality (mathematics) Element (mathematics) Directed graph
Kante Shortest path problem Connected space Zahl Supremum Optimum Iteration Length Directed graph Distance
Kante Logical constant Shortest path problem Trail Stress (mechanics) Theory Order of magnitude Distance Connected space Scalar potential Summation Length Directed graph
Mathematics Stress (mechanics) Compass (drafting) Negative number Length
Mathematics Matrix (mathematics) Quote Length
Mathematics Partition (number theory) Iteration Military operation Vertex (graph theory) Content (media) Optimum Quote Directed graph
Algebraic structure Reduction of order Ideal (ethics) Exponential function Element (mathematics)
Kante Stress (mechanics) Compass (drafting) Graph (mathematics) Moment (mathematics) Content (media) Total S.A. Equation Inequality (mathematics) Rand Invariant (mathematics) Negative number Optimum Negative number Absolute value Summation Length Absolute value Directed graph
Kante Sign (mathematics) Stress (mechanics) Keilförmige Anordnung Matrix (mathematics) Diagonal Index Bellman equation Laufzeit Negative number Directed graph Length
Operations research Shortest path problem Trail INTEGRAL State of matter Nummerierung Desire path Square Set (mathematics) Term (mathematics) Number Supremum Iteration Vertex (graph theory) Summation Length
Subset Square Iteration Vertex (graph theory) Length
Kante Operations research Stress (mechanics) Weight Desire path List of anatomical isthmi Group action Transformation (genetics) Sign (mathematics) Keilförmige Anordnung Matrix (mathematics) Algebraic closure Zusammenhang <Mathematik> Negative number Negative number Diagonal Matrix (mathematics) Length
Kante Sign (mathematics) Keilförmige Anordnung State of matter Weight Desire path Summation Transformation (genetics) Length
Zahl Keilförmige Anordnung State of matter List of anatomical isthmi Universe (mathematics) Optimum Set (mathematics) Binary file Equation Length Professional network service Physical quantity
Boom barrier Kante Mass flow rate Spring (hydrology) Graph (mathematics) Model theory Supremum Quote Parallelen Untere Schranke Flux Maß <Mathematik>
Kante Polymorphism (materials science) Zahl Matrix (mathematics) Constraint (mathematics) Equation Mathematics Rand Matrix (mathematics) Vector graphics Number theory Supremum Summation Nichtlineares Gleichungssystem Dynamic range Strömung Compact space Multiplication Product (category theory) Euclidean vector Compass (drafting) Incidence algebra Connected space Spring (hydrology) Vertex (graph theory) Untere Schranke Matrix (mathematics) Maß <Mathematik>
Constraint (mathematics) Feasibility study Summation Equation Untere Schranke Matrix (mathematics) Maß <Mathematik> Compact space
Round-off error Zahl Surface Number theory Summation Automaton Kapazität <Mathematik> Infinity Rounding Factorization Order of magnitude
Graph (mathematics)
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so hallo allerseits
hier war mir beim letzten Mal stehen denn sind immer noch beim Thema was Sie ja schon aus G 2 alles im Prinzip kennen kürzesten Wege was wir noch ein bisschen mehr in einen etwas allgemeineren Blickwinkel hin einbetten sie kennen Algorithmen wieder extra das hat mir beim letzten Mal auch noch einmal wiederholt werden heute noch mal kurz auf wenn man fort und fort war schon zu sprechen kommen jetzt eingebettet in die Theorie die wir und jetzt mal entwickelt haben und dann wenn wir hoffentlich endlich die Themen verlassen kürzeste Wege und ähnliches und uns zu weiterführenden Themen dann hin bewegen so ich hier sehen Sie noch einmal den allgemeinen Algorithmus sie ändern sich da extra hat in jeder Iteration ein Distanz wird endgültig gesetzt und der Gottesbeweis bedeutet im Prinzip zu beweisen dass der wert denn diese dass diese Distanz variabel Fliesen ein Knoten hat tatsächlich der Yale Distanz wird dieses Knotens ist also die Länge des kürzesten Pfades vom Staat Noten zu diesen Knoten wir haben aber andere ein anderes Konzept kennen gelernt das haben Sie auch schon mehr G 2 kennen gelernt wenn man fort war zwar schon wo erst ganz zum Schluss nach der allerletzte Iterationen sämtliche Distanz Werte endgültig fest sind in jeder einzelnen zwischen Iteration in jedem einzelnen Schritt des 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 Distanz Werte von allen Knoten tatsächlich schon der Craig der bis zum allerletzten Schloss so hier ist noch mal der allgemeine Algorithmus es ist gerade meine algorithmische Schema wie man wir sind wieder bei der Situation gegeben sein gerichteter Graph mit Kantenlängen Startknoten S und wir wollen die Distanzen zu allen anderen Knoten haben sie kennen das ja schon das ist immer dasselbe Bild wir haben den Distanz wird von es gleich 0 da kann man nix falsch machen wenn man den auf 0 setzen ja da brauche ich groß nachzudenken und alle anderen Distanz würde setzen wir auf plus unendlich weil wir immer haben wollen das der Wert der dort steht in einem für einen Knoten V der wird die Frau einen Knoten V ist entweder plus unendlich oder die Länge irgendeines Vaters von es noch vor Ort natürlich mit der Zielsetzung dass am Ende die Länge eines kürzesten Pfades ist zwischendurch ist immer die Länge irgendeines Vaters oder eben war solange die Sage nun nicht berührt worden ist und endlich so so dass wir keinen Fehler machen wenn wir den Distanz wird auch immer wieder nur reduzieren ja wir haben eine neue Möglichkeit entdeckt zu diesem Knoten zu kommen über eine andere kannte haben den Distanz zum Start Nutzen dieser kannte wie sehr man sich der Staat nun insgesamt wir haben hier eine kannte die zu diesem Knoten vorbei führt gucken jetzt von einem Knoten dahin wir haben ein wird wir haben ein die wird für diesen Knoten und wenn in dem Moment gerade der Distanz wird von Frau größer als der Distanz wird von Plus der Länge von noch Haushalt hieß es mit C abgekürzt nicht mit L es sollte der konsistent bleiben so wenn das der Fall ist das ist die rechts ist die Länge eines gewissen Weges von nach vorn nämlich des Weges für den die EU steht von es nach der kannte von und nach V links ist die Länge und eines Weges oder das unendlich bin vor noch nie angefasst worden ist und wir können nichts falsch machen wenn wir sagen also die in die Variante ist die von voraus die Länge eines und eines Weges von ist nach V wir können nichts falsch machen wenn wir jetzt setzen des von V also ich verwende hier mathematische Notation colon gleich aber das was Sie recht steht die Länge dieses Weges ja das ist das Grundprinzip ist genauso eigentlich auch in der extra das Grundprinzip dass es immer wieder dieselbe dass derselbe eine Bausteinen wie man die das dann den Distanz wird korrigierten dabei auf der sicheren Seite ist so was machen wir 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 wir dann sehen dann müssen sie das halt mit dem vollen Ausdruck in vergleichen weil sie es auch nicht wie das kommt gut wirken überrascht sein dass ist also Sie sehen man kann man noch so viel Arbeit ist immer wieder für Überraschungen gut so wir setzen die die reingehen erkannte jedes Knotens wie immer auf 0 am Anfang weil eben jedes Knotens der dass das unendlich hat weil wir eben noch keinen einzigen Fahrt haben den Weg den sie über dem so wie wäre es etwa so in dem Moment wenn wir wenn wir das setzen würden wir auch zugleich noch die von V die Kante von Noch-Vorsitzenden als die aktuelle nächsten letzte Kante eines Falles oder andersrum gesagt als die letzte Kante des aktuellen Vaters von es nach vor so und dann gehen wir einfach durch wir halten eine Liste von Knoten die momentan Kandidaten sind niemand immer in jedem Schritt 1 Element man raus gucken uns die einzelnen Kanten an die aus dem ausführen und für Netz diesen Schritt aus den ich an der Tafel hatte korrigieren die gegebenenfalls wenn die Distanz Werte so sind wie sie hier eine Tafel gerade stehen in der 1. Zeile dann wird eben diese Satzung da unten gemacht so und dann kann es noch an wenn wir wirklich was passiert ist mit dieser keine wenn diese Distanz er tatsächlich durch diesen korrekt Schritt verändert worden ist und das gerade jetzt dieser Knoten nicht in der Liste ist dann fügen denn lässt er eine Weile wählen Sie wenn Sie diesen Knoten V er jetzt so behandeln von ausgehend Obst dafür ist die Distanz hier verändern dass sie Distanz von vor den das 1 von vor verändern es es kann durchaus sein das bis dahin bis zu diesem Moment hier das alles gestimmt hat diese Distanz Werte hier gestimmt haben durch das vor nicht beeinflusst worden sind oder das Vorgehen und in dem Moment in Distanz wert hier verändern dann kann es sein dass über diese kannten die Optimalität bei denen nicht mehr für das da müssen die also wieder rein die die Reinheit heißt den Knoten V 1 diese kann reinzubringen heißen Quotenfrau reinzubringen deshalb ist es eine Knoten müsste keine kann ist das Leben Knoten dann jeweils noch mal weil wir sowieso alle ausgehenden Knoten bekannten eines Knoten dann betrachten das noch mal irgendwann muss nicht gleich sein irgendwann vielleicht später ich Liste an und und machen so lange bis die ist der 1. wir für immer alle nur ein Element in dieses nur ein Knoten die Lästereien wenn potenzielle von diesen Knoten ausgehend die Optimalität spielen auf mindestens einer kannte verletzt sein könnte wenn man die Liste aller ist dann haben wir keine einzige Minute mehr bei der ausgehenden kann denn die Optimalität Bedingung verletzt sein könnte und dann sind wir fertig denn wir Mannesmann mal gesehen wenn die optimale Testbedingungen für alle kannten erfüllt ist nämlich gerade das was hier was hier zudem zur Veränderung geführt hat die Optimalität Bedingung ist gerade die Bedingungen für jede Kante UV dass die von Frau kleiner gleich die von bloß wenn von und nach V ist wenn das für alle kannten gilt genau dann sind die Distanz wird allesamt korrekt hat mir beim letzten Mal bewiesen und diese und diese Tatsache dass das genau dann wenn diese wenn dieser Ungleichung für jede Kante gilt das genau dann alles unsere korrekt sind das ist die Rechtfertigung für diesen korrekt Schritt in jeder Iteration dass wir genau dann wenn es um verletzt ist mit dafür 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 das wie er diese optimal die fällt sein könnte dass wir dann die Schleife beenden
so viel vor zum Beispiel nicht gesagt wie die aussehen sollte zum Beispiel kann das nur eine viel Flughöhe seien Sie wissen was sehr viel verkehr ist vorne holt man rausfinden steckt man rein wir wir gehen durch die die die Kanten durch und jeder kannte jeder einzelne kann der prüfen
wir die und auf die Art und Weise also wir machen jetzt hier in dieser Reihenfolge wenn das viel Fucky ist dann läuft das darauf hinaus dass wir immer wieder durch alle kannten die noch potenziell in Frage kommen also nicht mehr um den durch alle kannten aber alle kann die noch die noch vielleicht die Optimalität Bedingung der aktuelle verletzen könnten könnten gehen wir mal durch also es ist weiterhin eine Knoten Keyhole nicht von Knoten aber was da aber für jeden Knoten kommen sie alle kannten an immer am besten in derselben Reihenfolge und gehen auf die Art und Weise immer durch alle potenziellen kann in derselben Reihenfolge durch so und das ist nicht überraschend viel hat sehr viel mit breiten Suche zu tun nach jedem nach dem nach dem Karten Durchlauf also nachdem wir mal durch die durch die ganze kann meine durchgekommen sind das ist etwas ich glaube nicht dass das freilich ich erst mal gesagt ich glaube nicht dass diese Aussage wirklich genau korrekt ist aber sie ist die echt Aussage sogar noch ein klein wenig wie soll ich sagen besser sie zum ist komplizierter aber er hat dieselbe Ghazi sowas steht erst mal hier als Aussage nach Karsch nach K Durchläufen hat besteht in jedem Distanz wert die Länge eines kürzesten Pfades der höchstens K Kanten hat das kennen Sie von das ist nichts anderes als der wenn man fort Algorithmus was Sie hier sehen jetzt nicht als Ort Version sondern als Version von einem Knoten so einen anderen warum schauen Sie wir sind hier in dieser Situation Karten schwirrt so nach Induktions- Voraussetzung ist das hier die Länge eines kürzesten Weges dieses dann oder dass selber ein eingeleitet habe es ein kürzeste Weg mit maximal kam das von erst nach und da fiel es auch die Länge eines kürzesten Weges mit maximal kam es einst kannten von erst nach und 1 wegen die höchstens kann es einscannen haben ist das bis zu was das jeweils ein Christa weg und diese kann diese kannten Zahl die obere Schranke ist für für die Länge in im Sinne von Anzahl kannten die wächst mit die mit ihr von Iteration zu Iteration und 1 einschritten haben Sie alle Vater drin ja keine Fahrt kann mehr als 1 kannten enthalten unmöglich nein es als Karten nach einem dieser Schritt Entschuldigung sind Sie garantiert mit dem Algorithmus durch so so wählen das hier der der kürzeste Weg wenn wir diese Update machen oder anders und es gibt 2 Möglichkeiten entweder Sie machen diesen Update nicht dann bleibt es bei dieser Länge dann bleibt es hinterher das das war da sich nichts ändert das das ist weiterhin die die Länge 1 für Frau die Länge eines kürzesten Weges mit maximal K minus 1 kannten das ist natürlich auch ein kürzeste Weg mit maximal K könnten dann so wenn ich habe hier was ändert über die nur eine kann hinzufügen kommen wir von K minus 1 nach K das heißt wenn wir tatsächlich ein oder für sogar mehrere arktischen Schritte machen mit verschiedenen kannten das kann ja sein dass sie nicht nur 1 mal diesen Abgleich Schritt machen in dieser K in diesen Karten passt sondern mehrfach mit verschiedenen kann aber wie man's auch dreht und wendet Distanz wird der Staat nur diese alle kannten war immer die Länge eines kürzesten Weges mit maximal kann es einst kannten eine Kante dazu ist jetzt die Länge eines kürzesten Weges von maximal K kannten so warum bin ich mir nicht sicher dass die Aussage so aus so jetzt kompliziert genug ist weil ich oder will oder ist das doch genau weiß das noch was passieren kann in so einem Pass ist zufälligerweise meines Erachtens wir können sehr gerne Markus diskutieren können Sie mir wieder vielleicht sagen dass das was ich mir überlegt habe falsch ist das ist doch so ist wie es richtig ist dann frage ich wieder ob mich jemand anderes die vor diesem übernehmen will und dieselbe Antwort weil ich derjenige bin der bezahlt wird das wird so langsam zum einen Gag die bezahlen könnte man vielleicht auch als einen Blick bezeichnen haben so ist kann zufällig sein wenn wir Sohn sonntags durchmachen das wir vielleicht ist eine Kante erwischen und zufällig ist später
dann die nächste K im selben Pass ist die nicht später ist die hier später ist die hier später ist die er später ist er später zu einem Knoten fort ja nehmen sie an diesem allerersten in dem allerersten parat ja da war ursprüngliche noch alles unendlich und so zufällig ich ist dass die 1. kannte die angefasst wurde da wurde dieser wird entsprechen runtergesetzt dann im selben passt diese kannte als 2. zufällig die als 3. 4. 5. 6. das heißt also wir haben tatsächlich 1 wird hier als Distanz wird von Frau der garantiert nicht größer ist als die Länge eines kürzesten Pfades mit maximal einer könnte ja aber Potential sogar kleiner ist als das was hier in den Theorien drinsteht es ist ein der die Länge eines kürzesten Weges ist und wir können ja vielleicht das Beispiel noch fortführen wir könnten zum Beispiel sagen es gibt tatsächlich noch mehr kannte ich dann wie einer dieser eine kann dann wäre die Länge dieser kannte die Länge eines Kreuzes kann jedes mit maximal einer kannte logisch es gibt ja nur diesen einen Weg aber es kann auch durchaus sein das in einem passt das hier alles in nacheinander gemacht wird und wenn die Länge dieses Weges klar dass ist die Länge dieser könnte dann würde das diese Länge dieses Weges herauskommen das ist aber nicht die Länge eines Christen Wege sind maximal anerkannte sondern möglicherweise etwas kürzeres deshalb bin ich der ist das der Gedanke wie klar gewonnen deshalb bin ich der Meinung dass das Theorem etwas zu und kompliziert formuliert wurde das dann noch mit den Komplikation ist ein er würde den Finnen aber es kann ja sein dass diese Karte das ist richtig der Algorithmus würde diesen einen Schritt finden aber es kann ja sein dass diese kann der länger ist als diese ganze Regionen ja wo ist also wir machen doch hier so A B C D E F G und Fauna nicht ins wir setzen zufällig in folgender Reihenfolge dar wie das kurz sagen die von Art gesetzt die von S bloß länger es aber in dieser Reihenfolge die von B gesetzt den vollen ja plus Länge A und so weiter bis am Ende des von V gesetzt die Form Ehe bloß länger die Frau ja und wenn wenn das kürzer ist ja vielleicht aber infolge von oder vielleicht auch in der es eigentlich egal aber wenn diese gesamte hier wenn unten die Summe der einzelnen kann man kürzer ist als die die Länge dieser kannte ja die haben alle länger als oder die hat die eine Million der Ohren dann würde er nicht eine Million auskommen nicht zufälligerweise sondern das würde diese 1 2 3 4 5 6 die Angst und die 6 als das herauskommen das heißt also das ist der Grund warum ich der Meinung bin dass das Lemma noch unter komplex ist es müsste noch etwas genau formuliert werden dass der tatsächliche distanzierter dran drinsteht nicht größer ist sondern höchstens kleiner oder gleich ist zur Länge eines Christen Weges von von Karin erkannten Kowski O 4 als sehr sehr genau ob er sagt genau eine Fahrt von Höchst also in 1. dazu und von höchstens einer Kante die Länge eines Christen nix von höchstens einer Kante das wäre in unserem Beispiel daran korrekt im Lemma wenn der eine Million ausgeben wenn die Oberkante 1 Millionen hat warum nicht die nein also das Lemma sagt was nicht der Algorithmus er sagt nach einem ich besitze für K gleich 1 1 und er sagt nach einem Schritt hatte die Länge eines gibt ist weil ist mit höchstens einer Kante gefunden mehr die die da nun komplett des Passes noch sicher keine Tattoos sonst nur bei schon ist ok ja das heißt also damit mit dieser Formulierung ist es ist dieses Beispiel was ich mir überlegt habe ausgeschlossen okay ja okay dann dann okay dann dieser Formulierung ich glaube das ist wahrscheinlich beabsichtigt gewesen hatte nur diesen Fall unendlich ausschließen wollen mit dieser Formulierung aber sie haben ich dann diese Formulierung ist mein Beispiel auch ausgeschlossen Gott wieder was dazugelernt wenn interessante Diskussion zur Prüfung der Liebenden ist alles aufgenommen so Induktion Anzahl der der Schritte das habe ich eben angedeutet wie diesen Optionen aus dem Weg geht wie viele Schritte sind
notwendig da jeder Pfad höchstens Ende seines kannten haben kann also jeder Pforte keine Züge enthält sind wir nach 1 1 Durchläufen durch und für jede Kante kostet das eine Operation einen Jahr konstanter Operation wir kriegen Durchläufe Größenordnung und kannten mich in jedem Durchlauf das ergibt dann einmal so
das kann man noch ein bisschen besser machen die könnten in der ist ach so warum beschäftigt man sich damit der ein Grund warum man sich damit beschäftigt jetzt ich meine die freies war warum beschwert man sich dann so werden sonntags gibt ein Grund warum man sich damit beschäftigen wird der Grund ist dass der eigens von der Xtra nicht mehr die negativen kannten umgehen kann hier klappt das so wenn wir das Ganze noch ein bisschen anders ordnen was wäre eigentlich ursprünglich gemacht haben als die Knoten Listen hatten dann können wir wieder zurück ins erst Implementationen Knoten statt kannten speichern und kriegt das wäre dann da
dann wieder raus ist alles also nicht so und so viel anders es bleibt dabei einmal ist der Aufwand und das ist das Beste was man weiß bis momentan wenn negative Kantenlängen erlaubt sind aber noch keine negativen Zirkel wer noch negative Züge nochmal zu besprechen haben so was wir haben
ist wenn man fort sie haben den man vor Ort du in weiß ich nicht mehr G 2 entweder kennen gelernt wie hier als ein Algorithmus für kürzeste Wege von einem Quoten so einen anderen oder zum Beispiel bei mir kennen gelernt für Europäer ist also alle da wir wollen eine Matrix haben von dem zugenommen so jeden Knoten denn Distanz hat denn beide Problemstellungen prall beide Problem Bayern kennen Sie bei aus der geht so ich weiß nicht was Sie da jetzt jeweils kennen gelernt haben es ist was ich woran ich das aufgezogen haben wir als Europäer ist das letztendlich ja das gleiche ist nur dass man ihn nicht von einem Knoten ausgeht sondern Sie wissen dass von der Mann hat noch Matrix unter wenn die werden ab gerettet aber hierfür gibt es auch das ist das was was hier so ein bisschen im Beweis steckt die invariante ist was jetzt diesen einmal war das also diskutiert haben nach sonst nach Sonne zu verschütten nach K Schritten ist das die Länge eines kürzesten Weges mit maximal K kannten so wir gegen das Beispiel jetzt hier nicht weiter durch das können Sie verwenden um sich das noch mal klar zu machen gut dann was sagt dass wir diese nur testen wir den Pitbull das mal den komplett über Einzeltermine ich schon warum es wird doch
immer ach so inkompatibel kann er
das bedeutet jetzt nicht das habe ich mich jetzt verlesen das bedeutet nicht dass ein Knoten der Distanz Label dieses Knotens und der und der Pi Pointer miteinander inkompatibel sind so was bedeutet das für verschiedene Knoten ist uns lieber das die Optimalität Bedingungen bis zum Ende für keine einzige kannte erfüllt sein muss so wie hier das
hat mich immer vorbereiten einiges an Zeit gekostet bis ich dann endlich vom Herrn stelle den Forumseintrag dazu gelesen habe dir die Sache dann klar gemacht hat was hier passiert ist Folgendes wir die Variante das ist ohne heuristische Beschleunigungstechnik das bedeutet nicht die die asymptotische Komplexität wird besser dadurch es bleibt bei dem n x n aber potenziell in der Praxis aus die mögliche Anzahl der der Schritte die die notwendig sind kann damit drastisch reduziert werden es geht um die Problematik bei was ist jetzt hier die Referenz ist meine mal ganz ganz genau nachdenken es geht um die Problematik oder man und umgekehrt wir haben sämtliche Knoten nummeriert und die Serienvariante sagt mal gucken welche Reihenfolge zuerst so rum und erst dann da man jeder kannte geht natürlich wieder so herum nach rechts wenn wir die Quoten so in eine Reihenfolge gebracht haben oder sie geht nach links und die Aussage ist dass die Update Schritte immer zuerst von rechts nach links gemacht werden und danach alle von rechts nach links und danach alle abdeckt Schritte von links nach rechts in den einen Pass so ist wo sie mir nochmal vergegenwärtigen was der der genaue Vorteile von dieser Variante war aber ich glaube da muss ich nochmal nachschlagen das habe ich das die Vorbereitung ist es leider ein Schritt etwas zu zu lang muss ich nochmal nachschlagen trage ich dann beim nächsten Mal nach sorry aber das was jetzt hier steht das ist falsch das habe ich wie gesagt ne ganze Weile gekostet ich habe erst mal im Internet recherchiert Variante haben dem wo dieses Inhalte gefunden haben den zufällig bei Google auf diesen besagten Forumseintrag gestoßen wo Hersteller der der Autor dieser Folie dann gemeint hat ja wahrscheinlich stimmt das nicht er muss sich halt korrigieren scheint nicht gemacht worden zu sein gut das zweite
Variante ist folgender wir hatten zu erst mit der viel Fucky also vorne rausnehmen Knoten hinten rein tun der was wir hier machen ist mir etwas anderes regelt das ist die das steht hier wenn ein Knoten schon mal da war in der Liste der wenn schon meinen dass das war dann würde wieder vorne aufgehängt angehängt ansonsten wird der hinten angehängt der Gedanke dahinter ist es stimmt dieses Bild da wieder wenn ich diesen Knoten ja ausgenommen habe und hier abdeckte dann packe ich die Sintflut wieder an den Anfang dass er möglichst bald wieder benutzt wird warum stellen Sie folgende Situation Herr werden wenn in diesem Turnier korrigieren darauf darauf hin diese ganzen diese ganzen Knoten das Tanzen weil wir diesen Knoten betrachtet haben von hier aus korrigierende die jetzt korrigieren wir die weiter weil sie vielleicht als nächstes kommen so wie bisher werden die es nächstes gekommen jetzt komme einem nächsten Pass wieder hier dass wir den runter korrigieren und sie müssen wieder die alle unter korrigieren der Gedanke ist der heuristischer Gedanke also war es lässt sich nicht in einer verbesserte asymptotische Komplexität ummünzen der Gedanke ist der wenn wir diesen Kloten gleich wieder behandeln dann ist die Wahrscheinlichkeit sehr groß dass es mehrere Reduktionen hier gibt und erst später aber diese Knoten weiter hinten in der Clou sind erst später 1 müssen einmal diese Knoten reduziert werden und nicht jedes Mal wenn wenn diese Krone es wird ja wenn wir einfach immer derselben Reihenfolge durchgehen die bisher vorgeschlagen ist immer so dieser Knoten wird reduziert Potenzial durch irgendwelche kannten dann später diese geübt wurden reduziert damit wieder im nächsten passt vielleicht dieser Gruppe reduzierter müssen die wieder reduziert werden und so weiter aufgrund der redet der 10. dann 4 wenn wir das so machen dass der mit größerer Wahrscheinlichkeit bei baldmöglichst wieder noch vor denen weiter behandelt wird und genau das sagt diese Regeln mit den 2 oder genau das versucht diese Regeln mit 2 N zu verwirklichen dann ist die Wahrscheinlichkeit sehr groß dass erstmal mal mehrfach dieser Knoten hier weiterhin reduziert wird bis die einmal dann reduziert werden müssen das ist der der Gedanke hinter dieser heuristischen Beschleunigungstechnik und das was ist hier in tötet das tiefe Kirchen dann genannt wird wir haben also eine die Khieu Decke spricht man sowie aus einige Kyu wo man von beiden Seiten also in diesem Fall vom 1 2 Seiten einfügen von einer Seite löschen aber allgemein spricht er von einer Decke oder die Kilo wenn man von beiden Seiten einfügen löschen kann so wenn man das so macht auf diese Art und Weise hat das vor in der Praxis eine Verbesserung aber in der Theorie sogar eine Verschlimmbesserung an nämlich das ich jetzt hier nicht ausführen wenn
Sie nicht stur von vorne nach hinten durch in die bei viel vor sondern irgendwie auf unkontrollierte Art und Weise von den Wochenenden einfahren an der jeweils einfügen da wenn Sie wenn das so völlig und Sie haben sie kann vorhersehen welche was da passiert aber im sie können natürlich wenn sie sonst haben schrittweise nachrechnen was dort passiert aber es ist also so undurchschaubar was da passiert und da kann es dann durchaus sein dass sich dieses Prinzip gegen sie kehrt wenn Sie wenn Sie den Sinn dummes Beispiel haben und das dann viel viel mehr an Schritten zu tun es als mit die er mit den Algorithmen die wir bisher betrachtet haben ein Beispiel ist es öfters mal gibt Algorithmik praktisch besser als der als die Standardvariante aber theoretisch schlechter ja in Ihrem Kopf warte darauf zu Papier gebracht zu werden bestes Beispiel mitnehmen die Prüfung und wir reden darüber ist das auch so sich zu ihrem Schaden sein wenn wenn wenn das Gespräch von ihrer Seite aus konstruktiv dann ist dann suchen sie nach besuchen Sie einfach in in Google Mail nach dieser Variante das wird bestimmt wo leichten Beispiel zu finden sein ich glaube auch nicht dass es
schwer ist so konstruiert und ich habe und ganze sich sofort aus dem Ärmel schütteln negative Züge das hat mir schon mal das kann man ganz kurz durchgehen das hat mir von vorletzten Termin vielleicht oder oder spätestens letzten Termin wenn wir einen negativen Züge haben wenn es nicht wenn es mindestens einen negativen Zirkel gibt im Grafen also wo die Summe auf ein Züge auf dem die Summe der der der Kantenlängen insgesamt negativ wird dann bedeutet das das hat mir schon mal ich jetzt nur wiederholen ich nur meiner drauf eingehen dann bedeutet das dass auf irgendeinem Züge diese Vorgänge kannten tatsächlich zügeln weil das ist kleiner als das das ist kleiner als das dieses Tanzes kürzer als die geht ist das Gesetz sie und so weiter und so fort können Sie noch mal in den Aufnahmen dann sofern wenn diese Aufnahmen dann endlich mal und eingestellt werden können sie dann wie ich glaube vorletzten Termine nochmal nachschlagen was hat da gesagt hatten so das können wir natürlich n in in Jahre Zeit in der Anzahl der Knoten checken ob es sowas gibt ja wir nehmen uns für jeden Einzelnen Knoten diesen vor diese Vorgänge aber hinterher das sind das heißt dabei dass wir für jeden Toten nur einen einzigen Vorgänger als ihr Vorgänger kannte gibt haben in der von viele kannten diesen Grafen er sehr dünn besetzt und da können Sie natürlich mit tiefen so das aber schon mal ganze Mann angesprochen kann sie mit tiefen Suche sehr schnell herausfinden dass sie da einzige drin haben also sehr schnell heißt bewegen ihrer Zeit wenn wir das nicht immer machen sondern hin und wieder mal nach so und so viele Schritten nach vielleicht nach in vielen Schritten oder nach Inhalte vielen Schritten oder entführte vielen Schritten oder 2 in vielen Schritten egal dann bleibt es in derselben Komplexität natürlich dran die die 1. deutsche Komplexität bleibt dieselbe wenn man das nicht jedes nach jedem Update Schritt machen sondern nur alle so und so viel in Male oder alternativ gebrochen gar nichts und 4 einen 1 abzu- frickeln mit diesen Pointer Sie können auch unter Umständen die wir können auch stoppen wenn wir wenn CD die längste Kantenlänge ist der der die absolut Verdi Venlo der Betrag der längste Betrag einer Kantenlänge ist und wenn dieser wert kleiner ist als als er wenn wir nehmen an dass dann zwar kleiner ist als in Mali länger dann wissen wir diese Länge dieser wert diese Distanz wird muss von einem negativen zu bekommen sollen irgendwann passiert das ja weil so lange es dann wenn es ein negativer Titel ist dann bricht Algorithmus dass man nicht von sich selber ab der durch sich selbst aber die Optimalität Bedingungen nicht nicht hinzukriegen sind also die Abbruchbedingung für den Algorithmus nie und das heißt er suche CL sucht sich immer wieder entlang der negativen Zügel wird immer kleinere immer kleinere Distanz werde und irgendwann werden diese Werte weil das im unendlichen im negativen aus aufhören würde wenn dieses das würde kleiner als dieser Wert minus 1 x 10 und in dem Moment wissen wir können wir auf an weil diese Distanz werden in meine Zelle garantiert durch einen negativen Zügen entstanden sein kann ja div die Frau ok die Frage warum ich immer zivile kleinsten sie aber auf dem zügiger negative und positive könnten sie sind auf jeden Fall auf der sicheren Seite wenn sie diesen werden es einmal sehr nehmen er also also immer nur die negativen wenn nur die negativen kannten jenes C einfließen lassen sein die Klassiker des wie das was Teil kann das 5 Tausend Jahre der die die ich glaube das müssen wir noch mal noch mal am Rande des jetzt müssen so kompliziert mehr okay das ist dann der wenn
man fort Algorithmus im Prinzip genau das was wir bisher gesagt haben und wenn wir einmal durch oder oder das ist noch immer eine andere Möglichkeit wie wir die Zügel finden können das ist noch die Möglichkeit zum ist die wie die bei mir G 2 gehört haben ich das negative Züge finden eingeführt haben noch noch eine Variante nämlich sie für das ganze minus 1 mal durch ja in das heißt also Ende das einzige Reaktion nach der Karte Migration sind die ist ja das wird die Länge eines kürzesten Weges von es zu diesem Knoten mit maximal K kannten am Ende wenn alles und rechten Dingen zugeht ist das jeweils der kürzeste Weg aber wenn Sie noch irgendwo eine nicht eine Verletzung der Thema Vitez Bedingungen haben dann wissen Sie Sie haben einen negativen Zügel gefunden weil eine von dieser kannten eine von einer Kant auf diesen negativen Züge das aber schon mal festgestellt es geht nicht auf das die Optimalität Bedingungen auf die da kannte erfüllt sind wenn wenn die wenn die wenn das ein negativer Züge ist sie ändern sich wenn das sie zum Beispiel vor 1 ist vom 2 dann ist Optimalität spielen würde heißen die vor 2 kleineren gleich V 1 bloß Länge von V 1 noch vor 2 diese Gleichung wenn die Optimalität spielen erfüllt wären würde diese Gleichung diese Ungleichung für das bekannte denken ist gelten es stellen sich vor Sie agieren das alles auf sie haben also jetzt hier die V 3 kleiner gleich die V 2 in bloß c V O 2 vor 3 und so weiter einmal um den Zügel rum bis auch auch diese Karte die wir zuvor 1 führt dazu dann haben Sie jeder wenn sie dass die alle addiert die linken Seiten addieren und die rechten sollten an die für alle für alle diese kann auf den Zügel dann haben sie links und rechts das selbe stehen nämlich die Summe der Gesamtwert aller Knoten können Sie wegstreichen dann steht der hinten links noch ein bleibender 0 bricht und bleibt die Summe der Kantenlängen übrig 0 kleiner gleich Summe der Kantenlängen das geht bei einem negativen zu König also völlig unmöglich auch negativen Züge das alle kannten die Optimalität Bedingungen erfüllen und das da brauche man bloß zu testen ob noch irgendwo die er optimal mit SPD nicht erfüllt ist wenn Jahres negative Züge gefunden weil wenn alles mit rechten Dingen zugehen würde wenn es keine negativen Züge gäbe wären wir nach 1 1 Ration fertig überlegen ob gemaltes Bedingungen wenn es hingegen nicht mit rechten Dingen zugeht wenn es da einige Defizite gibt dann macht sich mindestens eine dieser negativen Züge auf diese Art und Weise auf mindestens einer dieser Kanten bemerkbar und dann haben wir zumindest erstmal entdeckt dass ist negativen Züge gibt und mit dieser Strategie die Nachfolger die dann die die letzten kannten den Grafen der letzten Karten zu durchsuchen nach nach zügeln wir auch tatsächlich so negativen Syrien Hand bekommen
so Alters können wir relativ schnell durchgehen wir könnten zum Beispiel der extra von jedem Staat Noten aus Los laufen lassen hätten natürlich auch Old ist sind wie wir so eine komische Distanz so komische also durch die Komplexität raus wenn man vor Ort können wir und machen das kennen Sie aus der G 2 Uhr denke ich da haben Sie jetzt gleich die Matrix ist dann hat man ein Abwasch oder man könnte natürlich auch so wir mit 4 wenn man fort für einen Staat Noten eingeführtes könnte man natürlich dann auch für Einzelstaaten Noten einmal durchführen aber für die Laufzeit ist es das selbe
so was ist dieser trivial Algorithmus gut diese triviale Algorithmus ist im Grunde wir initialisieren die Matrix wie immer mit plus unendlich für alle Knoten beziehungsweise Distanz 0 für ein Klon selber und setze schon die Kanten also in sehr wenn man schon das Paar als Ort der schon das Spaß haben die Matrix Sie sehen jetzt Distanz von Ihnen auch J nicht mehr Distanz mit nur einem Index von erst zum Stoff vom Staat und so im andern wurden sondern wir haben hier die eine Matrix von Distanz werden das Problem ist sie die alle mit auf der Diagonalen mit neue jeder Knoten hat es dann das 0 zu sich selber am Anfang es keine negativen Züge geht hatte auch am Ende das Ganze nur zu sich selbst das negative Züge gibt gibt es mindestens einen Knoten der Distanz kleiner 0 hat am Ende es Algorithmus also auf der die Kanaren negative Zahl und initialisieren auffälligen angesagt 0 1 Kantenlängen führen wir einen da muss keine keine geht mit unendlich und dann machen wir solange die Korrektur bis es keine Gelegenheit zum Kultur machen mehr gibt okay hier noch
noch mal das selbe immer wenn wir wenn die obere Schranken haben für die für die für die kalten Winde schon gern im für die Kantenlänge also dem maximal wird sämtlicher Kantenlängen dann kann höchstens einmal C der höchste Wert sein überhaupt vorkommen kann die Länge eines Weges ein wie keine höchstens 1 1 könnten haben kann jeder kann begann höchstens länger Großzeh haben also ist die Länge eines Weges höchstens einmal C Groß oder müssen zumindest einmal Zicklein dazwischen sind alle Kantenlängen das heißt also wenn die wenn sämtliche kann man integral sind dann heißt es dass man es um einen Zähler immer bei jedem Update die Kantenlänge reduziert wird sie kann frühestens von Plus als sie in einer Schritten oder in größeren sprühen bis minus 1 x C reduziert werden und daher kommt es dass wir in höchstens zweimal x C er Schritten für ihn als Enkel Fred 1 ist das ja man Quadrates tanzen wir können höchstens zweimal in x 10 Schritten er habe dieses Tanz von einem zum anderen richtig berechnet so er wird war schön das würde ich habe ich mir angesehen hier das ich so einführen wie es auch einige die 2 selber eingeführt habe nämlich über den Variante ich sage das vielleicht ganz gut oder was wir hier haben wir viel etwa Scholle es ist eine Nummerierung der Knoten von V 1 vor 2 ich mach das mal doch vor 3 Gruppen vorkam minus 1 in der Mitte Volker Volker plus 1 in der Mitte sie sehen wir gucken mal eine Situation in der Mitte ein irgendwie durchnummeriert und die invariante bei Floyd war schon ist das nach K Schritten jeder wie jeder Distanz wert die Länge eines kürzesten Pfades ist von diesen Staat Noten hier diesen Ort erst also von irdenen beliebigen starten und zu einem beliebigen zielten wurden ändern sich bei der man vor Ort ist invariante nach K Schritten ist es die Länge eines kürzesten Wege sind maximal K kannten das heißt da wachsen die Pfade schrittweise sozusagen der in der länger im Sinne von von kannten zwar hier ist die werde die nach K Schritten sind sämtliche inneren Knoten hier aus der Menge V 1 bis vor ok also aus diesem aus diesem Bereich hier am Ende nach allen Iterationen haben Sie sich im ganzen Bereich das heißt jeder beliebige Fahrt ist möglich und damit haben Sie dann tatsächlich wieder die Länge eines beliebigen kürzesten Pfades ganz am Ende bekommen und diese Formulierung wie sie jetzt hier als in Bayern zu habe denke ich er legt sofort macht sofort klar wie eine Iteration aussehen muss nämlich für jedes ist schauen wir uns hier gibt es eine Möglichkeit das reicht nicht immer vielleicht nochmal neu nun so in der in der Karten Iterationen da haben wir von einem irgendwelchen Staaten wurden hierzu irgendein zieht wurden hier haben wir einen Weg aktuelle dessen innere Knoten alle aus v 1 bis v ok minus 1 sind ja das ist seit dem Variante also am Anfang der KD 3 zu 1 dass das Bild irgendwo außerhalb den wir haben 1 weg berechnet hier und ein Weg hier die dieselbe Eigenschaft haben nämlich alle in einen Knoten aus v 1 bis v ok minus 1 ja das geht ja schließlich mit diesem Element Ausweises vorkamen seines Geldes nicht nur für dieses Paar Staaten wurden sieht nur Sommer für jedes Paar also auch Infokarte ziehe Knoten wie hier oder der Staat notwendig hier ist so das heißt also alles was wir in diese Iterationen machen müssen für dieses Paar und starten sie Knoten ist wir gucken uns an diesen plus diesen wird was gibt das und vergleichen das mit diesen wird und wenn das hier diese Summe kleiner ist als diese wird dann denken wir ab entsprechend dann wird für diese Länge plus diese Länge unsere neue Weg länger in das heißt also wir prüfen auf ist ein der vom bringt uns VK etwas er ist ein Facharzt über fokal läuft und wir wissen welches der beste ist das wir auch vorher schon diese beiden gerechnet haben ist der Pfad über fokal läuft besser als der Vater nicht über fokal läuft sondern nur über vor 1 fokal minus 1 ohne Fokker wenn ja wenn er besser ist dann immer den nicht bleiben aber dem alten das wird war ich denke das ist recht intuitiv anschaulich wie das funktioniert und Sie sehen wieder wenn man von den Variante ausgeht das versuche ich den Studierenden im in Nägeli 2 zu erklären wenn man von der invariant ausgeht wird alles plötzlich ist das ist keine Schikane des Dozenten K und auch keine keine Liebhaberei des Dozenten die unbedingt die Studierenden reindrücken würde sondern es wird plötzlich alles wenn man von dort aus geht es sehr viel einfacher und klarer und lässt sich ohne grosses ohne großen Lernaufwand auch gut im Kopf behalten will ich mir ein aber ich das den Studierenden die die die 2 wirklich verklickern soll das habe ich noch nicht verstanden da bin ich auf Anregungen sehr dankbar was kann man tun und damit die Studierenden der GD 2 ich will die kleine Minderheit dies ganz gut gepackt hat sondern die große Mehrheit dass Sie diesen einfachen Gedanken mit dem man sicher das Lernen leichter macht und und den oder nur verbessern kann diesen einfachen Gedanken dann tatsächlich zu verinnerlichen und zu werden so das ist das
das eben gesagt haben was ich immer noch mal gezeichnet habe und ich nochmal durch zu gehen
das macht jetzt eigentlich wenig sehen dass er nehmen aus dem Prüfungsstoff raus diese Sache
rekursiv und Fall Barschel ist noch mal was ich eben gesagt habe können Sie nochmals sich diese Folie hinterher und nochmal gegenchecken dass das was ich hier eine Tafel gemacht habe und mündlich erzählt habe dass das dem entspricht hoffentlich was hier steht so warum ist
das es besiegen noch n hoch 3 wenn man fort war er noch 4 Jahre weil wir in jeder einzelnen Iteration für jedes Paar aus Staat und Zielquoten nur 2 Längen anders vergleiche nahm die für dieses Paar berechnet worden ist und die Länge die sich aus diesen beiden fahren ergibt ja jeder Einzelisolation ist für jeden einzelnen Paar eine konstante Aufwand dar was ergibt insgesamt in noch 3 EL Integration im Quadrat Paare so
ach so man sollte vielleicht auch Dozenten von Algorithmen Veranstaltungen sagen wie einfach das alles wird wenn man alles immer Variante auf aufhängen so dass man das als man Matrix oder speichern kann das haben Sie mir geht's so gesehen das ist noch mal der Punkt den ich mündlich angesprochen hatte vorhin sie können daher nie das wollen war im im Zusammenhang mit der man vor sie kann daher die negativen Zahl Zyklen auf der regionale ablesen alle kann die genau die Knoten bei den auf der regionalen wird kleiner 0 ist genau diesen einen negativen Züge dran diesen alternativen Scheck haben wir eben auch schon mal gesehen das ist auch nichts Neues müssen uns ja guter sollten uns ansehen transitive ist ein wichtiges Thema der vergessen mal das ist jetzt das Tanzen gibt ja das ist das um größte Wege gibt was zuweilen sehr wichtig ist ist die Information zu berechnen zwischen welchen 2 Knoten das überhaupt eine Kante gibt eine Tür und ich mir keine so in Fahrt ja und das kann man das nennt man die transitive Hülle also Sie haben das sind die echten kannten vielleicht ein paar reichte könnten da gab es natürlich viel größer und es gibt einen Pfad da bilden sie das und die transitiven kannten diese einbinden das sind die Pfade also haben wir noch das und so ja wenn Sie immer transitiven Schritt machen 2 Karten hernehmen und über Brücken wenn das oft genug machen dann haben sie eine Kante drehen für jedes Paar von Knowhow wo sie wo sie eigentlich nur nun Pfad im ursprünglichen auf und das die transitive Hülle oder so transitive Abschluss eines Grafen und was hier steht es nicht aus als die Bemerkung mit den Gründen die wir jetzt hier die eigentlich egal mit welchen mit den Algorithmen die wir jetzt hier hatten können Sie immer sie nehmen einfach Kantenlänge 1 also neutrale kann man können Sie immer die transitive berechnen überall da wo ein endlich wird am Ende der Matrix steht da gibt es eine solche kannte und der werde aber steht zu machen für diese kann der wäre dann 4 wenn sie kann man an einzusetzen so das
ist also haben eine sehr interessante Sache die wollen wir nicht auslassen hatten diesen Ähnlichkeit mit dem Thema zielgerichtete Suche und erstellen Algorithmus dieser beim letzten Mal betrachtet haben da geht es genau um solche kann auch Knoten Werte auch die Idee ist folgende sie
erinnern sich wenn wir solche Knoten Werte haben und wer ändern die Kanten nach so einem Schema ab dass die neue Kantenlänge gleich der alten Kantenlänge plus dem ein Knoten wird vom Staat Noten Minus im Club mit vor er vom Ziel wurden ist dann sind wir am kürzesten Wegen kürzeste überführt die Weglänge ändern sich natürlich aber das Verhältnis zwischen 2 wegen vom selben Staaten und Unsummen sie nun bleibt das selber wenn einer von den beiden vorher kürzer war mit den ursprünglichen C werden so auch mit den sich durch werden kürzer das liegt einfach daran dass diese F Werte sie ernähren sich Sieg oder sie kannst dann auch noch mal wenn Sie wollen nachschlagen für jeden für jeden für den internen Knoten des Vaters kommt der erfährt einmal positiv einmal negativ vor in der Summe der Kantenlängen gemäß Zielstrich hitzig weg das bleibt übrig die bei diesen ganzen dieser den weggeben der der erfährt vom Staat Noten oder wir vom 10. und diese natürlich für alle Pfade vom selben staatenlosen selben sie Knud identisch also ändert sich nichts wenn wir das so umsetzen nur was für Werte nehmen wir als es
zur die Idee ist wir machen einmal wir machen einmal ein Bellmann vor Ort der ein bisschen anders ist auf einen etwas anderen Grafen und zwar belichteten skizzieren wie diese etwas andere Graf aussieht wobei es geht sogar ich kenne eigentlich die Variante wie das im selben könne Grafen mit einem beliebigen statt Noten gibt aber ich halte mich jetzt hier an die Folie und für einen neuen künstlichen stark Noten zu so wir haben jetzt das ist wie üblich unser Graf nicht in der Menge des für die Grafik gerichteten darf nicht in dieses immer und wir haben einen künstlichen neuen Start Noten dieser beim Europäers eigentlich da mal keine einzelne Staaten und aber jetzt finde eine rein und jeweils mit Längen 0 7 bekannte von diesem Staat wurden zu jedem echten Knoten in jeweils Länge 0 jetzt führen wir wenn man fort einmal aus bei der die Bezüge drin haben dann sind Sie natürlich im ursprünglichen die Grafen drin klar dann wie machen wir dann verloren habe jetzt setzen wir dieser F Werte die sich jetzt magische Weise zu H werden gemausert haben dass dasselbe was eben auf der letzten wurde als er vertreiben setzen wir als die berechnete Distanz her und der Grund dafür warum wir das machen wir setzen jetzt die die Kantenlänge entsprechend sowie bis so wie wir im gesagt haben entsprechend um der Grund warum wir das machen steht hier wenn wir mit diesen wenn wir mit diesen werden mit diesem so berechneten Werten diese er die Kosten der die CD die Länge modifizieren dann sind diese in eine große gleich 0 warum sind die alle größer gleich 0 ja weil setzen wir einen C Strich von UV wir wollen zeigen dass das größer gleich 0 ist das ist normal CDU-Frau das denke reich an größer gleich 0 zu sein plus der in diesem künstlichen Grafen berechnete Distanz wert es mit der der bezeichnet es was ist erst nach minus der davon S nach Frau so und die Optimalität Bedingung besagt gerade das ist die kürzeste Weglänge von es nach Frau natürlich nicht kürzer sein natürlich nicht größer sein kann als die Küste von erst nach plus dem Weg bis der kann von und nach V ja das der kürzeste Weg links ist hier die kürzeste Weg von 1. Frau und rechts ist die Länge von irgendeinem einen gewissen Weg von es war von dem ich küsse sowie kann es noch Plus kann davon und nach V so und dann steht aber schon da ich setze diese Gleichung 1 diese ungleich Entschuldigung und dann steht es schon da und jetzt wenn die Karten in größer gleich 0 ist Treffer können Sie wo wo alle weiteren für alle weiteren Staaten da extra für auf diesen auf diesem modifizierten Kantenlänge kriegen die richtigen kürzesten Wege raus sind nicht mehr die richtigen Kantenlängen er nicht mehr die Hinfahrt Längen also dieses das werde ständig aber die können Sie dann das aber bei vorletzten mal gesehen können sie dann wieder zurück rächen indem sie diese der der Werte vom Staat und vom Zielquoten dass eine abziehen ganz andere drauf addieren und verdienen auch die richtige Distanz wird er aber schon mal betrachtet letztes oder wohl letztes Mal warum ich noch meine zu betrachten das ist der Grund des warum wir das das ist und das ist das interessante war sie dann schon so Algorithmus Finder was Sie machen ist einmal anstatt wenn man fort mit jedem Noten einmal sie könne nicht einfach mehr geben da extra mit ihm starben ein Mann und sehr negative kann man da extra funktioniert nicht leider immer wenn man vor Ort auf dem des Grafen auf der Basis kriegen Sie da kriegen Sie modifizierte Kantenlänge größer gleich 0 sind können jetzt für jeden Staat Notentext Rauch und viel schneller als alles andere Deix nix und haben die richtigen Wege müssen nur die die die Idee Tanzen entsprechen attestieren wir schon mal dann dass man gesehen haben das ist mir das ein praktischer trägt dabei nicht dass man also im Prinzip schon da extra wir verwenden kann von dem Staat wurden einmal um Olpe das zu berechnen auch wenn die kann den ursprünglich negativ sind die modifizierten Kantenlängen also teilweise negativ sein können modifizierten kann man so nicht negativ so das ergibt dann natürlich
entsprechend viel bessere Zeit Komplexität je nachdem was Sie da einsetzen wo nicht weiter zu diskutieren und auf essbar Squaws das heißt wo die könnten Zahl jetzt nicht viel Gras größer ist als die Knoten Zahl ich glaube ich hatte schon mal ganz zu Anfang gesagt wenn sie beispielsweise planaren Grafen haben ein Grafen denn sie kreuzungsfrei in die in einbetten können so zum Beispiel ich rufe das ist die kannten Zahl höchstens 3 minus 6 die Knoten Ende Knoten zwar betrachten wir hier und heute jetzt nicht warum das so ist das ist nur ein Beispiel dafür ein geografisches weil zum Beispiel Autobahnnetz und so weiter das ist kein dreimal traf zum hat Brücken und Tunnel aber das ist nicht so viele das heißt also es bleibt noch dabei dass die das die erkannten Sal in Lehner eine größere Knoten Zahl es auch bei einem Autobahn Netzwerk mit der sehr kleinen konstante doch vor das heißt also auf Autobahn Netzwerken wir diese Variante für Old per falls man und per Ausschusses Pass auf Autobahnen 2. machen will wer diese Variante dann schneller als wird und die asymptotische Komplexität so endlich vorbei mit kürzesten Wegen wir können die restliche Zeit
nutzen um in das nächste
Thema einzusteigen Netzwerkschlüssel
kennen Sie das aus der GT 2 aus Kindergartenjahr okay das Bild vielleicht aber aber nicht unbedingt das Thema haben Sie immer Flüsse in der die so gesehen wer nicht okay decken wir vieles auch wieder noch schnell machen wolle er die Dinge dieser sowie zu kennen sie
wissen was wir die wir haben es immer mit gerichteten Grafen zu tun wir haben den Kosten März auf jeder kannte haben eine untere Schranke 5 los wird auf jeder könnte eine obere Schranke auf dem Fluss wird jeder kannte viele Flüsse die der kannte wir haben einen Balance wert für jeden Knoten ich weiß nicht ob so allgemein eingeführt haben
mit Balance werden B oder etwas gut da machen es vielleicht nicht ganz so schnell so was ist die Situation wir haben hier eine Situation die wahrscheinlich müssen allgemein als wie sie sie wirklich so kennen gelernt haben wir haben einen gerichteten Grafen wenige D 2 wir wissen worauf es hinauslaufen soll es Flüsse die die Kanten sind in die Rohre oder Kabel oder Informationskanäle oder was auch immer und da sollen Einheiten durch geschickt werden im Allgemeinen ist eine obere Kapazität man kann nicht zu viel durch schicken das sind die aber Bauens OJ J man kann aber auch durchaus in manchen an ist es sinnvoll auch eine untere Schranke zu haben das heißt dass man mindestens L I Ort Fluss Einheiten durch schicken muss ich durch jedes der der einzelnen der einzelne kannten die Rohre sind oder so etwas ich habe letztens gewesen durch die ganzen Wasser Sparmaßnahmen mehr Toilette mit nur Überspielung Grund und du Duschkopf mit mit reduziertem Ausstoß und so weiter gibt es teilweise wohl schon Gemeinden wo die wo die er wo die Wasser Versorgungswerte Werke durch die durch die Abwasser Kanäle noch zu sich Frischwasser durch period müssen damit es da halt nicht nicht irgendwelche Probleme gibt mit dem fehlenden oder Wasser Wasser damit habe man nicht gerechnet als man die Kanäle gebaut hat oder welchen Techem Gründe ist es sehr vorteilhaft dass dann eine gewisse Mindestmenge durchfließt das wäre ein Fall wo wir solche und und Schranken für den für den Fluss haben das mindestens so viel durchfließen aus deren Kosten das heißt pro Fluss Einheit die wir durch schicken kostet und die dem wir durch die Karte von Ihnen ja durch schicken comma Co sowie Fluss Einheit C I J in Euro oder was auch immer 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 die 2 betrachtet es gibt eine Quelle von der Frist aller raus und es gibt eine senken die wies einflussreichen wie Rache jetzt etwas allgemeiner wir sagen es gibt quält Knoten zu plane also die was bereitstellen und zwar was die bereitstellen ist pro Sekunde oder wie auch immer B von V Einheiten die werden da rein gebrummt ins Netz von diesen Knoten aus in seiner von ihnen ausgehenden Kanten und von da aus müssen sie sein und wie weiter für transportiert werden dann gibt es andere kannten diesen senken die haben bedarf da wird was reingepumpt also das Ganze hat natürlich jetzt durch die alle erneuerbaren Energien eine eine Tat an Aktualität gewonnen das ist das ist da das ist Tagwerk Knoten gibt die produzierten Strom egal ob man ihn braucht aber der muss dann irgendwo abge- da muss irgendwo weitergetrieben werden und auf der anderen Seite gibt es 10 Knoten die unter Umständen viel weniger brauchen als das was rein also je nach dem Beitrag bei prallem Sonnenschein im Sommer ist das was rein reinkommt 1 Quelle Quoten größer als das was abgenommen wird in Deutschland ist es ja nicht so weitverbreitet Klimaanlagen zu haben sonst wäre es kein Problem den ganzen Strom abzunehmen während wären im tiefsten Winter wo die ganzen Solarzellen auf den auf den Dächern alle nicht nicht viel bringen dafür darf jetzt dann wieder da mussten von woanders her der Herr des Play herkommen und manche benutzt das sind einfach nur Zwischenstationen die haben den die wird dem Balance wird 0 das heißt also genau das was reingeht Klobrille pro Zeiteinheit ist auch das was raus gehen soll pro Zeiteinheit wir immer von einem stabilen Zustand das heißt also von Zeiteinheit zurzeit Zeiteinheit ändert sich der Fluss wird auf jeder kannte nicht die Variante dass dieser Zustand ist stabil ist wurde auch intensiven Algorithmik untersucht auf Basis von dem was wir hier betrachten ist natürlich viel komplizierter und wäre er Inhalt einer weiterführenden anschauen Seminars so wir wollen keine Parallelen kannten oder Schleifen haben die würden endlich die auch nicht weiter stören aber gut für dich haben wollen und ich haben die Stimme ist ja gut über das natürliche Umstände bei den kannten wir einfach Indizien die keiner von ihnen ja das CI hat immer 2 parallele kann haben und in auch wirklich und bei dessen das jetzt aber das wird uns das eigentlich
mit nicht stören so dass man KostO Problem das haben Sie wahrscheinlich nicht mehr geht so gesehen ist das allgemeine Problem wir wollen einen Fluss wir haben in den kannten also die kann sie wieder Rohre Kommunikationskanäle oder was auch immer wir wollen einen Fluss haben ein eigentlich einen statischen Fluss der sich von Zeit zu Zeit einer sich ändert der kostet uns natürlich etwas in diese Kosten wollen wir minimieren jeder Fluss Einheit die wir durch die kannte ich er er die schikaniert schicken kostet und zehrt Einheiten 1 Euro vielleicht und wenn der XI hat Einheiten von Ihnen auch hier durch die Kandidat schicken koste ist dementsprechend sichert mal XJ Einheiten und das über alle kannten aufsummiert ist die du sind die Gesamtkosten die uns das alles kostet so was müssen wir dabei beachten wir müssen die Balance erleben Gluten beachten und zwar das ist etwas komplizierter ist Jan Werner CSU Dreiteilung gehabt Knoten mit B größer 0 mit B kleiner 0 mit Bild gleich noch die einen waren die die die die Quellen die was rein geschickt haben ins Netz die einen die was rausgezogen haben und die 3. wusste immer nur der Fluss durch geht 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 und rangiert man Not ist oder Enten oder was raus aus dem Netz dass der Gleise und rangiert Not ist ja wir haben am kleinen Knoten da gehen und welche kann nur ein und irgendwelche kannten gehen raus und der bringt von hier das ist mir Quelle von da kommt was hier nach rechts über diese könnten raus aber es kann trotzdem sein dass noch hier Fluss reingeht der dann auch hier raus das fließen muss oder umgekehrt deshalb vor vereinheitlichen wir das was wir sagen die Summe der aus fließenden Fluss Einheiten minus der Summe der einen fließenden Fluss einhalten ist gleich dieser Gesamt Bahn aus ja dann dann haben wir in dieser Formulierung ist die Möglichkeit drin das auch selbst in einem Quelle Knoten noch noch hinterrücks Fluss einfließen kann und und das aus einem senden Noten noch in der Rückfluss rausfließen kann so und das Ganze noch unter der Bedingung dass der Fluss wird auf jeder kannte zwischen unteren und oberen Schranke ist das ist das Problem mit dem wir uns zuvorderst beschäftigen werden für jede Kante haben wir also ein Wert ja mal so was wie ein Vektor dessen Komponenten mit dem Kandis jetzt sind sie können sich das vorstellen die keinen sind durchnummeriert und das sind die das in die Indizes des Vektors so so kann man sich also Vektor vorstellen und wie gesagt eine statische Fluss statischen klammern weil wenn man mal vor Einfluss redet meint man in einem allgemeinen statischen Fluss wenn man eine Stadt im Fluss meint dann sollte dann will man meist von einem dynamischen Fluss Überraschung okay das 1. sind die Fluss Haltungsbedingungen das 2. die Kapazitäts- Beschränkungen nach oben nach unten so jetzt noch eine kleine mathematische Spielerei am Rande wenn wir eine bestimmte Art von Matrix hernehmen Diplom kann Inzidenz Matrix was ist das das haben Sie mit Sicherheit einer G 2 gesehen das muss ich mir überlegen wo sind jetzt am besten die Knoten wo sind die Kanten das ist eine große Matrix wir haben wenn Sie so durchgehen gehen sie aller 1 1 eines Knotens durch das heißt also hier haben Sie die Karten ja bekannte VW eine Spalte für eine Kante VW wir unser und wohnt Knoten V und ein Kühlung Knoten W also je eine Zeile für jeden Knoten und an dieser Stelle steht eine 1 zu 1 plus 1 an dieser Stelle eine minus 1 und ansonsten steht über eine neue in dieser Spalte und das machen sie mit ihrer Spalte das haben Sie mit Sicherheit schon mal gesehen so das ist diese Matrix wie sie hier genannt groß N so und was hier steht ist wenn Sie jetzt das Multiplizieren mit dem diesen besagten Vektor wo irgendwo mittendrin jetzt ESX VW steht ja was steht denn der daher was steht an der Stelle v und was steht an der Stelle W hier sie gehen hier ganz normale Matrix weckt aber Delegation sie gehen hier die Sparte die Zeile durch ein Matrix und denen Vektor durch und für jede kannte die raus geht aus diesen Knoten wir addieren Sie das mit plus 1 auf Mittwoch also positiv und für jede kannte die raus geht die eingeht ich mach mal genommen könnte UV hier steht eine minus 1 an dieser Stelle für die Karte diesem Klon reingeht addieren Sie das demnächst wird auch mit dem man aus das heißt sie haben genau das was hier von Gluten V steht wenn normale nur die Biker Matrixmultiplikation machen also Sekte Modifikation es ist exakt diese Gleichung einfach in für Küster Mark durch Schreibweise hier also halt hier muss sich das genau ein Schreiben hier steht jetzt B von Frau und hier steht das Bild von W die dieser einzelnen Produkte jetzt ja fast immer 0 mehr ist es nicht also als für die Kanten die nicht vorkommen ist 0 die nicht mit Frau zu tun haben für die kann vorausgehen das ist hier in dieser Zahl ein Eintrag Fluss 1 für die kann den Foreign es ist der 2. Eintrag minus 1 und das heißt für alle die die ihrer die rausgehen wird der entsprechende X wird positiven so gezielt für alle die reingehen wir diese entsprechend wird negativ aber gezielt auf der rechten Seite setzen wir dann die Balance wird an und das reduziert diese diesen Satz von Gleichungen für jeden Knoten eine Gleichung kritisiert dass auf diese Marke Schreibweise NX gleich E kleine mathematische Spielerei am Rande Auto also sich weiter dass sich das immer damals Spielereien eine dafür würde mir bestimmt das weit an die Gurgel gehen es kommt keine Frage von
wegen was lassen Sie sich das kosten oder so so eine so ein Spezialfall der war durch das von einigen praktischen Interesses ist der Fall einer Strömung Zirkel welche nämlich dass sämtliche Knoten kein Chat mit 9 Cent also für jeden 1 sind wurden geht die Summe rein gleicht das Sommerhaus beachten Sie dass der 0 Fluss nicht immer zulässig ist in der mehr untere Schranken ja wir haben hier untere Schranken
und wenn diese untere Schranke größer 0 ist die kann auch kleineren oder gleich 0 sein wenn diese größer 0 ist ist der 0 Fluss nicht zulässig der Fluss der über jede einzelne kannte ab 0 Einheiten fließen ist so damit das
Ganze nur funktioniert macht man sich mal klar muss man sich mal klar machen das ist da die Summe sämtlicher Balance Landwirte 0 sein müssen warum Form bis die Summe sämtlicher weil 4. 0 sein schauen Sie sich diese Gleichung hier an
noch mal und bedenken Sie dass diese Gleichung für jeden nur einmal vorkommt ja stellen sich wegen Gluten diese Gleichung jeweils hingeschrieben und Annan dar so wenn Sie wenn Sie diese Gleichung aller addieren längst alle linken sollten addieren und an rechten Seite hat was kriegen Sie links raus ja Sie haben diese Gleichung für jeden Knoten so und donnernder schön geschrieben und addieren alle linken Seiten in Summe XJ mir somit so die unter den die rechten Seiten was kriegen sie längst raus 0 warum er der Umsatz ist es vielleicht eine etwas steile Begründung von nichts kommt nichts der die das Waldemar das Argument was für den ich gleich ein sich ist immer so dass es durch rechnen müssen ist einfach die jeder einzelne kann der komm beim beiseite bei ihrem stark Noten hier vor und bei Ihnen 10 Knoten hier vor das heißt der X wird die leisten kann bekommt einfach einmal positiv und einmaliger diese diese Summe vor hitzig weg wenn linke Hand die Summe 1 0 ist da muss natürlich damit die Gleichung aufgehen recht auch alles 0 sein und nichts anderes wird hier
behauptet dann das ganze ob es muss die Summe der Balance Balancen 0 sein das wissen Sie von dem Thema erneuerbare Energien also da wird natürlich dafür gesorgt dass die Balance im einen wie geplant werde man 0 sind weil und welche senken gibt dass das ganze irgendwo keine Ahnung abgeleitet wird irgendwohin wo es dann wenigstens keinen Schaden anrichten aber auch keinen Nutzen hat wobei ich habe jetzt gerade ist es in den den in den Online Medien drin einen Vorschlag von der RWE die guten alten Nachtspeicheröfen wieder ja wiederzuverwenden nämlich da er zu Zeiten mit einer etwas anderen Automatik ich weiß nicht ob Sie das präsent Nachtspeicheröfen kennen es geht im Prinzip vom E-Werk 2 Arten von Strom einen teuren und einen billigen den billigen kriegt man nur wenn man bestimmtes Gerät hat wie Nachtspeicherofen würden eben billiger abgerechnet billiger Nachtstrom eben und wenn etwas anderen Vorrichtung mit 1 alle anderen Automatik die der Nachtspeicherofen immer dann an wenn der Strom besonders billig ist weil eben gerade viel eingespeist wird uns damit kann man zum ein Stück weiter das Speicherproblem lösen dass man ja hat ja das mit den erneuerbaren Energien wohin mit dem Strom dann wenn man viel braucht kriegt man nicht viel dazwischen müsse man speichern und die Idee dass die zentral zu speichern mit noch Sprecher und mal gucken sie haben das durchgerechnet ist also die sind der Meinung dass das funktionieren gut
hin und wieder gehen wir mehr schwinge das von vorne rein so ein dass die dass sämtliche Werte Kosten Kapazitäten und des Werte alle ganzzahlig sind wir hatten schon mal dass es keine wirkliche Einschränkung der Allgemeinheit ist ja sie können problemlos wenn wenn sie keine ganzzahligen Werte haben wenn sie wenn sie Nachkommastellen haben können Sie beispielsweise das wir auf auf der auf ganzer Tausend tausendste Runden und haben da keine großen Rundungsfehler dran gemacht also wenn sie es nur ausreichen feingranulare machen können Sie den Rundungsfehler natürlich beliebig reduzieren und wenn sie es auftaucht kann so 1007 reduzieren mehr damit alles um den Faktor 1000 multipliziert und haben das ganz es ist also wirklich und keine Einschränkung ja aber manchmal möchte man auch sie keines von den Christen wegen manchmal möchte man auch unendliche nicht unendliche Weg längs und und die Kapazität haben wenn es also keinen gibt auf die man über die man beliebig viele rüber schicken kann die keine die keine Einschränkung haben er und das ist das sei diese bemerken Sie was das eigentlich auch schon für Küsse wegen natürlich gilt aber hier vielleicht noch ein bisschen stärker zuschlägt haben wenn Sie werter addieren dann kann es natürlich immer sein dass sie über den maximalen Wert hinausgehen der ist bei der ist bei beiden Datentyp Ente etwa ein Jahr mit 32 Bit gar nicht mal so groß ich glaube so Kursen 4 bis 5 Milliarden wenn ich mich recht ist lange her okay 2 Milliarden also der Gesamtbereich von minus bis plus ist in 4 Komma irgendwas was man ja also wenn Sie das mal vergleichen mit den Staatsschulden dann ist das eine lächerliche Zahl also Sie können ganz schnell machen sich immer bewusst zu müssen mit Datentyp schaut und den können Sie ganz schnell selbst in ganz natürlichen Größenordnungen zum Overflow kommen mit langen wird schon ein bisschen schwieriger kann dafür dürfte ist die Wahrscheinlichkeit groß dass bei halt beim Datengebühren das ist halt nicht der Standardtyp der der typischerweise unterstützt wird von Architektur so dass alles Flächen langsamen geht aber das ist Kaffeesatzleserei was jetzt schnell und das langsam geht soll ich lieber nicht machen so
jetzt gehen wir die technischen Details und das heben wir uns dann aber auf bis zum nächsten Mal das macht aber keinen Sinn dass wir jetzt hier mitten drin dann in der Einführung der technischen Details dann aufhören gut
da danke ich Ihnen für heute und wir sind am Ende
Loading...
Feedback
hidden