Minimum Cost 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 | 14 | |
| 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/21483 (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
Graph (mathematics)Maxima and minimaMass flow rateModel theoryLink (knot theory)Directed graphMinimalkostenflussproblemVector spaceFeasibility studyConstraint (mathematics)Conservation lawPositional notationBipartite graphTransportation theory (mathematics)Maß <Mathematik>FluxSupremumVertex (graph theory)SummationKanteGrand Unified TheoryMaß <Mathematik>Kapazität <Mathematik>Absolute valueSet (mathematics)Untere SchrankeLösung <Mathematik>Mathematical optimizationBoom barrierComputer animation
09:10
Maxima and minimaBipartite graphTransportation theory (mathematics)Maß <Mathematik>WärmestrahlungConstraint (mathematics)Planar graphOrthogonalityLink (knot theory)Mathematical optimizationFeasibility studyResidual (numerical analysis)Graph (mathematics)Proof theoryInflection pointRange (statistics)KanteOptimumChain complexInfinityDirection (geometry)FluxTheoryGrand Unified TheoryStress (mechanics)
18:10
Link (knot theory)Maxima and minimaMathematical optimizationConstraint (mathematics)Conservation lawTotal S.A.Residual (numerical analysis)Graph (mathematics)Set (mathematics)KanteAdditionOptimalitätsbedingungMathematical inductionVariable (mathematics)Scalar potentialSummationFluxExponentiationGradientComputer animation
27:10
Maß <Mathematik>Maxima and minimaReduction of orderCondition numberMathematical optimizationGraph (mathematics)Residual (numerical analysis)Range (statistics)Link (knot theory)Feasibility studyProof theoryNegative numberCycle (graph theory)Equivalence relationEvent horizonProfessional network serviceDirection (geometry)KanteGrand Unified TheorySummationStress (mechanics)Kapazität <Mathematik>Scalar potentialPotential gameOptimalitätsbedingungNegative numberFamily of setsComputer animation
36:10
Maxima and minimaMathematical optimizationVertex (graph theory)DistanceLink (knot theory)Hill differential equationFeasibility studyCondition numberProof theoryCycle (graph theory)Equivalence relationNegative numberCategory of beingAdditionLiquidOptimalitätsbedingungPotential gameKanteModulformKapazität <Mathematik>LengthUntere SchrankeSupremumSet (mathematics)Boom barrierComputer animation
45:10
Cycle (graph theory)Negative numberCondition numberMaxima and minimaMass flow rateLink (knot theory)Residual (numerical analysis)Graph (mathematics)Mathematical optimizationBellman equation8 (number)IterationZielfunktionINTEGRALFunction (mathematics)Directed graphZahlLaufzeitKapazität <Mathematik>IterationKanteSign (mathematics)MassNegative numberSummationChain complexMaß <Mathematik>IntegerVelocityComputer animation
54:16
Maxima and minimaMaß <Mathematik>Negative numberCycle (graph theory)Mathematical analysisResidual (numerical analysis)IterationArithmetic meanGraph (mathematics)AerodynamicsComputer programmingTransformation (genetics)Sign (mathematics)Number theoryRational numberINTEGRALChaos (cosmogony)Kapazität <Mathematik>RoundingTrailIterationAbschätzungSet (mathematics)Universe (mathematics)KanteCalculationMass flow rateGrand Unified TheoryMaß <Mathematik>Computer animation
01:03:21
Range (statistics)StatisticsTransformation (genetics)Maxima and minimaIterationLink (knot theory)Mathematical optimizationVector spaceConstraint (mathematics)Insertion lossDirected graphConservation lawChemical equationMaß <Mathematik>Inflection pointSummationOptimumMischung <Mathematik>Kapazität <Mathematik>Nichtlineares GleichungssystemFilm editingNegative numberTerm (mathematics)OptimalitätsbedingungKanteEquationComputer animation
01:12:27
Maxima and minimaDirected graphVector spaceConstraint (mathematics)Conservation lawChemical equationCondition numberMathematical optimizationResidue (complex analysis)Vertex (graph theory)Graph (mathematics)DistanceReduction of orderProof theoryArc (geometry)Residual (numerical analysis)Electric currentSet theoryLink (knot theory)Maß <Mathematik>Hydraulic jumpLösung <Mathematik>KanteInvariant (mathematics)SummationTrailHausdorff spaceDecision theoryKapazität <Mathematik>QuoteSample (statistics)Stress (mechanics)Computer animation
01:21:32
Mathematical analysisMaxima and minimaIterationSign (mathematics)LengthMaß <Mathematik>Total S.A.Scaling (geometry)Physical quantityIterationSummationSupremumFactorizationLaufzeitWegeproblemBoom barrierWell-formed formulaComputer animation
01:29:12
Maxima and minima
Transcript: German(auto-generated)
00:01
Präsentiert von OpenLearnWare, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo, wir machen ein neues Thema, minimale Kostenflüsse. Wir haben uns jetzt die ganze Zeit mit MaxFlow beschäftigt.
00:21
Wir werden jetzt zu minimalen Kostenflüssen kommen. Ich denke, dass wir das in den letzten beiden Terminen durchziehen können. Zu den weiteren Themen werden wir nicht mehr kommen. Ich denke, ich werde daraus eine dreistündige Veranstaltung machen, sodass auch jemand mit meinem Tempo in der Lab ist, durch diesen ganzen Stock durchzukommen.
00:44
Falls Sie Interesse daran haben, das vielleicht schon als dreistündige Veranstaltung zu bekommen, wird sich das sicherlich irgendwie arrangieren lassen mit Prüfungstechnisch usw. Aber was die Veranstaltung angeht, so wie sie in Tukan jetzt in diesem Semester angeboten wird,
01:03
wird dieser Stoff natürlich, den wir hier besprochen haben in der Vorlesung, natürlich der einzige Stoff sein, der in der Prüfung zugrunde liegt. Das versteht sich. Gut, minimale Kostenflüsse will ich gar nicht so viel dazu sagen, denn das hatten wir schon. Am Anfang, als wir mit Früsten begonnen haben, ist es nur eine Erinnerung.
01:23
Wir haben wieder eingerichteten Grafen. Jetzt haben wir Kosten auf jeden Kanten. Wir haben untere und obere Schranken, wie bisher auch auf jeder Kante. Meistens bei Max Flow hatten wir die unteren Schranken auf Null gesetzt, aber es ist nicht zwingend notwendig. Und hier wird es auch nicht immer der Fall sein.
01:45
Und das hatten wir ausgiebig diskutiert, das will ich Ihnen noch mal ganz kurz daran erinnern, dass wir bei jedem Knoten einen Wert haben, der sagt, ein Wert BV, der sagt, wenn er größer ist als Null dieser Wert, dann kommen dort Flusseinheiten rein,
02:01
oder sollen dort Flusseinheiten reinkommen in der Lösung. Wenn er kleiner als Null ist, dann sollen dort Flusseinheiten aus dem Netzwerk rausgezogen werden. Wenn er gleich Null ist, dann soll da gar nichts passieren, dann soll die ganz normale Flusserhaltungsbedingung gelten. Genau das, was reingeht, geht auch wieder raus aus diesen Knoten. Das ist, wie gesagt, eine alles Wiederholung.
02:24
Bei Max Flow hatten wir uns im Wesentlichen konzentriert auf dem Fall eine Quelle, eine Senke. Aber das hatten wir von Anfang an hier allgemein eingeführt, dass die Supply- oder Demand-Knoten, dass es nicht nur einer sein muss, sondern dass es mehrere sein können.
02:42
So, wir hatten das auch schon mal gesagt, nur noch mal zur Erinnerung. Wir können ohne Beschränkung der Allgemeinheit davon ausgehen, dass wir keine parallelen Kanten oder Schleifen haben. Der Schleifer war zur Erinnerung eine Kante, deren Start- und Endnoten derselbe ist. So, was ist die Problemstellung dann? Minimierung, Flusserhaltungsbedingung.
03:02
Wir kommen erst einmal dazu. Für jeden Knoten soll Summe, was rausgeht, minus Summe, was reingeht, gleich dem B-Wert dieses Knotens sein. Das heißt also, wenn dieser B-Wert größer ist als Null,
03:22
Summe, was rausgeht, minus Summe, was reingeht, also größer Null ist, dann ist die Bedingung, wir reden hier von einer Bedingung an dieser Stelle, dann sagt die Bedingung also, aus diesem Knoten soll entsprechend viel rausfließen, umgekehrt, wenn es kleiner Null ist. Kapazitätsbeschränkung unter einer Gruppe Kapazität eingehalten.
03:41
X ist die Lösung, die wir berechnen wollen. Und dieses X nennen wir weiterhin, so wie bisher auch ein Fluss oder auch statischen Fluss und eine Abgrenzung zu dynamischen Flüssen, deren Theorie auf der Theorie statischer Flüsse aufbaut. Dazu werden wir aber dieses Semester nichts sagen. Aber da geht es darum, dass der Fluss nicht permanent in der Zeit immer gleich statisch ist,
04:04
sondern dass der Fluss sich auch ändert in der Zeit. Also beispielsweise, dass eine Riesenmenge an Flußeinheiten das Netzwerk hindurchzuschicken ist und am Anfang baut sich der Fluss erst auf und dann strömt es und dann strömt es und am Ende baut sich der Fluss wieder ab. Das wäre ein Szenario für dynamische Flüsse beispielsweise.
04:23
So, was minimieren wir hier? Das hatte ich kurz eben übersprungen, will ich noch mal ganz kurz sagen, weil wir das auch schon alles hatten. Für jede Flußeinheit, die wir über eine Kante schicken, ij, kostet uns Cij Einheiten in Euro oder in sonst einer Währung.
04:43
Und wir schicken Xij Einheiten drüber. Das heißt also, Fluss über diese Kante ij zu schicken, kostet uns Cij mal Xij. Und über alle Kanten hinweg nehmen wir natürlich die Gesamtsumme. Die Gesamtkosten des Flusses ist die Summe der Kosten der Flüsse auf den einzelnen Kanten.
05:05
So, Flusserhaltungsbedingungen, Kapazitätsbedingungen. Notation hatten wir auch öfters mal. M ist immer die Anzahl der Knoten, M die Anzahl der Kanten. U ist eine obere Schranke für die echten oberen Kapazitäten.
05:27
Also wir hatten ganz zu Anfang des letzten Kapitels gesagt, es kann auch eine obere Schranke, eine obere Kapazität unendlich sein, um anzuzeigen, dass man darüber beliebig viel Fluss überschicken will.
05:40
U ist die oberste obere Schranke, die eben nicht unendlich ist, die einen echten Flaschenhals darstellt. Auch für die Kosten nehmen wir einen Maximalwert. Zunächst mal haben wir die Kosten nicht von vornherein als positiv eingeführt, sondern sie können auch nicht durch als negativ oder null sein.
06:03
Wir setzen daher für diesen Wert groß C als obere Schranke nicht für die Kosten, sondern für den Betrag der Kosten. Das heißt, damit haben wir die negativen Kosten auch größenordnungsmäßig eingefangen. So, es gibt diverse Anwendungen dafür.
06:23
Gehen wir zu dieser zweiten Anwendung hier. Typische Situation. Sie haben ein Netzwerk mit spezieller Struktur. In solchen typischen Anwendungen ist das Minimum-Kostproblem.
06:43
Nämlich, dass Sie eine Menge von Knoten haben, die Sie nach links zoomen. Wir werden schon mal mit die Partiten grafen. Eine Menge nach rechts.
07:04
Das sind hier Facilities. Also typische Situationen sind verschiedene Versorgungsstationen, von denen man Güter transportieren kann. Und verschiedene Endkunden, verschiedene Ziele, die jeweils einen Bedarf haben.
07:24
Und Sie haben die Wahl, für jede vernünftige Möglichkeit von einer dieser Facilities
07:43
etwas rüberzuschicken an dem allgemeinen Gut zu den Customers. Das kostet sich natürlich jeweils etwas. In der Realität abhängig vor allem von der Geografie.
08:01
Die sind natürlich geografisch nicht so schön aufgereiht, sondern die sind irgendwo auf der Erdoberfläche verteilt. Dementsprechend haben Sie irgendwelche Kosten. Und was Sie wollen, Sie haben hier Möglichkeiten, wie viel Sie rausschicken können. Und Sie haben hier Bedarfe, wie viel Sie hier reinschicken sollen.
08:24
Und Sie wollen einen Minimalkostenfluss berechnen, der dafür sorgt, dass hier keine Kapazität von einer Facility überschritten wird. Und dass hier die Bedarfe genau gesättigt sind.
08:43
Und Minimalkostenflüsse kann durchaus heißen, dass beispielsweise hier rein mehrere Flüsse gehen. Eine von hier und eine von hier, die zusammen dann diesen Bedarf verfolgen. Es muss nicht so sein, dass immer genau von einer Facility zu einem Customer dafür gesetzt wird.
09:04
Es gibt noch weitere verschiedene Beispiele dafür. Es gibt unendlich viele Anwendungen des Minimalkostenflussproblems, die wir hier aber jetzt nicht weiter diskutieren wollen. So, wir können die Optimalität einer Solisimulösung sehr einfach charakterisieren.
09:33
Nämlich, dass es keinen Zykl gibt, auf dem wir den Fluss verändern können,
09:44
sodass die Kosten sich damit verbessern. Wovon ist hier die Rede? Also zunächst mal im Ursprungsgrafen. Sie erinnern sich schon vom Nextflow her, die haben es immer mit Fahren bzw. jetzt mit Zyklen zu tun,
10:00
die vorwärts- und rückwärtskant haben können. So, und wenn Sie jetzt, Sie können diesem Zyklen eine von zwei beliebigen Orientierungen geben. Und wenn Sie jetzt die Möglichkeit haben, ein kleines Epsilon hier auf den Vorwärtskanten
10:24
nach dieser Orientierung den Fluss zu erhöhen und hier auf den Rückwärtskanten den Fluss zu vermindern, sodass Sie nicht aus dem Kapazitätsbereich bei irgendeiner Kante rausgehen, dann kommt es jetzt darauf an, wie sich die Kosten dadurch verändern.
10:43
Alles plus ein Epsilon minus demselben Epsilon. Epsilon plus ein Epsilon verschwindet sich. Wenn jetzt, wenn sich diese Fluss so verändern, dann heißt es, dass Sie hier auf jeder Vorwärtskante die Kosten um Cj mal Epsilon erhöhen
11:08
und hier auf jeder Rückwärtskante die Kosten um Cj mal Epsilon vermindern. Also dieses j ist natürlich anders als dieses, das haben wir hingeschrieben.
11:20
Und je nachdem, wie die Gesamtsumme ist, die Kosten der Vorwärtskanten, die Kostenwerte hier der Vorwärtskanten, positiv genommen, davon abgezogen die Kostenwerte der Rückwärtskanten. Wenn das negativ ist, dann heißt das, diese Operation, diese Änderung der Flusswerte entlang dieser Cypels
11:42
hat insgesamt eine Verbesserung gebracht, eine Verringerung der Gesamtkostenwerte und damit kann der ursprüngliche Fluss nicht optimal gewesen sein. Das Ganze übersetzen wir jetzt wieder, dieses Bild übersetzen wir jetzt wieder
12:01
in den Visuagrafen, weil dort, weil wir dort ja die Unterscheidungen machen, wir sind zwischen Vorwärts- und Rückwärtskanten. Das ist der Sinn und Zweck des Visuagrafen eigentlich.
12:21
Und weil wir dort bequemerweise mit den Restkapazitäten eh nur arbeiten, also nicht mit explizit mit aktuellen Flusswerten minus, nein, mit Oberkapazitäten minus aktuellen Flusswerten, sondern mit der Rest, diese Differenz schon von vornherein als Kapazität im Visuagrafen.
12:42
Dann würde dieses Bild sich ergeben, die Kontrolle hier, 1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, 5, 6, 7, 8, 9, dann würde sich das hier im Visuagrafen übersetzen,
13:08
dass alle Kanten dieselbe Richtung haben und das wir da jeweils um Epsilon erhöhen. Auf den Kanten, die schon ursprünglich in dieser Richtung waren,
13:20
so wie diese Kante hier, bleiben dann die Kosten der Depose, so wie sie waren. Und auf den Kanten, die umgedreht worden sind, wird dann auch der Kostenwert negiert, sodass das Ganze völlig identisch ist im Visuagrafen.
13:41
Die Operation ist völlig 1 zu 1 zu holen, als wenn wir im ursprünglichen Grafen mit Vorwärts- und Rückwärtskanten arbeiten würden. So, die eine Seite von Theorien habe ich Ihnen jetzt gerade eben schon mal bewiesen, die einfach, die leichte. Nämlich, wenn es einen Zykel gibt mit negativen Kosten,
14:04
dann kann dieser, dann können wir entlang dieses Zykles Fluss erhöhen. Ein Zykel im Visuagrafen ist immer ein Zykel, an dem wir den Fluss erhöhen können, so ist gerade der Visuagraf definiert. Das heißt also, wir sind zu einem neuen zulässigen Fluss gekommen,
14:21
Flusserhaltungsbedingungen sind erfüllt, Kapazitätsbedingungen sind erfüllt und weniger Kosten, das heißt also, der ursprüngliche Fluss war nicht optimal, wenn es einen solchen Zykel gibt. Umgekehrt, das Ganze wird jetzt ein bisschen kompliziert,
14:42
deshalb wollte ich hier mal wieder, also kompliziert mit Notation, deshalb wollte ich hier mal wieder abweichen von den Folien und versuche das Ganze ein bisschen anschaulicher zu erläutern, was die umgekehrte Seite des Beweidens angeht.
15:09
So, wir wollen dieses Theorem beweisen, Theorem 1. Ein zulässiger Fluss ist genau dann optimal, Kosten optimal, minimale Kosten, genau dann, wenn es im Visuagrafen keinen gerichteten Zykel mit negativen Kosten gibt.
15:25
Eine Richtung haben wir schon, die Einfallrichtung, wenn es einen gerichteten Zykel mit negativen Kosten gibt, kann es nicht optimal gewesen sein. Jetzt drehen wir es um, wir nehmen an, dass dieser Fluss, von dem jetzt die Rede ist, nicht optimal ist, dann x Stern, dann gibt es einen anderen Fluss,
15:40
x Quer, der noch geringere Kosten hat. So, wir können das, so gilt können wir uns gefolgt überzeugen. Wir gucken uns eine Kante an,
16:08
bei der die Flusswerte von x und x Quer unterschiedlich sind. So eine Kante muss es geben, wenn x Quer besser ist als x Stern,
16:20
können die beiden nicht identisch sein auf einer Kante. So, zum Beispiel, dass hier auf dieser Kante der bessere Fluss, x Quer größer als dem x Stern ist. Zum Beispiel, kann auch genauso gute Sachen mitbekommen.
16:40
So, das hat aber Konsequenzen, weil beide Flüsse die Flusserhaltungsbedingungen erfüllen. Dann muss es entweder mindestens eine Kante geben, die rausgeht, wo das selbe gilt,
17:01
oder alternativ muss es mindestens eine Kante geben, die reingeht, wo sich das umdreht. Sonst können nicht beide Flüsse zugleich an diesen Knuten hier die Flusserhaltungsbedingungen erfüllen.
17:21
Mindestens eines von beiden muss gelten. Zum Beispiel das hier. Das Argument lässt sich fortsetzen, dann gibt es wieder eine Kante, vielleicht geht es jetzt mal das Argument in die umgekehrte Richtung, vielleicht wieder in die umgekehrte Richtung, vielleicht geht es jetzt wieder um.
17:42
Das Argument lässt sich immer weiter fortsetzen, ins Unendliche rein. Was heißt denn das Endliche? Und das Endliche heißt, es muss sich irgendwann zügig schließen. Weil wir haben ja nicht viele Knoten, die wir besuchen können. Irgendwo müssen wir mal einen Zügelbeschluss haben. Das kann ein Kurzschluss hier sein, dass wir hier irgendwo zurückkommen.
18:03
Oder das könnte auch so sein, wie ich das jetzt hier anleuten möchte, dass wir tatsächlich zu der Kante zurückkommen, die wir mit der weggekommen sind. Muss nicht sein, es könnte auch sein, dass wir hier so einen Kurzschluss haben und hier diesen Zügel haben. Aber es wird schöner, dass die Kante, mit der wir angefangen haben,
18:21
auch Teil des Zügels ist. So, dann können wir entlang dieses Zykles, x quer ist ja, erfüllt ja auch die Kapazitätsbeschränkung, dann können wir entlang dieses Zykles den Fluss verändern.
18:43
So, u minus, so nach unserem Schema. U minus epsilon plus epsilon plus epsilon. Und sind ein kleines Stück näher nach x quer gekommen.
19:02
Wir sind mit x Stern gestartet. Und sind ein kleines Stück näher nach x quer gekommen. Und wenn wir das epsilon so groß gehen, wie der Flaschenhals dabei. Also, da wo es zum Anschluss geht, die minimale Restkapazität von diesem Zügel,
19:21
die wir verwenden können, dann heißt es, mindestens eine Kante auf diesem Zügel, wo x quer und x Stern sich unterschieden haben, auch mindestens an dieser Kante sind x quer und x Stern identisch geworden. Damit x Stern durch Addition von diesem epsilon oder Subkription von diesem epsilon
19:43
so stark geändert, dass es identisch mit x quer geworden ist. So, und das kann man fortsetzen. Das haben wir jetzt anders gemacht. Haben wir einen Fluss bekommen,
20:03
der sich von dem x quer, von diesem super guten Fluss um eine Kante weniger unterscheidet. Auf einer Kante weniger unterscheidet. Jetzt noch mal das selbe nochmal. Wieder so ein Zügel. Wir kriegen wieder einen neuen, leicht veränderten Fluss, der sich wieder, mindestens einer Kante weniger unterscheidet
20:21
von unserem Ziel, von unserer super guten Lösung x quer und so weiter. Das sind endlich viele Schritte, vollständige Induktion über die Anzahl der Kanten, auf denen x Stern und x quer sich unterscheiden. Induktionsanfang trivial. Wenn es nur Kanten sind, auf denen sich beide unterscheiden, braucht man nichts zu tun.
20:40
Induktionsschritt ist genau dieses Bild. Wenn die beiden sich unterscheiden, nehmen wir einen solchen Zügel her, ändern darauf den Fluss, sodass auch mindestens einer Kante die beiden Flüsse sich nicht mehr unterscheiden und können dann die Induktionsvoraussetzungen anwenden und wissen,
21:01
der Unterschied zwischen x Stern und x quer ist so zu beschreiben, als eine Menge Vollzüge, die man durch das Zügel erinnern kann. Ja, ist das so weit klar? Also übrigens nichts Neues. Das haben wir eigentlich schon mal am Anfang des Themas Flüsse. Als wir gesagt haben, dass sich ein Fluss
21:21
dekorbonieren lässt in Fahre und Zügel. Und die Differenz zweier Flüsse, was wir jetzt nochmal gesagt haben, lässt sich dekorbonieren in Zügel alleine. So, der Entscheidungsgesetz der,
21:42
dass es mindestens unter diesen eigentlich vielen Zyklen, die wir so konstruieren können, um von x Stern nach x quer zu kommen, dass es mindestens ein Weg ist, bei dem diese Operation zu einer Verbesserung der Kosten führt. Denn x quer ist ja besser als x Stern. Wenn jeder Zügel auf dem Weg von x Stern nach x quer,
22:01
jede solche Zügeländerung, nur zu einer Verschlechterung oder Gleichbleib führen, dann könnte x quer nicht besser sein als x Stern. Also es muss es einen solchen Zügel geben und damit ist das Theum bewiesen. Wenn x Stern nicht optimal ist, wenn es einen besseren Fluss gibt, dann gibt es einen Zügel,
22:22
auf dem wir den Fluss verändern können, ausgeben von x Stern und zu einer besseren Lösung kommen. Sodass die Kosten durch diese Änderung auf diesem Zügel reduziert werden. Das ist das, was ich versucht habe hier mit diesem Bild in meinen mündlichen Erklärungen anzudeuten,
22:43
beziehungsweise das, was hier völlig identisch, völlig analog, soweit ich das gesehen habe, dann mit einer ganzen Menge von Notationen dann auch bewiesen wird.
23:03
Wie üblich, wenn Sie mir in der mündlichen Prüfung das gut nochmal wiederbringen können, was ich jetzt mündlich unter einer Tafel betrachtet habe, ist es schön, wenn Sie sich aber lieber den Folien folgen wollen in der mündlichen Prüfung,
23:21
ist es mir auch recht. Aber letztendlich ist beides, soweit ich das gesehen habe, eigentlich derselbe Gedankengang nur einmal von mir informell ausgedrückt und hier sehr formal ausgedrückt. So, es gibt noch eine andere Optimalitätsbedingung für minimale Kostenflüsse.
23:43
Da haben wir eine zusätzliche Variable für jeden Knoten, die traditionell mit Pi von V für Potential abgekürzt wird. Wir haben jetzt zunächst einmal Definition. Wir haben jetzt ein Wert Pi von V
24:00
für jeden Knoten V und können einfach mal etwas definieren, was wir hier abgekürzt haben, C, V, W, Pi, abhängig von Pi also, die sogenannten reduzierten Kosten der Kante, dass wir von den ursprünglichen Kosten der Kante im Visual grafen,
24:21
den Potentialwert des Startknotens abziehen und den Potentialwert des Zielknotens draufsetzen. Wobei dieses C, V, W quer, das ist hier die letzte Zeile, ist das, was ich eben hier im Beispiel genannt hatte.
24:42
Wenn Sie vom ursprünglichen Grafen aus den Visualgrafen übergehen, dann machen Sie ja potenziell aus einer Kante zwei Kanten. Und wenn Sie hier Kosten C, J drauf haben, dann würden Sie für die Vorwärtskante
25:01
die Kosten C, J setzen und für die Rückwärtskante die Kosten minus C, J. Denn Fluss über die Vorwärtskante hier zu schicken, bedeutet ja, den Fluss hier zu erhöhen, bedeutet, die Kosten entsprechend diesen Kosten über C, J zu erhöhen. Fluss über die Rückwärtskante zu schicken, bedeutet,
25:21
Fluss hier zu vermindern, also entsprechend Kosten wegzunehmen auf dieser Kante. Das sind die C-Quer-Werte. So, erst einmal eine Kleinigkeit.
25:41
Wenn ich auch eine Pfad habe, auf dem ich dann die reduzierten Kosten aufsummiere, dann kommt noch eine ganz einfache Relation
26:00
zu den ursprünglichen Kosten raus, das werde ich noch ganz kurz andeuten, warum das so ist. Einfaches Beispiel, Sie haben Knoten V1, V2, V3, V4, V5, V6.
26:24
Was ist die Summe der reduzierten Kosten? C, P, I gleich 1 bis 5, der Kante I, V I, V I plus 1.
26:48
Was ist das? Da kann ich jedes Mal die Definition einsetzen. Das ist die Summe I gleich 1 bis 5. Die ursprünglichen Kosten,
27:08
V I plus 1, jetzt muss ich selber noch mal gucken, wie rum ist das, dann zähle ich hier von P von V I ab und addiere P von V I plus 1 hinzu.
27:24
Das Ganze unter der Summe. Was steht jetzt hier? Das ist eine Teleskopsumme, ich weiß nicht, ob Ihnen jemand anderes sagt. Haben Sie die Teleskopsumme schon mal gehört? Okay, gut, dann sollte es leicht sein, dann sollten Sie allein von dem Begriff her schon ahnen, wohin das Ganze geht.
27:43
Na ja, jeder Pi-Wert hier von 2 bis 5 kommt zweimal vor. Einmal positiv, einmal negativ. Fallen also weg, das heißt, alles, was übrig bleibt, ist Summe I gleich 1 bis 5,
28:03
C V I V I plus 1, minus einmal ganz am Anfang, das hebt sich nicht weg, plus einmal ganz am Ende, das hebt sich auch nicht weg. Alles andere dazwischen hebt sich weg, weil es einmal positiv, einmal negativ vorkommt. Und nichts anderes steht hier
28:23
in etwas anderem Notation. Ich habe es jetzt hier für ein Beispiel gemacht, hier ist es allgemein formuliert, dass der Unterschied also zwischen den Gesamtkosten eines Fades nach reduzierten Kosten und nach Originalkosten
28:42
sich um einen Ausdruck unterscheiden, minus Pi-Startnoten plus Pi-Zietnoten, der Unabhängigung war das. Ja, Sie sehen hier, da kommt der Pfad nicht vor. Hier sieht man der Pfad von V 1.
29:03
So, da können wir einen Schritt weitergehen und das Ganze auch für Züge betrachten. Da heben sich dann auch noch zusätzlich die beiden weg. Wenn das ein Zügel wäre, dann wäre V 1 mit V 6 identisch, dann würde sich das auch wegheben und dann wäre tatsächlich übrig,
29:22
dass die Summe der reduzierten Kosten auf einem Zügel gleich die Summe der ursprünglichen Kosten auf diesem Zügel ist. So, was hat es jetzt mit diesen Potentialen überhaupt auf sich? Ich habe jetzt zunächst einmal hier auf dieser Folie viel Brimborium gemacht,
29:42
um da irgendetwas einzuführen, dessen Sinn und Zweck noch gar nicht so richtig klar wird. Sie können schon erahnen, dass wir da ein zweites alternatives Optimalitätskriterium damit rauskriegen, aber gut, da sind wir noch hin, aber vielleicht eine kleine Intuition,
30:01
eine ökonomische Intuition. Gehen wir mal vielleicht weiter. Nehmen wir mal an, wir haben eine Situation, dass wir das Gut, was wir transportieren wollen, durch Netzwerke hindurch, Wasser, Strom, was auch immer,
30:22
wenn wir das an einem Knoten V eine Einheit davon produzieren, dann kostet uns das ein Wert, den wir als Minus Pi von V ansetzen. Umgekehrt, Pi von V ist das Negative
30:43
von den Kosten der Produktion dieses Gutes an diesem Knoten V. So, wenn wir in einem Knoten U dieses Gut produzieren, eine Einheit davon produzieren
31:00
und dann eine Einheit von U nach V über die Kante UV schieben, dann ergibt sich als Gesamtkosten dieses hier, Minus Pi von U, wie wir eben gesagt hatten, so haben wir es gerade definiert, plus die Kosten für eine Einheit über eine Kante zu transpondieren, C quer UV,
31:23
und es macht in dem Sinne keinen Sinn, sowas zu machen, wenn die Potenziale tatsächlich diese Bedingungen erfüllen, also wenn die Erstehungskosten einer Einheit
31:43
am Knoten V kleiner sind, kleiner gleich sind, als die Erstehungskosten an einem anderen Knoten im Transport zum Knoten V, umgedreht, dass die reduzierten Kosten größer gleich Null sind. Wenn die reduzierten Kosten größer gleich Null sind, wenn wir ein Potenzial haben,
32:01
sodass die gefunden haben, sodass die reduzierten Kosten größer gleich Null sind, dann haben wir eine ökonomisch optimale Lösung gefunden dafür, wie viel wir an jedem einzelnen Knoten
32:20
erzeugen von diesem ökonomischen Gut und es nicht von woanders her transportieren lassen. Ich möchte gleich wieder weggehen davon, das hat eigentlich mit dem Weiteren nichts weiter zu tun, aber ich gebe Ihnen vielleicht eine gewisse Einsicht darin, insbesondere diejenigen von Ihnen vielleicht, die sich mit Ökonomie, gibt es jemand von Ihnen,
32:41
der Betriebswirtschaft oder was im ökonomischen Bereich an und aus gemacht oder ausgewählt hat? Okay, vielleicht sagt Ihnen das, solche Equilibrier, solche Gleichgewichtsfunktionen, wo die Situation so ist, dass wenn man irgendeine Kleinigkeit ändert, kann es nur schlechter werden.
33:03
Die ökonomische Situation. So, jetzt kommt die angesprochene Optimalitätsbedingungen. Ein Fluss ist genau dann, Fluss X Stern ist genau dann optimal,
33:21
wenn wir solche Potenziale pi finden, sodass dann tatsächlich diese reduzierten Kosten, von denen ich die ganze Zeit spreche, größer oder kleiner sind. Dann ist ein zulässiger Fluss optimal. Genau dann. So, eine Richtung ist wieder
33:42
wie so häufig die einfache. Und zwar, gehen wir nochmal zurück. Property 2. Für jeden Zyklen gilt,
34:03
dass die Summe der reduzierten Kosten die gleiche Summe der ursprünglichen Kosten. Jetzt muss ich nochmal überlegen.
34:22
So, ich will alles jetzt sehen. Wenn die reduzierten Kosten alle nicht negativ sind, heißt das,
34:41
dass auch die, wir sind ja im Ressort Grafen, wo wir immer Kapazitäten übrig haben. Wenn die reduzierten Kosten nicht negativ sind, dann heißt es natürlich, dass auch auf einem Zyklen, die reduzierten Kosten nicht negativ sein können.
35:01
Das heißt, nach dieser Property 2, nach dieser Gleichheit hier unten, dass dann auch, gemäß der ursprünglichen Kapazitäten, dieser Zyklen nicht negativ gewesen sein kann. So, die eine Richtung haben wir.
35:28
Wenn wir für irgendein Potential diese Bedingung erfüllt haben, dann über Property 2, dann haben wir auch die ursprüngliche, die erste Optimalitätsbedingung erfüllt.
35:44
So, jetzt gehen wir die umgekehrte Richtung, den dritten Spiegelstrich. Wir gehen davon aus, dass wir einen Fluss haben, der die erste Optimalitätsbedingung erfüllt. Das heißt, es gibt keine negativen Züge. Und wir wollen jetzt zeigen, dass es eine Notklotenpotenziale gibt,
36:03
sodass die reduzierten Kosten, gemäß diesen Notenpotenzialen, auf jeder Kante größer als null sind. Das heißt, wir haben ein Konstruktionsproblem. Wir haben einen Flüssigstern gegeben. Wir wollen diese Potenziale jetzt konstruieren. Da gibt es verschiedene Möglichkeiten.
36:23
Wir betrachten Option 1 und Option 2 im Grunde als eine Möglichkeit. Und Option 3, die überspringen wir hier. Da sehe ich jetzt nicht unbedingt den Sinn, warum wir den Option 3 betrachten sollten. So, lassen Sie sich jetzt erst mal nicht verdreßen von den Formen hier. Ich versuche es wieder anschaulich zu machen.
37:12
Wir betrachten mal eine spezielle Situation, dass wir einen Knoten haben, von dem aus es einen flusserhöhenden Fahrt
37:24
zu jedem anderen Knotenrahmen gibt. Wir werden diese einschränkende Bedingung fallen lassen in Option 2. Aber jetzt betrachten wir erst mal diese Situation. Irgendwie sowas.
37:40
Zu jedem Knotengrafen gibt es von diesem einen festgesetzten Knoten S aus. Ist egal welcher das ist. Den nennen wir dann halt S. Wenn wir ihn gefunden haben, von dem aus gibt es überall einen flusserhöhenden Fahrt. Wir machen also einen Fahrt im Rizualgrafen.
38:05
Und wir nehmen diese Kapazitäten, wir interpretieren diese Kapazitäten jetzt mal um. In Fahrtlängen, in Kantenlängen. Und berechnen wir einfach mal die kürzesten Fahrtlängen
38:21
nach diesen, nach den, äh, Entschuldigung, die Kosten. Nicht die Kapazitäten. Berechnen wir nach diesen Kosten, die wir als Fahrtlängen die kürzesten Wegedistanzen von diesen Knoten aus.
38:41
So, da kommen wir wieder zu etwas zurück, das wir schon kennengelernt haben. Wir haben hier eine Kante Vw. Und dann nenne ich einfach mal die kürzesten Fahrtdistanzen Pi von V und Pi von W. Und was wir wissen aus den Kapitel über kürzeste Wege ist,
39:09
dass Pi von W, natürlich ein kleiner Gleich, Pi von V plus Länge dieser Kante,
39:21
dafür haben wir diese Kosten hergenommen. Und das ist gerade die Bedingung, die wir brauchen, dass die reduzierten Kosten nach diesen Knotenpotenzialen größer oder höher sind. Das geht exakt da. Also, das muss man nur umstellen. Genau auf die Form bringen, wie sie es definiert nach.
39:44
Also, das nach links stellen und dann machen wir es. Das heißt also, wir können einfach die kürzesten Fahrtdistanzen von irgendwelchen, beliebigen Knoten aus hernehmen, sofern auch diese Knoten aus alle anderen erreichbar sind.
40:00
Und haben nach diesen kürzesten Fahrtdistanzen gemäß Kantenlänge gleich Kosten bei dieser Kante, haben wir ein solches Potenzial konstruiert, mit dem diese Zweitoptimalitätsbedingungen erfüllt sind, dass die reduzierten Kosten für alle Kantengröße nicht mehr sind.
40:23
So, aber so schön ist es natürlich im Allgemeinen nicht. Jetzt haben wir natürlich die Situation, dass es im Allgemeinen keine solchen Knoten mehr gibt, von denen aus alle anderen Knoten erreichbar sind. Es muss nicht sein, dass es den gibt.
40:43
Das ist das, was hier als zweite Option... Ja? Okay, okay, okay.
41:00
Wichtige Frage. So. Zunächst einmal sind die... Also die Frage war, woher die Pi vom Pi-Wert eigentlich kommen, nicht? Zunächst einmal sind sie beliebig. Wir sagen einfach nur, die Pi-Werte sind ein Potenzial. Wir nennen es halt Potenzial. Das sind irgendwelche reellen Werte,
41:23
die mit den Knoten assoziiert sind. So, die erste Verknüpfung sagt diese Optimalitätsbedingung. Sie sagt aus, wenn ein Fluss ist, genau dann optimal, wenn ich Knotenpotenziale finden kann, wenn es so etwas gibt, Knotenpotenziale gibt,
41:42
was diese Eigenschaft erfüllt. Genau dann optimal. Wenn es solche Knotenpotenziale gibt... Wir haben hier ein Beispiel. Ja, wir haben hier ein Beispiel. Da. Also vielleicht besser hier.
42:04
Wenn ich einen Knoten habe, von dem aus alle anderen Knoten erreichbar sind, dann kann ich ein solches Knotenpotenzial, was diese Eigenschaft erfüllt, konstruieren, indem ich schlicht und einfach die kürzeste Wege des ganzen Knotenpotenzialigener ernehme.
42:21
Das ist das Beispiel. Nicht im engeren Sinne ein Zahlenbeispiel, so mit 1, 2, 3 und 587, sondern ein genehmiges Beispiel, aber ich denke, es sollte bei Ihnen trotzdem auf fruchtbaren Boden fallen, nachdem wir damit sehr intensiv befasst haben zu Anfang der Folge.
42:43
So, ist damit Ihre Frage beantwortet? Gibt es weitere Fragen in dieser Stelle? Gut, dann machen wir mal weiter. Was ist jetzt der Fall, wenn es diese Knoten nicht gibt? Ja, ganz einfach. Dann schaffen wir uns diesen Knoten mit Gewalt.
43:04
Obtaining Accessibility. Wie machen wir das? Nehmen wir mal an,
43:25
es gibt noch weitere Knoten hier im Grafen, die von S aus nicht im visualen Grafen erreichbar sind. Das könnten eine ganze Menge sein. Dann ziehen wir einfach eine Kante rüber,
43:43
zu jedem von denen. So, ich hoffe, das wird noch halbwegs übersichtlich. Hier siehst du, hier sehen Sie, wir fügen Kanten ein, und zwar hin und zurück sogar,
44:02
so rum und zurück, und setzen die unteren Schranken auf Null, die oberen Schranken auf einen sehr, sehr großen Wert, und die Kosten auf einen sehr, sehr großen Wert,
44:20
sodass sich durch diese Kosten, sodass sich durch diese neuen Kanten die Situation nicht ändert. Ja, also, die Kosten sind so groß auf diesen Kanten, dass man da keinen Fluss drüber schicken will. Sodass es also keinen Unterschied macht, ob sie da sind oder nicht da sind.
44:40
Aber jetzt haben wir die Situation von Option 1 erreicht, alle Knoten sind mit Gewalt jetzt von S aus erreichbar. Also manchmal, Sie kennen ja den Spruch, wenn man mal ein Hammer als Werkzeug hat, dann merkt man alle Probleme als Nägel anzusehen. Manchmal ist ein Hammer auch mal etwas ganz Nützliches, auch bei uns.
45:05
So, Option 3 überspringe ich, brauchen wir nicht. Macht die Sache nur unnötig kompliziert. So, im Grunde wissen wir jetzt aber schon, wie wir einen optimalen Fluss,
45:23
einen maximalen Kostenfluss berechnen können. Wir fangen mit irgendeinem zulässigen Fluss an, und suchen schrittweise nach negativen Zyklen, nach Zyklen, auf denen die Gesamtsumme der Kosten negativ ist, verändern darauf entsprechend den Fluss,
45:43
so stark wie möglich, dass auf diesem Zyklen nicht noch weiteren Fluss verändern werden kann, ohne dass die Kapazitäten überschritten werden. Und dann gucken wir wieder, iterativ, wieder nach einem negativen Zyklen, verändern auch wieder die Zyklen und so weiter und so fort,
46:00
bis wir keinen negativen Zyklen mehr finden. Und die erste Optimalitätsbeliebung hat uns schon gesagt, wenn wir keinen negativen Zyklen finden, dann ist der Fluss optimal. Entweder wir finden einen negativen Zyklen, dann verändern wir den Fluss entsprechend, kommen zu besseren Kosten, oder wir finden keinen mehr, dann ist der Fluss, den wir so schrittweise erhalten haben, optimal.
46:23
Das nennt sich Negative Cycle Canceling. Also, wir canceln die schrittweise einen negativen Zyklen nach dem anderen, bis wir keinen mehr haben. So, ich habe jetzt so einfach mal gesagt, naja, wir starten mit so der Sieben Fluss, aber wie kriegen wir denn so der Sieben Fluss her?
46:42
Ja, ganz einfach. Das steht hier in dieser einen Zeile. Ich glaube, aber ich sollte vielleicht noch ein paar Worte mehr dazu sagen, was diese Zeile bedeutet.
47:13
Sie haben hier eben richtigen Graphen, wo alles drin ist. Alle Knoten, alle Kanten, alle Kapazitäten von Kanten, alle Kosten von Kanten
47:22
und alle B-Werte, Balancewerte von Knoten, ja? Sieht so aus, nicht? Können Sie sich vorstellen? Gut. Jetzt steht hier so lapidar in einem Satz, wir brechen mit einem maximalen Fluss. Was dahinter steht, was damit gemeint ist,
47:41
wir fügen ein Knoten S irgendwo draußen hinzu und ein Knoten E draußen hinzu. Und wenn wir einen Knoten V haben und einen Knoten W, jetzt muss ich überlegen, wie rum ist das richtig,
48:01
positiver Balancewert hieß, es geht mehr raus als rein, nicht? Das heißt also, was ich will, ist die Situation, dass Bv größer 0 ist und dass Bw kleiner 0 ist. Die mit Leichnung interessieren uns nicht. Dann fügen wir hier eine Kante mit Kapazität Bv ein
48:22
und hier fügen wir eine Kante mit Kapazität minus Bv ein. Und die restlichen Kanten usw. mit ihren Kapazitäten lassen wir. So, es gibt jetzt zwei Möglichkeiten.
48:43
Jetzt lassen wir den next flow von S nach T darüber laufen. Es gibt jetzt zwei Möglichkeiten. Entweder alle diese Kanten, die aus S rausgehen, werden bis zum Anschlag saturiert. Was identisch damit ist, dass alle Kanten nach T reingehen, bis zum Anschlag saturiert werden.
49:01
Sie haben sich ganz einfach gesagt, die Balancewerte müssen sich zu 0 aufsummieren. Das heißt, die Summe der positiven Balancewerte auf der einen Seite und die Summe der negativen Balancewerte auf der anderen Seite sein. Entweder das klappt. Dann haben wir einen Fluss hier drin, im ursprünglichen Grafen gefunden,
49:22
wo hier an jedem Knoten V Bv-Einheiten mehr rausgeht als eingeht. Weil diese Bv-Einheiten kommen hier, die fallen fast im Maße des Wortes vom Himmel. Und bei jedem Knoten W haben wir tatsächlich erreicht, in diesem Fluss, den wir hier konstruiert haben, der von S nach T durch das Netzwerk durchgeht,
49:44
dass Bv-Einheiten mehr reingehen als rausgehen. Das ist die eine Möglichkeit, dass wir es geschafft haben. Dann haben wir eine zulässige Lösung, Flusserhaltungsbedingungen für alle Balancewerte erfüllt. Kapazitäten haben wir bei dem Exflo von vornherein mitbeachtet.
50:04
Die andere Möglichkeit ist, dass wir das nicht schaffen, dass hier noch Kapazität übrig bleibt. Dann gibt es keinen zulässigen Fluss im ursprünglichen Netzwerk.
50:21
Denn wenn es einen zulässigen Fluss gäbe, dann könnten wir diesen Fluss hernehmen und erweitern auf diese Kanten und hätten unseren Fluss mit dem auf dem Anschlag. Wir haben aber einen maximalen Fluss, und wenn der maximale Fluss die nicht alles saturiert,
50:43
heißt es, es gibt keinen Fluss, der diese Kanten alle saturiert. War das jetzt ein bisschen zu schnell? War das jetzt irgendjemand zu schnell? Zu langsam. Ich kann auch schneller.
51:06
Wer hat okay gesagt? Ach so, ein Kurier von der Geschwindigkeit. So, jetzt haben wir eine erste zulässige Lösung
51:20
und jetzt können wir losgehen, einen negativen Zykl nach dem anderen zu canceln. Sie kennen den Bell-Mann-Ford-Algorithmus. Damit kriegt man negative Züge raus. Brauche ich nicht mal weiter hier zu wiederholen. So, die Gesamtkosten können am Anfang nur so hoch sein.
51:45
Anzahl der Kanten mal maximaler Kapazitätswert, also maximal m mal groß u. Viele Einheiten können über eine Kante rübergehen. Das heißt also, der Flusswert über eine Kante kann höchstens 10 mal u sein.
52:02
Anzahl der Kanten m ist das maximale, was der Kostenwert sein kann. Das heißt also, umgekehrt kann das das Beste sein, was wir erreichen können. Minus m mal 10 mal u. Kleiner als minus m mal 10 mal u kann kein Flusswert sein.
52:23
Das heißt, dieser Algorithmus startet mit irgendeinem Kostenwert m mal 10 mal u, kleiner gleich m mal 10 mal u und endet mit einem Kostenwert größer, gleich minus m mal 10 mal u und kann also nur in der Laufzeit.
52:43
Das beschränkt halt die Laufzeit, weil ja natürlich in jeder Iteration, wo ein negativer Zykel gecancelt wird, nimmt ja der Kostenwert echt ab. Und zwar, wenn wir von ganzen Zahlen rausgehen als Kapazitäten,
53:02
ist es auch eine ganze Zahl, um die es abnimmt, also mindestens eins. Das heißt, wir kriegen m mal 10 mal u raus als Anzahl der Iterationen. Und n mal m, die bellt mal fort, dominiert die Iteration, das ist der gesamte Aufwand.
53:21
Ist nicht schön, aber das war einer der Auskunftspunkte, von dem viele Leute losgegangen sind, um schrittweise bessere Laufzeiten hinzubekommen. Wir wollen uns aber jetzt mit diesem einfachen Algorithmus hier bescheiden. So, das ist dieser negative Algorithmus, der Negative-Cycle-Canceling-Algorithmus.
53:46
Sie haben wie üblich den gerechten Grafen, Kantenkosten, Kapazitäten, jetzt die Balancewerte. Und falls es einen zulässigen Fluss gibt, soll er berechnet werden. Wir fangen an, so ich das eben hier angedeutet habe, einen ersten zulässigen Fluss zu berechnen.
54:07
Und solange es einen negativen Cycle gibt, suchen wir einen, identifizieren wir einen, setzen darauf, ändern darauf den Fluss, müssen natürlich immer den Swirl-Grafen entsprechend updaten.
54:21
Und das wars. Also eigentlich ein sehr einfacher Algorithmus. Ok, das ist ja High-Level, natürlich. Aber das sind alles Dinge, die wir schon besprochen haben, die wir jetzt nicht nochmal im Einzelnen hier aufführen müssen, was das im Detail heißt. So. Ja, genau. Das muss man sich klar machen.
54:47
Wenn die Kapazitätswerte und die Balancewerte ganz zahlig sind, dann sind sämtliche Flüsse, die wir im Laufe der Zeit berechnen, die sind immer ganz zahlig.
55:00
Und auch der letzte Fluss ist ganz zahlig, das heißt also, wenn die Kapazitäten und die Balancewerte ganz zahlig sind, dann gibt es tatsächlich ein Mincos Flow mit ganz zahligen Flusswerten. Weil dieser Algorithmus einen solchen konstruiert. Also muss es ihn geben, sonst könnte er nicht konstruiert werden.
55:20
Ich möchte Sie darauf aufmerksam machen, dass das alles andere als selbstverständlich ist. Wenn Sie zum Beispiel Situationen haben, dass Sie nicht ein Gut von irgendwelchen Knoten oder irgendwelchen anderen Knoten transportieren wollen, sondern zwei Güter, Klaviere und Elefanten wollen Sie mit Ihrer Speditionsflotte transportieren
55:41
und an manchen Startpunkten haben Sie so und so viele Klaviere und so und so viele Elefanten und an den Endpunkten wollen Sie so und so viele Klaviere jeweils rausbekommen und so und so viele Elefanten. Sie haben aber das selbe Netzwerk, die selbe Kapazität, die sich die Klaviertransporte und die Elefanten-Transporte teilen muss.
56:04
Ja, allein diese kleine Änderung, dass Sie nicht Eigengut haben, dass Sie transportieren sondern zwei Güter, die Sie sorgsam auseinanderhalten müssen, da wo Elefanten verlangt werden, dürfen nicht Klaviere geliefert werden und umgekehrt, die sich die gemeinsamen, dieselben Kapazitäten auffüttern,
56:23
da ist es schon nicht mehr so, dass Sie ganz zahlige Leute haben. Da haben Sie noch halbzahlige Lösungen, also halbe Elefanten und halbe Klaviere können Sie dann optimal anliefern, aber wenn es mehr als zwei Güter sind,
56:40
dann wird es beliebig razzomal. So, den Algorithmus gehen wir jetzt hier nicht durch, das können Sie wieder für sich dann im stillen Kämmerlein anschauen, um nachzuvollziehen, wie das Ganze funktioniert.
57:01
Über diese Folie brauchen wir jetzt auch nicht so viel zu sagen. Das sind noch ein paar Verbesserungsmöglichkeiten. Die erste Verbesserungsmöglichkeit, wenn es denn eine ist, ist, es bietet sich ja an, nicht einfach irgendeinen Zykl zu nehmen,
57:23
auf dem wir vielleicht gerade mal so eine Einheit verbessern können, wenn es irgendwo einen anderen Zykl gibt, auf dem wir gleich tausend Einheiten verbessern können, vielleicht eine ganze Menge anderer Zykl, wo man nur eine Einheit verbessern könnte, gleich mit erschlagen haben, die sind auch gleich weg, die sind damit auch gleich zerstört.
57:42
Also, es bietet sich doch an, darüber nachzuschauen, ob man nicht immer die maximale Verbesserung gleich, ein Zykl mit maximaler Verbesserung finden kann. Wäre schön, wir werden das hier nicht beweisen, aber es wäre schön, das zu haben, weil man dann nämlich beweisen kann,
58:01
dass die Anzahl der Interaktionen deutlich reduziert ist. Sie wissen, immer wenn ein Lockfaktor im Spiel ist, ist es eine deutliche Verbesserung. Schön, aber das Problem an der Sache ist, so ein Zykl mit maximaler Verbesserung zu finden, ist irgendwie schwer. Sie erinnern sich, haben wir das hier schon mal betrachtet, irgendwie schwer?
58:23
Also, der Optimierungsalgorithm, da bin ich laufend davon, jeden Mittwoch. Hier bin ich mir jetzt nicht ganz sicher. Ich will Ihnen kurz nochmal sagen, was endlich schwer heißt, pragmatisch gesehen. Ich will nicht darauf eingehen, was es theoretisch heißt, mathematisch, sondern was es pragmatisch heißt.
58:42
Ich meine, wir haben das schon mal am Anfang, irgendwann, als es um Deichstrau-negative Zyklen ging, muss man so kurz gesagt haben, ich sag normal. Es bedeutet ganz, wenn eine algorithmische Problemstellung irgendwie schwer ist, ja, irgendwie schwer ist ein Attribut, eine Eigenschaft von algorithmischen Problemstellungen. Wenn eine algorithmische Problemstellung, wie hier das Finden eines Zykl mit maximaler Verbesserung irgendwie schwer ist, heißt es,
59:08
für jeden Algorithmus, den Sie für diese algorithmische Problemstellung sich auch nur ausdenken können, egal wie er aussieht, egal wie genial Sie sind, für jeden, auch nur denkbaren Algorithmus,
59:23
gibt es Beispiele von sehr moderater Größe, auf denen dieser Algorithmus länger braucht zum Rechnen als dieses Universum überlaut. Und zwar um Größeordnungen, das heißt, wir reden um mehrere Universen, bis der endlich mal fertig ist.
59:42
Von moderater Größe, 15 Knoten, 100 Knoten oder so etwas. Ist also nicht wirklich eine prägende Situation. In der Optimierungsalgorithmen rede ich darüber, wie man mit Problemstellungen, die NP-schwer sind, umgeht, weil das dumme an der Sache ist, dass die meisten Universen,
01:00:00
Die aus der Freien Wildbahn, aus dem Komikal, aus der Ökonomie, Logistik, Ingenieurwissenschaft, Planung in Fabriken und so weiter. Egal woher, die Probleme sind in der Regel nicht schwer. Dunkel gelaufen. Man kann aber trotzdem noch eine ganze Menge damit machen, um zu Ort bringen müssen, um zu kommen.
01:00:20
Aber hier für unsere theoretischen Betrachtungen, die effizienten Betrachtungen, da binden sie eher so die hübsche theoretische Vorlesung. Da ist das dann sozusagen das Ende der Bahnstange. Da wird es hässlich, und hässlich heißt Vorlesung-Optimierung-Album nicht nur Vorlesung effizient ist. Das wäre jetzt keine negative, nicht als negative Werbung für die andere Vorlesung gemeint.
01:00:46
So, was man aber noch machen kann ist, entlang eines Zykles von negativen Kost, man kann einen Zykl mit minimalen Durchschnittskosten so definiert, also Gesamtkosten geteilt durch Anzahl der Kanten im Zykl,
01:01:11
kann man finden. Und das führt dann tatsächlich zu, das will ich hier nur erwähnt haben, sie brauchen sich auch nicht diese Formeln jetzt für die Prüfung zu merken.
01:01:23
Diese Folie ist nur so nebenbei. Das führt zu dieser Situation, einen solchen minimalen, durchschnittlich minimalen Kostenzykl, den kann man relativ schnell finden, und die Anzahl der Iterationen ist dann auch noch sehr klein.
01:01:46
Sie sehen, ich glaube letztes Mal habe ich gesagt, je ekliger die Formeln sind zur Abschätzung so als Forstregeln, desto ekliger ist es den Algorithmen zu implementieren, und das trifft bei diesen Algorithmen voll und ganz zu.
01:02:01
Also sollte ich Ihnen jemals die Aufgabe, Algorithmen und Praktikumstellen dieser Algorithmen hier zu implementieren, dann wissen Sie, ich habe etwas gegen Sie. Aber ich glaube nicht, dass das vorkommen wird. Falls ich etwas gegen Sie habe, gibt es noch ganz andere Möglichkeiten.
01:02:25
Aber das sind schon fiese Möglichkeiten, muss ich dazu sagen, solche Algorithmen. Wobei ich nichts gegen diese Algorithmen und ihre Urheber sagen will. Das ist schon eine geniale Leistung.
01:02:41
Ein wichtiger Punkt ist, wir haben ja jetzt erst einmal Kantenkosten positiv oder negativ betrachtet. In gewissen Situationen, ich glaube wir werden dazu noch kommen, möchte man lieber nur nicht negative Kantenkosten haben.
01:03:02
Das ist eine ganz einfache Geschichte, wie man zu nicht negativen Kantenkosten kommt. Hier, so weit. Wie kriegen wir hin, dass sämtliche Kantenkosten nicht negativ sind?
01:03:20
Naja, wenn wir eine Kante mit negativen Kosten haben, was war das VW?
01:03:52
Übrigens, die Bezeichnungsweise, dass man VW dafür nennt, ist wesentlich älter als irgendwelche Automobilformen. Das ist keine Schleichwerbung.
01:04:08
Und der hat Kantenkosten C, VW kleiner Null. Na ja, hauen wir wieder mit dem Hammer drauf, drehen wir die Kante um, setzen Kantenkosten C, VW.
01:04:22
Wir müssen aber nur dazu beachten, dass es natürlich hier Balancewerte gibt, die wir jetzt abdenken müssen, damit die Situation wieder im Lot ist.
01:04:44
Das steht hier, wie das abgedatet werden muss. Ich denke, das brauchen wir nicht weiter zu besprechen. Also, ohne beschränkende Gemeinheit, sind von jetzt an alle Kantenkosten nicht negativ. Wenn sie das nicht sind, dann machen wir es mit Gewalt.
01:05:10
Jetzt kommt die andere Situation. Was haben wir jetzt eben gemacht? Der Negative Cycle Cancelling Algorithm. Wir sind gestartet mit einer zulässigen
01:05:23
Lösung, mit einem zulässigen Fluss, der aber nicht unbedingt optimal ist. Und haben durch Cancelling von negativen Zyklen, haben wir diesen Fluss Schritt für Schritt die Kosten reduziert, solange bis dieser Fluss optimal ist. Aber die ganze Zeit, jeder Zwischenschritt, vom allererstem bis zum allerletzten, jede Zwischenglösung hat die Flusserhaltungsbedingungen und die Kapazitätsbedingungen eingehalten.
01:05:52
Jetzt drehen wir es um. Sie kennen das von Max Flow. Da war dieselbe Situation. Die meisten Elemente, die wir betrachtet haben, haben die Zulässigkeitsbedingungen, Kapazitätsbedingungen und Zyklen eingehalten.
01:06:05
Und haben schrittweise den Max Flow immer mehr Max gemacht. Sie verstehen, was ich meine. Mit der Formel A möchte ich nicht zitieren.
01:06:23
So, dann haben wir Preflow Push gesehen, Push Relabel gesehen. Also manchmal nennen wir es Preflow Push, manchmal nennen wir es Push Relabel. Ich habe schon wieder vergessen, wie viel es genannt hat hier in der Vorlesung. Ist ja auch egal.
01:06:41
Bei dem Algorithmus war es so, dass wir nicht einen zulässigen Fluss hatten, weil die Flusserhaltungsbedingungen nicht erfüllt waren. Dafür haben wir aber die Optimalität in der ganzen Zeit hindurch. Die Optimalitätsbedingungen, nämlich, dass es einen saturierten Schnitt von S nach T gibt, eingehalten. Und so ähnlich ist es hier. Die Zwischenergebnisse sind nicht zulässig, weil sie
01:07:09
zwar die Kapazitätsbeschränkungen einhalten, aber nicht die Flusserhaltungsbedingungen, die Balanzbedingungen an den Einsynchronen.
01:07:21
Aber es ist immer optimal. Die Optimalitätsbedingungen sind immer erfüllt. Es gibt keinen negativen Zykl. Die Optimalitätsbedingungen sind immer erfüllt. So, wie geht das? Gut, wir brauchen noch diese technische Einschränkung, die
01:07:51
keine echte Einschränkung ist, dass es V-Zwecknoten-Einfahrt gibt im Visualgrafen. Wie man das erreichen kann, haben Sie gesehen, als wir von S aus mit Gewalt überallhin ein Pfad gebastelt haben.
01:08:04
So, ich erkläre Ihnen das Ganze wieder, glaube ich, am Bild. Oder vielleicht lassen wir noch mal ganz kurz, bevor ich Ihnen das am Bild erkläre.
01:08:20
Wir brauchen noch eine Notation, die Ihnen bekannt vorkommen könnte aus dem Bereich Max Flow, wo wir da EV-Excess Überschuss hatten. Und genau das ist es auch wieder. Was ist der Überschuss hier? Das ist das, um das die Balancebedingungen, die Flusshaltungsbedingungen an diesem Knoten verletzt ist.
01:08:44
Ja, eigentlich sollte es sein, dass diese Summe hier Summe rein, Minus Summe raus, nein umgekehrt, Summe raus, Minus Summe rein, nach drüben geschoben, dass die gleich B von V ist. Eigentlich, sagt die Flusshaltungsbedingungen, dieser Wert EV, so wie er hier definiert ist, ist gleich Null.
01:09:03
So, wenn wir die Flusshaltungsbedingungen nicht erfüllen, heißt das schlicht und einfach, diese EV-Werte sind nicht alle gleich Null. Es gibt Werte, die nicht gleich Null sind. Hier, im Gegensatz zum Thema Pochereben, also Rhythmus, ist es aber so, dass dieser E von V Wert durchaus auch negativ sein kann.
01:09:23
Dort war es immer positiv, hier darf er positiv oder negativ, darf natürlich auch gleich Null sein und am Ende soll er auch gleich Null sein. Das heißt also, wir haben die Situation, Optimalität ist erfüllt durch unseren Fluss X, das heißt es gibt keinen negativen Zyklen, Kapazitäten sind eingehalten,
01:09:43
aber die E von V-Werte sind nicht alle gleich Null, das heißt die Flusshaltungsbedingungen sind nicht an allen Knoten erfüllt. So, wie ist jetzt die Idee des Alkoholkos? Eigentlich eine ganz einfache Sache.
01:10:34
Das ist wieder unser großer Traum.
01:10:41
Jetzt haben wir hier irgendein Knoten mit E von V Null. Jetzt suchen wir uns einen kürzesten Weg zu irgendeinem Knoten mit E von V Null.
01:11:05
Ich habe vergessen was noch zu sagen, das müsste auch auf der nächsten Folie stehen, oder sogar auf der Folie hier unten. Über alle Kanten entweggenommen summieren sich diese Differenzen hier zu Null auf.
01:11:26
Weil jeder X-Wert genau einmal vorkommt positiv und einmal vorkommt negativ. Wenn ich also diese Gleichung hier, E von V gleich B von V plus bla bla bla, aufsummiere für alle Knoten V,
01:11:45
dann heben sich diese Terme mit X hin nun alle weg. Weil jede einzelne dieser X-Werte einmal positiv einmal negativ auftraut. Über alle Knoten hin weggenommen. Bei dem einen Knoten einmal positiv bei der Zielkante, negativ bei der Startkante.
01:12:06
Nein, positiv beim Zielknoten der Kante, negativ beim Startknoten der Kante. So, das heißt was übrig bleibt ist, wenn ich diese Gleichungen hier aufsummiere über alle Knoten V,
01:12:21
dass die Summe der E-Werte gleich die Summe der W-Werte ist. Die Summe der W-Werte haben wir festgestellt, wenn das Ganze überhaupt lösbar ist, ist die Summe der W-Werte Null. Nur dann kann die Instanz überhaupt lösbar sein. Haben wir schon mal vor ein paar Terminen festgestellt, können Sie dann, haben Sie mitgekriegt, dass die ersten Filme online sind?
01:12:41
Okay, die Qualität hätte ich mir ein bisschen anders vorgestellt, vor allem von dem Tafel auf Schrieb, aber ich hoffe Sie können dann noch möglichst viel Informationen daraus ziehen. Gut, deshalb, weil die Summe aller E-Werte gleich Null ist,
01:13:07
muss es einem solchen Knoten V mit E-W kleiner Null geben. Wenn es hier den mit größer Null gibt und ungefähr natürlich auch.
01:13:22
Wenn es keinen größeren Null gibt, gibt es auch keinen kleiner Null, dann sind alle E-Werte Null und dann haben wir alle zulässige Lösungen. Wenn wir keine zulässige Lösung haben, wenn wir arbeiten müssen, zulässige Lösungen zu bekommen, dann haben wir mindestens einen größeren Null und mindestens einen kleiner Null. So, jetzt suchen wir den kürzesten Weg zu den Knoten hierher,
01:13:42
den kürzesten Weg hierher, den wir zulassen. Wie man das macht, wissen wir. Ohne Beschränkungen der Allgemeinheit, sie ändern sich von eben von vorher, gehen wir davon aus, dass die Kostenwerte alle uns negativ sind. So, jetzt haben wir alle E-Werte. Ich hatte vergessen zu sagen, kürzesten Weg, wie vorher,
01:14:03
bezüglich der Kosteneizkante liegen. Ohne Beschränkungen der Allgemeinheit sind die nicht negativ, wir können das einfach mit Eiz da machen. So, und wenn wir jetzt den Fluss hier entlang erhöhen, dann heißt das, ich hoffe, ich habe das jetzt richtig gemacht,
01:14:22
es kann sein, dass ich eher kleiner Null und größer Null da habe, dass ich kleiner und größer Null vertauschen muss, und dann können Sie ja über das Verständnis noch einmal zuhause überlegen, ob das Sorum richtig ist, dass hier EV-Grußanlage und EV-Kleider so ist, oder ob es andersrum sein muss. Mein Koffeepiegel ist leider nicht hoch genug, um das jetzt hier nochmal durchzureißen.
01:14:46
Das sind doch so die schönen kleinen ebbaren Unstädigkeiten, an die man wunderbar sein langes Verständnis überprüfen kann. So, wenn wir den Fluss hier dann erhöhen, dann heißt das, dass dieser Überschuss und dieser Unterschuss,
01:15:03
wie ich das so sagen darf, dass die sich entsprechend reduzieren. Und wir also die Gesamt-Distanz von Zulässigkeit reduziert haben. Und wenn wir ganzzahlige Werte wieder haben, ganzzahlige Kapazitäten, ganzzahlige Balancewerte,
01:15:20
dann haben wir auch tatsächlich einen ganzzahligen Wert reduziert, mindestens eins. Nicht irgendwie so einen kleinen Frickelkabel zu haben, sondern mindestens eins. Das ist jetzt noch keine große Kunst.
01:15:40
Warum? Jetzt müssen wir nur darauf achten, die Invariante soll sein, dass es keine negativen Zyklen gibt. Das heißt die Invariante ist, dass dieser Fluss immer optimal ist. Warum ist die Invariante erfüllt? Also vorher, bevor wir diese Operation, diese Füße erhöhen,
01:16:01
entlang dieses Fades gemacht haben, gab es nach Annahmen noch keinen negativen Zyklen. Wir müssen jetzt beweisen, dass es danach nach dieser Operation auch keinen negativen Zyklen gibt. Wie können wir das beweisen? Na ja, wie kann denn ein negativer Zyklen entstanden sein? Ja, vorher nicht da, aber er kann entstanden sein dadurch,
01:16:22
dass irgendwelche Kanten, mindestens eine Kante hier vorher in der Gleichnull hatte und hier die Füße nun hat, sodass rückwärts diese Kante plötzlich flusserhöhend ist. Dann hat es den Fluss wieder so entschieden. So kann ein neuer Zyklen entstehen, den vorher nicht gemacht haben.
01:16:44
Muss nicht ganz so schön sein, kann auch ein bisschen rarer üben sein, aber so vom Gesamtkonzept her sieht es so aus. So, wenn dieser Zyklen negativ ist, das ist aber das Entscheidende. Hier haben wir noch einen zweiten alternativen Pfad von v nach b.
01:17:01
Nämlich hier lang entlang des Zyklen ohne die Kante und hier lang weiter. Wenn dieser Zyklen negativ wäre, dann hieße das, dass dieser alternative Pfad hier hinten rum kürzer gewesen wäre als die hier.
01:17:26
Und das hat gewählt worden wäre. Warum? Das Ganze ist negativ, der ganze Zyklen ist negativ, inklusive der Kante so herum. Das können Sie sich noch mal im stillen Kämmerlein klar machen.
01:17:40
Das bedeutet, die Kante so herum ist mindestens so lang, ist sogar länger als dieser Teil des Wegs. Sonst könnte der Zyklen mit der Kante so herum nicht negativ sein. Das würde ich Ihnen als Aufgabe zur Brutung des Verständnisses zu Hause mitgeben.
01:18:05
Ich würde Ihnen noch mal ganz kurz klar machen, dass das Bild natürlich wieder trügerisch simpel ist.
01:18:32
Ich würde noch mal ein Zeichner von v nach d mit diesem Pfad. Dann kann der Zyklen natürlich beniedig anders aussehen.
01:18:43
So, nochmal vorwärts zeigen und so weiter. Jetzt bin ich selber durch eine Decke gekommen. Also ich kriege das nicht mehr hin, dass das jetzt ein Zyklen wird. Aber Sie verstehen, was ich meine. Dass dieses Bild, wie ich es hier gezeichnet habe, natürlich nur konzeptionell richtig ist.
01:19:03
Aber das Verhältnis zwischen dem ursprünglichen Pfad und den damit konstruierten Zyklen kann beliebig Krauto drüben sein. So, dann haben wir diesen Alkohol schon erledigt. Ist doch schön, wie schnell und hoffentlich auch intuitiv einleuchtend das Ganze ist,
01:19:23
wenn man sich jetzt nicht an den Folien aufhält, sondern versucht, das Ganze mal an der Tafel zu visualisieren. Das brauchen wir dann alles nämlich auch nicht mehr. Schauen Sie, was ich Ihnen alles erspart habe.
01:19:40
Das Leben kann doch mal nett sein, oder? Gut, für Studierende, die aus den Grundlandveranstaltungen rausgekommen sind, ist das Leben ja sowieso schon recht nett im Verhältnis zu denen, die im Grundlandveranstaltungen drin sind. Oder nicht? Sagen Sie ja.
01:20:00
Genau. So, das kam ja alles jetzt hier. Schauen Sie sich das mal an. Das haben wir jetzt alles übersprungen. Und jetzt kommen wir endlich zu dem Algorithmus, den ich Ihnen eben skizziert habe. Successive kürzeste Wege zu finden. Also, wie üblich, wenn Sie mir das noch mal näher bringen können in der Prüfung,
01:20:23
wie ich es hier mit Aufnahme und einer Tafel gemacht habe, reichen mir das voll und ganz. Auch für eine beliebig gute Note. Aber wenn Sie unbedingt wollen, können Sie mir gerne das noch mal erklären, wie es hier auf den Folien durchgeführt wird.
01:20:41
Aber im Prinzip müsste es auf dasselbe hinaus laufen, soweit ich das jetzt durchgeschaut habe. Und der Algorithmus ist dasselbe. Sie sehen, wir suchen uns immer einen Knoten, der Überschuss hat.
01:21:01
Suchen uns einen kürzesten Weg überall hin. Suchen uns dann einen Knoten, der Unterschuss hat. Und nehmen dann hier in 3.4. Gucken uns dann an, wie viel Kölnerinfluss wir überschicken. Wir gehen natürlich davon ab, wie viel Überschuss bei dem einen Knoten ist,
01:21:21
wie viel Unterschuss bei dem anderen Knoten ist, wie viel risuelle Kapazitäten auf dem Weg ist. Erhöhen entsprechend und daten alles ab. Und fertig. So, können Sie sich hier noch mal angucken, wie das Ganze aussieht. Das müssen wir jetzt heute auch nicht machen.
01:21:43
Analyse, die wollen wir jetzt nicht überspringen. So, also, jeder Iteration löst ein kürzeste Wegeproblem mit nicht negativen Kantenlängen. Dieser Satz ist so schön prägnant, dass ich nichts anderes tun kann, als den vorzulesen. Es war didaktisch schlecht, aber das hätte ich jetzt besser machen können.
01:22:07
So, jede Iteration kostet, dominiert wird das Ganze durch dieses kürzeste Wegeproblem, durch DAEXTRA. Die beste Implementation hatten wir nur kurz erwähnt, sind aber nicht darauf eingestiegen.
01:22:20
Die asymptotisch beste Implementation hat diese asymptotische Komplexität. Dafür muss man aber mit ätzenden Damenstrukturen rumhantieren. Also, diese Fibonacci-Heaps haben sehr, sehr entfernte Ähnlichkeit mit den Heaps, die Sie in der Genie 2 kennengelernt haben.
01:22:46
Ist was deutlich komplizierteres, aber genial. Also, wenn Sie mal ein paar Genialitäten in der Informatik sehen wollen, können Sie sich gerne mal die Fibonacci-Heaps zum Beispiel ansehen. Oder einige andere Dinge, die wir hier immer nur erwähnt haben.
01:23:02
So, jede Iteration verringert den Überschuss mit mindestens einer Einheit, weil wir hier ganz traurig sind, ohne beschränkende Allgemeinheit. So, wenn wir jetzt wieder mit oberen Schranken arbeiten,
01:23:26
die größte Balance hat, glaube ich, Supply von Übungen und Knoten, dann kriegen wir die Anzahl der Iterationen entsprechend raus. In jeder Iteration wird an einem Knoten die Unbalance um eins reduziert.
01:23:42
Das heißt, Anzahl Knoten mal maximale Unbalance. Das ist eine Oberschranke für die Anzahl der Iterationen. Das ist natürlich in der Realität viel besser bei normalen Instanzen, bei nicht pathologischen Instanzen. Und dann kriegen wir diese Laufzeit insgesamt raus,
01:24:01
weil wir in jeder Iteration ja eben einmal Dijkstra als dominierenden Faktor drin haben. Wir können natürlich auch umgekehrt in der Summe der B-Werte, der Balancewerte, die Anzahl der Iterationen ausdrücken.
01:24:22
Also höchstens so viel Iterationen kann es natürlich geben. Und darin ausgedrückt sieht die Gesamtabschätzung mit Dijkstra als dominierenden Faktor für Iterationen eben entsprechend so aus. Ja, da werden wir heute nicht mehr weit kommen.
01:24:44
Das kennen wir, das Thema Scaling. Vom letzten, ungefähr von der letzten Woche sogar. Ja, letzte Woche. Bei Max Flow. Sie erinnern sich, das war so eine ganz merkwürdige Kiste. XS Scaling hieß es da.
01:25:01
Aha, Scaling hat was gesagt. Aber XS Scaling sagt plötzlich was. Dass wir nur Überschüsse weitergeleitet haben bei Kurzgelegel, also dass wir im Korridor zwischen Delta Halbe und Delta sind, solange bis es das nicht mehr gibt.
01:25:21
Und dann gehen wir den Korridor eins runter, zwischen Delta Viertel und Delta Halbe, arbeiten in dem, dann in Korridors Delta Achtel bis Delta Viertel und so weiter und so fort, bis wir ganz oben bei Nummer eins gelandet sind. Dass wir also immer zuerst viel Fluss weiter schütten, solange wir so viel Fluss irgendwo haben als Überschuss,
01:25:42
dann entsprechend weniger, in der nächsten Phase und wieder weniger und so weiter. Was ja auch der Iteration entspricht, dass man erstmal die großen Sachen wegschafft, weil die kleinen dann entsprechend weniger. Wenn man die großen Sachen wegschafft, hat man viele der kleinen Sachen schon erledigt.
01:26:05
So, und genau so werden wir das bei minimalen Kostenflüssen sehen. Die Kapazität, es gibt verschiedene Möglichkeiten, hier Scaling anzuwenden. Es gibt auch Cost Scaling, das heißt, dass man schrittweise immer nur bestimmte Kostenwerte betrachtet,
01:26:23
aber hier betrachten wir nur den Ansatz Capacity Scaling. Das heißt also, dass wir uns erstmal nur mit großer Kapazität kümmern, immer noch mit großem Wert kümmern
01:26:41
und dann erst wenn die alle abgearbeitet sind, dann den Korridor entsprechend einzusetzen, ähnlich wie beim Access Scaling bei den letzten Jahren. Wie Sie sehen, die Ideen kommen immer wieder und deshalb macht es, denke ich, Sinn,
01:27:01
hier viel über die verschiedenen Ideen zu reden und insbesondere zu versuchen, ihnen die Ideen wirklich näher zu bringen, dass sie die Dinge auch verstanden haben, auch wenn das auf der anderen Seite bedeutet, dass wir nicht so viele Algorithmen hier schaffen, die eigentlich vorgesehen sind, laut Folie. So, aber da kommen wir jetzt dieses Mal nicht mehr weiter.
01:27:22
Es macht, glaube ich, keinen Sinn mehr, um die verbleibenden zwei Minuten da noch tief einzusteigen. Sie haben eine Frage? Ja, wie sieht das mit der Planung aus? Machen wir die nächsten Folies, wenn wir dann nur noch die zehn besten Folien haben, oder haben wir das nächste gelangt? Ich mache so weit, wie es sinnvoll ist beim nächsten Mal.
01:27:41
Das heißt, ich werde nicht nach zehn Folien, zehn Folien sind es noch? Nein. Also ich habe es jetzt nicht gezählt. Ich werde nicht nur diese zehn Folien weiter machen, sondern ich werde dann beim nächsten Thema so weit weiter machen, werde auch natürlich dafür sorgen, dass wir am Ende des nächsten Termins nicht mittendrin, sozusagen mittendrin in der Zeile enden, sondern werde rechtzeitig vor Ende des nächsten Termins
01:28:05
umschwenken auf eine allgemeine philosophische Betrachtung des Restes Kapitels. Und das bedeutet natürlich auch, dass auch nur diese allgemeine philosophische Betrachtung des Restes Kapitels berührungsüberwacht ist und nicht die Details, zu denen ich dann nicht mehr gekommen sein werde.
01:28:21
Oh, schöne Verwendung von Foto 2. Gut, damit haben wir jetzt sogar diese zwei Minuten fast überprüft. Es ist mir früher mal passiert, wo ich Folien für Vorlesungen zum ersten Mal gemacht habe,
01:28:42
dass ich mich manchmal verschätzt habe, da war ich gerade mal so eben ein Termin voraus mit den Folien und dass ich dann manchmal entzückt war, dass es so viele Nachfragen gab, weil mich das davor gerettet hat, noch weit vor Ende der Veranstaltung mit meinen Folien zu Ende zu sein. Aber in diesem Fall kann ich das gelassen sehen.
01:29:01
Also es sind Folien da für alle Eventualitäten für den Rest dieses Semesters. So, dann möchte ich mich für heute bedanken und wir haben die Zeit gut rumgekriegt und wir sehen uns dann beim nächsten Mal wieder.