Network Flows VI
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Teil | 13 | |
| Anzahl der Teile | 15 | |
| Autor | ||
| Lizenz | CC-Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben. | |
| Identifikatoren | 10.5446/21477 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
2
3
4
5
7
8
9
10
11
12
13
14
00:00
Maß <Mathematik>Lokales MinimumFunktion <Mathematik>Gerichteter GraphGanze ZahlEntscheidungsmodellKette <Mathematik>RichtungKanteZahlenbereichUniformer RaumMechanismus-Design-TheorieMomentenproblemEbeneMaß <Mathematik>Kapazität <Mathematik>Fluss <Mathematik>Schnitt <Mathematik>MengeHöheInvarianteZahlReihePhysikalische TheorieLängeKnotenmengeComputeranimation
10:00
KnotenmengeAnalysisFunktion <Mathematik>Lokales MinimumMaß <Mathematik>Ganze ZahlGerichteter GraphVektorraumKreisbogenGraphIterationVorzeichen <Mathematik>Operations ResearchSchnitt <Mathematik>InvarianteHöheKantePfad <Mathematik>QuadratRichtungEigenwertproblemEnde <Graphentheorie>Computeranimation
15:19
AnalysisEntscheidungsmodellVorzeichen <Mathematik>Gerichteter GraphOperations ResearchVektorraumKreisbogenGraphKnotenmengeIterationFeasibility-StudieFunktion <Mathematik>Maß <Mathematik>Lokales MinimumGanze ZahlBeweistheorieVektorpotenzialDiskrete-Elemente-MethodeKantePotenzialfunktionIterationAbschätzungSummeMeterLaufzeitGruppoidQuadratMengeComputeranimation
21:26
Operations ResearchFunktion <Mathematik>BeweistheorieVektorpotenzialAnalysisEntscheidungsmodellAbschätzungSummePotenzialfeldQuadratKanteIterationFunktion <Mathematik>HöhePotenzialfunktionAsymptoteZahlenbereichComputeranimation
26:30
Explorative DatenanalyseAnalysisGerichteter GraphOperations ResearchKorrelationVektorpotenzialFunktion <Mathematik>BeweistheorieLokales MinimumIterationComputeranimation
27:43
Vorzeichen <Mathematik>Gerichteter GraphAnalysisVektorraumKreisbogenGraphKnotenmengeIterationLokales MinimumMaß <Mathematik>Funktion <Mathematik>Ganze ZahlFeasibility-StudieMathematikOperations ResearchBeweistheorieVektorpotenzialLie-GruppePhasenumwandlungEntscheidungsmodellZahlSummeLaufzeitMaximumGrößenordnungKanteQuadratReiheAbschätzungKnotenmengeAsymptotikPotenzialfunktionComputeranimation
36:25
PhasenumwandlungGruppoidBeweistheorieAnalysisAlgebraische StrukturZentrische StreckungStrategisches SpielKnotenmengeLokales MinimumGleichungMaximumSummeFaktorisierungQuadratGruppoidHöheLängeComputeranimation
44:34
Lokales MinimumFunktion <Mathematik>Gerichteter GraphGanze ZahlZentrische StreckungKnotenmengeInnerer PunktMaß <Mathematik>KonditionszahlAnalysisMathematikPhasenumwandlungGanze ZahlKapazität <Mathematik>KanteExponentGrößenordnungHöheAbschätzungSchnitt <Mathematik>QuadratParametersystemIterationLogarithmusMaß <Mathematik>ZugbeanspruchungPhysikalische GrößeComputeranimation
54:31
Maß <Mathematik>PhasenumwandlungKonditionszahlZentrische StreckungFunktion <Mathematik>VektorpotenzialBeweistheorieAnalysisGruppoidQuadratSummeFaktorisierungMengeNatürliche ZahlPotenzialfunktionQuotientLogarithmusMathematikLängeZahlentheoriePhysikalische GrößeFunktion <Mathematik>VerschlingungComputeranimation
59:35
Funktion <Mathematik>KnotenmengeInnerer PunktMaß <Mathematik>Lokales MinimumGerichteter GraphGanze ZahlZentrische StreckungMinimumComputeranimation
01:01:59
PhasenumwandlungGruppoidFunktion <Mathematik>VektorpotenzialBeweistheorieZentrische StreckungAnalysisLie-GruppeMaß <Mathematik>EntscheidungsmodellLokales MinimumZahlenbereichMaß <Mathematik>Computeranimation
01:04:54
Maß <Mathematik>KonditionszahlFunktion <Mathematik>KnotenmengeInnerer PunktLokales MinimumGerichteter GraphGanze ZahlZentrische StreckungEntscheidungsmodellKette <Mathematik>FaktorisierungFormation <Mathematik>Kürzester-Weg-ProblemTopologieComputeranimation
01:09:23
PhasenumwandlungGruppoidVektorpotenzialFunktion <Mathematik>BeweistheorieZentrische StreckungAnalysisMaß <Mathematik>Lokales MinimumIndexberechnungOperations ResearchZahlKapazität <Mathematik>Größter gemeinsamer TeilerQuadratNumerisches GitterLaufzeitNetzwerk <Graphentheorie>MeterKlon <Mathematik>GrößenordnungKanteComputeranimation
01:12:23
ResiduumVorzeichen <Mathematik>ÜbergangHeuristikKreisbogenKnotenmengeOperations ResearchLokales MinimumGrothendieck-TopologieMachsches PrinzipBeweistheorieKanteZykelEnde <Graphentheorie>FeuchteleitungSchnitt <Mathematik>Computeranimation
01:16:12
HeuristikKnotenmengeMengenlehreLängePhasenumwandlungLokales MinimumHöheSchnitt <Mathematik>KanteZahlÜbergangEckeComputeranimation
01:21:30
PhasenumwandlungKnotenmengeAbstandHeuristikSchnitt <Mathematik>Langsam wachsende FunktionHeuristikVerschlingungZusammenhang <Mathematik>Klon <Mathematik>Netzwerk <Graphentheorie>Fluss <Mathematik>HöheNetzwerkflussComputeranimation
01:26:48
Computeranimation
Transkript: Deutsch(automatisch erzeugt)
00:01
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, Sie kennen diesen Algorithmus vom letzten Mal, eine andere Vorgehensweise als wir sie vorher betrachtet haben, um dasselbe Problem
00:21
maximale Flüsse zu lösen. Hier, das hatte ich letztes Mal auch zum Wiederholten mal gesagt, wir sind vielleicht nicht so schnell, wie andere Dozenten mit derselben Vorlesung hier, was dann natürlich dazu führt, dass die Übungsblätter sich auch entsprechend nach hinten heraus verschieben, versteht
00:41
sich, aber mir geht es darum, dass sie die Dinge wirklich, diese, die Konzepte wirklich richtig verstehen, denn das ist es, was man sinnvollerweise aus einer Vorlesung effiziente Grafenalgorithmen mit hinausnehmen kann, die Ideen, die dahinter stehen. Seien wir ehrlich, wenn sie nicht später an der Uni in meiner Richtung irgendwie weitergehen, dann werden sie
01:03
mit diesen speziellen Algorithmen, auch mit denen, die wir vielleicht dieses Mal hier nicht schaffen werden, eh nicht wieder in Kontakt kommen, aber was sie an Ideen, an Konzepten gesehen haben, das wird, das wird hoffentlich vom bleibenden Wert sein. Ich denke auch, dass ich wahrscheinlich im
01:20
nächsten Jahr diese zweistündige Vorlesung zu einer dreistündigen machen kann, damit sogar so ein langsamer wie ich das schafft, diesen ganzen Stoff durchzuziehen. So, worum geht es hier? Die Idee der Grundgedanke oder das Bild, was man vielleicht vor Augen haben sollte, ist,
01:43
dass von zu jedem Zeitpunkt, wenn sie sich das als einen Schnappschuss vorstellen, gibt es so etwas wie einen Ausfluss aus S hinaus, dass jede Einheit Fluss, dass eine ganze Menge Einheiten Fluss aus S hinausgehen, die dann
02:03
irgendwo im Moment gerade versickern, irgendwo mittendrin, zum Teil vielleicht sogar schon bis T angekommen sind, ansonsten irgendwo mittendrin sich aufstauen, Exzess-Überschuss produzieren an diesen Knoten, Fluss geht rein, aber geht nicht weiter raus, erzeugen sozusagen so was wie einen Druck und wir wollen schrittweise diesen Überschuss, immer so viel wie
02:27
möglich Überschuss von den momentanen aktiven Knoten, die Überschuss haben, immer weiter voran drängen mit der Zielsetzung, möglichst viel nach T zu kriegen und das, was wir aus T herausgedrückt haben, aber nicht
02:43
nach T rein kriegen, weil hier irgendwo Schnitte sind, deren Kapazität kleiner ist, als das, was wir rausdrücken können unmittelbar bei S, dass das dann so nach und nach wieder dann nach S zurück wandert, so dass am Ende alle
03:01
Überschüsse an Zwischenknoten beseitigt sind, nur noch S, es geht nur noch Fluss aus S raus und nach T rein und weil die Invariante immer ist, dass es zu jedem Zeitpunkt einen Schnitt gibt von S nach T, der vollständig saturiert ist, wo definitiv nichts mehr rübergehen kann von S
03:23
Seite zu T Seite, deshalb wissen wir, wenn am Ende ein zulässiger Fluss entstanden ist, wenn auch die Flusserhaltungsbedingungen erfüllt ist, Kapazitäten sind sowieso immer erfüllt, dann ist es auf jeden Fall ein maximaler Fluss, weil auch am Ende immer noch ein Schnitt saturiert Sie kennen das Mixed Flowing Cut Theorem, der Flusswert eines maximalen
03:43
Flusses ist gleich die Kapazität eines minimalen Schnittes, die minimale Kapazität eines Schnittes, um genau zu sein, so und das ganze wird gesteuert durch diese ominösen, validen Labels, Distanz Labels mit dieser Bedingung, dass wenn Sie eine Kante andersherum, wenn Sie eine Kante VW
04:12
haben, über die Sie Fluss rüber schicken können, eine Vorwärtskante, wo noch Restfluss möglich ist, wo noch Restkapazität übrig ist oder
04:23
eine Rückwärtskante, wo positiver Fluss drauf ist, den Sie wegnehmen können, wenn Sie so einen Labeling haben, was wir ja schon bei Max Flow mit kürzesten Wegen kennengelernt haben, dass Ihnen das
04:42
dann tatsächlich diese Steuerung ohne Kontrolle, ohne wirklich bewusste Einflussnahme, dass Ihnen das diese Steuerung ermöglicht, dass der Fluss, wenn das geht, bis T geht und wenn es nicht bis T geht, dass es dann wieder zurückgeht. Ich will noch mal ganz genau herausarbeiten, was der
05:01
entscheidende Punkt ist, den wir uns da merken müssen, die entscheidende Idee, wenn Sie eine Fahrt haben, von irgendwohin nach irgendwohin, von X nach Y und dieser Fahrt habe K Kanten, K irgendeine Zahl. Wir wissen, von
05:28
irgendeiner VW, dass D von V kleiner gleich, ich hoffe, ich habe das jetzt eben richtig gemacht, ne ich habe das hier doch falsch rum gemacht, also D
05:42
von V kleiner gleich D von W plus eins, so rum war die magische Formel, D von V ist kleiner gleich D von W plus eins und wenn Sie das über den ganzen Weg hinweg hernehmen, dann ergibt sich sofort, dass D von X kleiner gleich D
06:08
von Y plus K sein muss, einfach überiteriert und da K kleiner gleich N
06:21
ist, ein Fahrt ohne Zykel, eigentlich sogar kleiner gleich N minus eins, echt sogar echt kleiner N, da K kleiner sein muss, wissen Sie, dass diese Label, wenn es einen flusserhöhenden Fahrt von X nach Y gibt, dass diese Label höchstens N
06:44
auseinander sein können, also dieses Label kann höchstens N minus eins Zähler höher sein als dieses Label D, das ist entscheidend wichtig in der Argumentation, weil wenn diese beiden Labels mehr auseinander sind,
07:03
mindestens N, dann gibt es keinen flusserhöhenden Fahrt mehr, da schließt sich der Kreis an dieser Stelle, wenn Sie wissen, dass dieses Label hier größer als N ist, das Label von T war ja immer null, dann wissen Sie, es gibt keinen flusserhöhenden Fahrt mehr von diesem Knoten nach T,
07:22
Sie wissen alles, was Sie hier noch an Überschuss haben, das muss nach S zurückgeschossen werden und das geht auch, weil das Label von S ist N, hat die Höhe N und irgendwann durch die Relabel-Schritte, Schritt für Schritt wird das Label von X immer dann, wenn es nichts anders geht, wenn wir
07:40
den Überschuss von X nicht mehr woanders hinschieben können, auf eine Ebene tiefer, immer abwärts zu einem niedrigeren Label, werden wir immer höhere Labeln, das Label von X und irgendwann wird es hoch genug sein, dass es von diesen Knoten aus der Überschuss dann wieder zurückgehen wird, das ist die Magie, von der wir hier reden und ich versuche zu
08:03
kommunizieren und weil ich weiß, dass ich selber damals lange gebraucht habe, um diese Magie zu begreifen und weil ich mal davon ausgehe, unbescheiden, dass ich zu denjenigen vielleicht gehöre, die relativ schnell mit so was
08:21
klarkommen, versuche ich das hier möglichst deutlich zu machen, ich gelinke mir. So der Mechanismus ist ganz einfach, es ist eine Schleife, solange der Fluss noch nicht zulässig ist, er erfüllt immer das Optimalitätskriterium, ist aber nicht zulässig, weil er die Flusserhaltungsbedingungen
08:41
verletzt, solange es noch aktive Knoten gibt, wo also Überschuss da ist, der aufgestaut ist und weiter geschickt werden sollte, nehmen wir uns Knoten, wenn wir von diesen Knoten aus Überschuss nach den Regeln der Kunst weiter schicken können, nämlich danach, admissible arc heißt, dass hier tatsächlich ein Gleich steht und nicht
09:03
nur ein kleiner Gleich, das also wirklich, wie die Intuition ist, dass der Fluss immer eine Stufe abwärts fließt, dann machen wir das, dann schicken wir so viel wie möglich Fluss drüber, also natürlich höchstens so viel wie Überschuss ist, weil wir keinen Unterschuss, wenn ich das so
09:22
sagen darf, hier produzieren wollen, also höchstens den Überschuss abbauen und nicht mehr als das und höchstens natürlich die Restkapazität und wenn das nicht der Fall ist, dann labeln wir den Knoten, denn setzen wir das Label dieses Knotens, wo wir diesen Überschuss nicht wegkriegen konnten über irgendeine admissible arc, setzen wir den gerade mal so
09:42
hoch, dass wieder mindestens eine admissible arc da ist, eine Kante VW, sodass da ein Gefälle wieder um einen Zähler vorhanden ist. So wir sind schon in die Analyse eingestiegen beim letzten Mal.
10:03
Wie fängt es an? Wir fangen damit an, dass wir den einen bestimmten Schnitt saturieren, nämlich den Knoten S, den Startnoten und den Rest, den saturieren wir, indem wir einfach auf jede Kante, die rausgeht, möglichst viel Fluss draufsetzen, alle anderen Flusswerte natürlich am Anfang Null, sodass wir am Anfang schon die Invariante erfüllt haben und wir
10:26
haben aktive Knoten, wir haben das schon gesehen, dass die Flusswerte tatsächlich immer einen Preflow ergeben, also immer nur in jedem Knoten außer S und T immer nur mehr Fluss rein als rausgeht, dass
10:46
wir am Anfang auch keinen Widerspruch erzeugen mit den Definitionen, wenn wir S auf die Höhe N setzen. Gut, wir haben auch schon gesehen, was wir eben
11:02
gesagt haben zunächst einmal ist, wenn zwei Knoten mindestens N auseinander sind, das ist der Fall bei S und T, dS ist gleich N und dt ist gleich Null, dann wissen wir, es gibt keinen flusserhöhenen Fahrt von S nach T
11:24
und das wird die ganze Zeit so bleiben, N bleibt auf dieser Höhe, T bleibt auf dieser Höhe, es bleibt immer ein valid labeling, das heißt also, die Invariante ist erfüllt, es gibt keinen flusserhöhenen Fahrt von S nach T. Das hatten wir alle schon gesehen, diesen Punkt nochmal, der wird dann
11:45
nochmal heute eine Rolle spielen, nochmal dieses Bild, das wir eben ganz am Anfang gesehen haben, wenn Überschuss an irgendeinem Knoten ist, dann muss der irgendwo herkommen, der kann nur aus S herkommen. Ja, das heißt, hier ist irgendwie Fluss, eine gewisse Anzahl von Flusseinheiten müssen nicht über einen
12:02
Fahrt, kann auch über verschiedene Fahrte gekommen sein, muss dieser Überschuss da reingekommen sein, das heißt aber im Umkehrschluss, dass man auch flussrückwärts wieder nach S zurückschicken könnte, sprich, dass es ein flusserhöhenen Fahrt von einem Überschussknoten, von jedem beliebigen Überschussknoten, das S zurückgeht, nämlich die Pfade, alle
12:23
Pfade über die Fluss hier reingekommen ist. So, das hier ergibt sich davor aus sofort, denn sollte das Label irgendeines Knoten, stimmt nicht ganz, für
12:44
jeden Überschuss, ja doch stimmt, für jeden Überschussknoten gilt ja, dass es ein Fahrt zurückgeht nach S, ein flusserhöhenen Fahrt, S hat Höhe N, wenn dieser Knoten Höhe 2N oder höher hätte, gäbe es diesen Fahrt zurück nicht. Ja,
13:01
und das heißt also, einen Überschussknoten können wir niemals so hoch labeln, größer gleich 2N, denn das würde diese Aussage widersprechen, dass es ein flusserhöhenen Fahrt zurück gibt und hier haben wir ja gesehen, wenn es ein flusserhöhenen Fahrt von einem Knoten zum
13:20
anderen gibt, kann das eine Label, das Anfangs Label höchstens N höher sein oder weniger als N höher sein als das End Label und da wir nur Überschussknoten relabeln, können wir auch niemals einen anderen Knoten ohne Überschuss haben, der auf so ein hohes Label kommt. So, wir wissen,
13:43
die Labels liegen alle, für alle Knoten Labels liegen im gesamten Verlauf des Algorithms, die Labels, liegt das Label immer zwischen Null und kleiner 2N, so dass wir also von vornherein wissen, wir haben höchstens 2N Relabeloperationen und das hatten wir schon mehrfach gesehen, warum das so
14:02
ist, dass wir saturierende Pushes, das heißt also die, bei denen wir so viel Fluss rüber schicken über eine Kante, dass die Restkapazität vollständig aufgebraucht ist, dass das beschränkt ist durch die Relabeloperationen, weil sie haben zunächst einmal ein Gefälle von da nach da, bei diesen D-Labels, wenn sie, da hin, sie haben
14:26
erst einmal ein ein Gefälle von da nach da, wenn sie Fluss rüber schicken zwischen den beiden Labels, wenn das saturierend ist, dann geht da nichts mehr rüber, das heißt, damit da später noch mal ein Push rüber gehen kann, in
14:40
derselben Richtung, muss hier was mit den Labels passieren, der muss mal irgendwann mal zwei mal, mindestens zwei hochgegangen sein, damit wieder mal Fluss zurückgeschickt werden kann in die andere Richtung und dann muss der noch mal zwei hochgegangen sein, damit noch mal in derselben Richtung Fluss geschickt worden sein kann, das heißt also, wir haben für jede Kante höchstens O von N mal einen saturierenden Push möglich, weil
15:08
danach das Label am oberen Anschlag ist, das Label starten wird uns dieser Kante. So, das Interessante sind jetzt immer die
15:23
nicht saturierenden Pushs, das heißt, die, bei denen ein, bei denen Fluss von über eine Kante rüber geschoben, geschossen, irgendwas wird, sorry, nicht fürs Protokoll, das war wirklich kein
15:44
Freundschaftsversprecher, möchte ich deutlich klarstellen, aber eben nicht immer noch Restkapazität übrig bleibt, was heißt das, gehen wir noch mal zurück zum Algorithmus, entweder es wird die Restkapazität, als ist das, ist der
16:00
Flaschenhals, dann ist es ein saturierender Push oder hier in Zeile sieben oder der gesamte Überschuss wird ab, von der einen Kante zunächst, über diese Kante von einem Knoten zum nächsten Knoten verschoben, ohne dass die Restkapazität damit vollständig aufgebraucht wäre, also bleibt noch Restkapazität übrig, das heißt, der gesamte Überschuss wird
16:24
verschoben. So, jetzt kommt eine interessante Technik zum Abschätzen von Laufzeiten, die hier in diesem Bereich, glaube ich, wirklich zum ersten Mal entwickelt worden ist, aber die inzwischen schon in vielen
16:43
anderen algorithmischen Problemstellungen nicht nur bei grafen Algorithmen Eingang gefunden hat, nämlich man nimmt sich so eine sogenannte Potentialfunktion her. Dazu brauchen wir mal wieder ein bisschen Platz. So, was ist diese Potentialfunktion hier in diesem
17:21
Fall? Die Summe aller Kanten label von allen, nein Entschuldigung, aller Knoten label von allen Knoten, die aktiv sind, die also Überschuss haben. So, das ist eine Funktion, die ist, wenn wir das mal über die
17:43
Laufzeit verfolgen, diese Potentialfunktion, wie ist die genannt? Phi, so, die ist am Anfang vor der ersten Iteration null, weil wir zunächst einmal ganz zu Anfang haben wir einen Nullfluss, mit dem wir
18:04
alles initialisieren, also am Anfang sind alle alle Flusswerte null, also fangen wir bei null an, danach setzen wir die Flusswerte, der kann ja aus S rausgehen, hoch, das heißt also wir erzeugen tatsächlich Knoten,
18:24
aktive Knoten, Knoten mit Überschuss, das heißt also durch diesen Schritt kommen wir zu einer Anfangssituation. So, hier, das ist vor der ersten Iteration, hier die Stelle, das ist nach der ersten Iteration
18:42
nach der zweiten, nach der dritten und so weiter. So, die verschiedenen Operationen, die wir in jeder Operation machen, einen saturierenden Push, einen nicht-saturierenden Push oder ein Relabel, die sorgen dafür, dass diese Funktion irgendwie hier hoch und runter geht und ganz zum Schluss, wenn
19:02
der Algorithmus terminiert, ist diese Funktion wieder bei null, denn es gibt keine aktiven Knoten, die eine und eine Summe über die leere Menge, wissen sie, ist immer null. Ja, so sieht diese Potentialfunktion irgendwie aus. So,
19:24
was wissen wir noch? Wir wissen, dass sie höchstens 2 N² sein kann, hier ist irgendwo 2 N², oberhalb oder höchst, trifft höchstens die höchste Spitze, weil ja jedes einzelne Label höchstens 2 N werden darf. Gut, so
19:47
jetzt gucken wir uns an, was mit dieser Funktion, mit diesem Phi passiert in den verschiedenen Arten von Operationen. Wenn wir ein Relabeling starten, ich bin mir nicht sicher, ob der Satz so stimmend, also ich bin mir
20:12
sogar ziemlich sicher, dass der Satz so nicht stimmt. Wir müssen hier ein bisschen abschwächen, aber das reicht auch. Was eigentlich hier stehen müsste, was stimmt und was korrekt ist und was auch reicht, ist, dass
20:24
sämtliche Relabeling-Operationen zusammen, was die hier jeweils eine Erhöhung bringen, also hier solche Erhöhungen von hier nach da oder von hier nach da oder von hier nach da, wenn wir diese Flanken, diese Westflanken
20:42
hier alle zusammenzählen, was das sozusagen am Gesamthöhe ist, Sie kennen das vom Fahrradfahren in den Alpen, da zählt man ja auch sämtliche Anstiege zusammen, um damit angeben zu können, dass man da 10.000 Meter Höhendifferenz geschafft hat oder so etwas, was man ja eigentlich in den
21:02
Alpen nicht schaffen könnte, wenn man nur die höchste Spitze oder die höchste Höhendifferenz hernimmt. So, also es kann nicht mehr als insgesamt zwei Höhenquadrat an Erhöhungen davon passieren, weil dann sind wir an einem Anschlag. Also dieser erste Satz hier, I Relabeling
21:25
Increases Phi by One, hinter dem stehe ich nicht. Ich glaube nicht, dass der richtig ist, aber es ist egal, den kann man ersatzlos streichen, der zweite Satz ist korrekt. So, ein saturierender Push erhöht Phi um
21:45
höchstens 2n, weil was passieren kann ist, dass ein, was kann bei einem saturierenden Push passieren? Es kann sein, oder was kann überhaupt bei dem Push passieren? Es kann sein, dass ein Knoten, der vorher nicht in diese
22:01
Summe reingezählt hat, weil er nicht aktiv war, dass der plötzlich aktiv wird, weil er vorher keinen Überschuss hatte und durch diesen Push jetzt Überschuss bekommt. Kann aber höchstens 2n werden, also das Label kann höchstens 2n sein von diesem Knoten, der vorher keinen Überschuss hat und jetzt Überschuss hat, sodass also, und es betrifft nur
22:22
einen einzigen Knoten, weil wir immer nur über eine einzige Kante in jeder Iteration Überschuss weiterschieben. Das heißt also, eine Erhöhung von Phi um höchstens 2n kann bei jedem saturierenden Push passieren. Mehr kann das nicht erhöht werden. So, jetzt kommt die Gegenrechnung. Wir
22:45
für die noch keine Abschätzung haben und der Gag an der Sache ist der, das machen wir indirekt. Wir schätzen ab, um wie viel höchstens diese Westflanken insgesamt in Summe sein können. Das haben wir gerade eben gemacht.
23:02
Das ergibt uns automatisch auch eine Abschätzung der Ostflanken, wo es runtergeht, denn wenn wir bei Null anfangen und bei Null enden, dann ist die Summe von aller Höhendifferenzen hoch, gleich die Summe aller Höhendifferenzen runter natürlich. So, der entscheidende Punkt ist jetzt, dass
23:26
ein nicht saturierender Push Phi vermindert diese Potenzialfunktion und zwar um mindestens eins. Warum? Das müssen wir uns noch mal genau
23:45
anschauen, was da passiert bei einem nicht saturierenden Push. Was heißt
24:07
ein nicht saturierender Push? Das heißt, erst einmal ein Push ist sowieso nur dann erlaubt, wenn dV gleich dW plus 1 genau ist. Nur dann
24:24
dürfen wir ja Fluss über eine Kante rüber schicken. So, wenn wir nicht saturierend sind, dann heißt es, dass der gesamte Überschuss, der an V, der bei
24:47
V ist, Platz hatte durch diese Kante hindurch, um nach W zu kommen. Und das bedeutet, V wird inaktiv, hat keinen Überschuss mehr.
25:06
Damit geht dV raus aus der Summe. Hier, das ist ja die Summe über alle aktiven Knoten. dV geht raus. Kann sein, dass W vorher inaktiv war, dann kommt dV rein, aber dV ist ja um 1 Zähler kleiner als dV.
25:26
Das heißt, in Summe dV geht raus, weil es inaktiv geworden ist. Möglicherweise war dV vorher nicht drin und ist jetzt drin in der Summe, ist aber 1 Zähler kleiner. Das heißt, insgesamt in Summe ist
25:42
diese Summe um mindestens 1 kleiner geworden. Falls W schon selber inaktiv war, ist es wahrscheinlich um mehr als 1 kleiner geworden. Und damit haben wir eine Abschätzung für die nicht saturierenden
26:01
Posch-Schritte. Wir wissen, die Relabeling-Operationen können insgesamt nur 2n² viel Westflanke erzeugen, also hochgehende Schritte. Wir wissen, jeder einzelne saturierende Push kann höchstens 2n Höhenerhöhung der Potentialfunktion erreichen. Wir haben die saturierenden Push-Schritte
26:23
schon auf der letzten oder vorletzten Folie abgeschätzt nach oben. Was war das nochmal? Das war n mal m. Asymptotisch. Und wir wissen, nur so
26:42
viel wie hier Relabeling und saturierende Push-Schritte an Erhöhung gebracht haben, kann jetzt hier durch die nicht saturierenden Push-Schritte an Verminderung hineinkommen. Genau so viel. Und da jeder einzelne Iteration mindestens um 1 vermindert, ist damit die Anzahl der Iterationen
27:01
mit nicht saturierenden Push-Schritte, die Anzahl der nicht saturierenden Push-Schritte vermindert. So. Und damit ergibt sich, wir können höchstens um so viel höher werden, auch nur so und das heißt nur so und so viele nicht saturierende Push-Schritte können wir auch haben, ergibt sich insgesamt asymptotisch O von n²m. Ist doch eine interessante, finde ich
27:24
persönlich eine interessante Argumentationsweise. Geht so. Warum ich hinter diesem Satz nicht stehe? Weil potenziell, wenn wir uns den Relabeling
27:47
anschauen, hier, diese Setzung muss ja nicht das Label von v um exakt 1 erhöht haben. Es kann auch mehr als 1 gewesen sein. Ja, sonst könnte man sich auch die Zeile einfacher machen. Dann könnte
28:02
man einfach hinschreiben, erhöhe die v um 1 und fertig. Ja, also hier muss nicht 1 rauskommen im Allgemeinen und deshalb stehe ich nicht hinter diesem Satz, der behauptet, dass die Summe der Labels durch ein Relabeling
28:22
eines einzelnen Knotens um 1 erhöht wird. Gut. Wir gehen dieses Beispiel nicht durch. Das gucken Sie sich im stillen Kämmerlein an. Gehen wir zu FIFO-Prefile Push-Eier. Es geht immer in den verschiedenen Variationen
28:41
von FIFO-Prefile Push-Eier darum, die nicht saturierenden Push-Schritte nach oben abzuschätzen, unterschiedlich gut abzuschätzen. Ja, weil die Relabel-Schritte, die hat man o von n², die saturierenden Push-Schritte o von n mal m. Wir hatten irgendwo vor ein paar, letztes Mal vor ein paar Folien gesehen, die Bemerkung, dass es Beispiele gibt, dass man Beispiele
29:03
konstruieren kann, bei denen wirklich n² und n mal m erreicht wird, die eine Verbesserung hinzukriegen. Aber bei die nicht saturierenden Push-Schritte, deren Abschätzung ja viel schlechter ist, da kann man noch viel daran
29:21
rumbasteln, um möglichst weit runterzukommen. Und eine Variante, wie man da weiter runterkommen kann, ist die FIFO-Variante von Preflow Push-Algorithmen. Was wir machen ist einfach folgendes,
29:42
wir halten die Knoten in einer Q drin. So alle aktiven Knoten sind irgendwie in
30:08
beliebiger Reihenfolge, ich sollte es nicht so weit nach hinten tun, ich muss da noch ein bisschen Platz, sind in einer Q drin, in irgendeiner beliebigen Reihenfolge, in so einer FIFO-Q, wir kennen die ja. Wir nehmen den ersten Knoten
30:22
raus, den hier, versuchen so viel Fluss wie nur möglich darüber zu schicken, über diverse Kanten, wenn wir mehrere zur Auswahl haben, solange bis es nicht mehr geht. Das kann zur Konsequenz haben, dass neue Knoten, die bisher nicht
30:40
aktiv waren, jetzt aktiv geworden sind, also Überschuss bekommen haben von diesen Knoten aus, Überschuss gegangen ist an Knoten, die bisher noch keinen Überschuss hatten, die werden hinten rangehängt. Dasselbe wieder, wir nehmen uns den ersten Knoten raus, tun alles um den
31:01
Überschuss loszuwerden, wir schaffen es vielleicht oder wir schaffen es auch nicht, vollständig loszuwerden. Jetzt bekommen wir potenziell wieder neue aktive Knoten, weil Knoten Überschuss bekommen, durch den jetzt die vorher keinen hatten und so weiter und so fort und
31:24
irgendwann kommen wir dann zu denen an, sie kennen das Spielchen nicht von irgendwelchen Kinderspielen auf Kindergeburtstagen oder O-Phases Spielchen oder ähnliches, wo man eine Reihe bildet und vorne raus und hinten geht es wieder rein und oder umgekehrt und so nach und
31:43
nach geht die Reihe immer weiter. So, das ist alles, das ist die einzige Variation der ganzen Sache. Das habe ich eben gesagt. Ja, als Denkmodell, wenn
32:04
wir hier an diesem Punkt angekommen sind, macht es Sinn zu sagen, dass nur als Denkmodell, das ist nicht implementiert im Algorithmus. Ja, der Algorithmus geht stur einfach die die viel vor durch, nimmt sich immer das erst Element, aber um darüber nachzudenken, über Laufzeiten nachzudenken,
32:21
macht es Sinn das in Phasen einzuteilen und zu sagen so, wenn der ursprüngliche Inhalt der Q vollständig abgearbeitet ist, kommt eine neue Phase und wenn dieser Inhalt irgendwann mal wieder abgearbeitet ist, kommt wieder eine neue Phase und so weiter. Ja, ist einfach nur um besser
32:40
darüber reden zu können. Das steht hier im dritten Spiegelstrich. So, die Behauptung ist, dass wir da jetzt um einiges besser sind, dass wir statt N²m jetzt N³ haben. Das heißt also bei dicht besetzten Grafen mit einer hohen Kantenzahl haben wir eine echte Verbesserung in der Asymptotik. Bei
33:01
dünn besetzten Grafen, wo die Kantenzahl Größen- und Knotenzahl ist, haben wir damit nichts erreicht. Es ist gleich geblieben. So, gut, was ist
33:24
die Argumentation? In jeder Phase, wir gucken uns die Phasen jetzt mal betrachtet. Ja, bevor wir zu den Knoten wiederkommen, ist der gesamte Q-Inhalt, der ursprünglich da war, einmal abgehandelt. So, in jeder, was
33:50
man sich jetzt klar machen muss, ist, was bedeutet das? Wir haben gesagt, wir nehmen so einen Knoten her und versuchen jetzt möglichst allen Fluss raus von diesen Knoten, möglichst einen Überschuss über Kanten
34:03
hinzubringen. Was bedeutet das? Es bedeutet, wenn die erste Push schon nicht saturierend ist, dann ist schon aller Überschuss weg. Ein nicht saturierender Push bedeutet, aller Überschuss ist abgetragen. So, wenn der
34:23
erste Push schon nicht saturierend ist, ist alle Überschuss abgetragen, fertig. Wenn der erste saturierend ist, kann es passieren beim zweiten. Oder wenn der erste und der zweite und der dritte und der vierte und der fünfte und sechste Push saturierend sind, kann es vielleicht beim siebten Push ein nicht saturierender Push gehen, aber dann ist immer Ende. Ja, das ist der
34:43
entscheidende Punkt. Wenn wir einen Knoten hernehmen und versuchen, allen Fluss rauszuschicken, so viel wie möglich, dann gibt es saturierende, saturierende, saturierende Pushe, vielleicht Null, vielleicht auch eine Million und am Ende noch eine nicht saturierende Push. Vielleicht,
35:04
wenn wir es schaffen, den Überschuss ganz rauszubringen, vielleicht noch einen, maximal einen nicht saturierenden Push, der dann den Rest vom Überschuss abträgt, ohne dass die Restkapazität auf dieser Kante damit ausgeschöpft ist. So, das heißt also, in einer Phase können höchstens für jeden
35:27
Knoten einmal ein nicht saturierender Push geschehen. So, das heißt, wir können diese N hoch drei bewiesen, wenn wir zeigen können, dass die Anzahl der Phasen nur ein Quadrat ist, weil in jeder Phase kann jeder Knoten nur
35:44
einmal einen nicht saturierenden Push haben, weil dann sein Überschuss weg ist und dann ist er fertig. So, jetzt gibt es eine neue Potentialfunktion. Eben hat man die Summe aller Distanzwerte von einem Überschussknoten.
36:05
Jetzt nehmen wir das Maximum und etwas andere Argumentationen, aber sehr, sehr ähnlich. Wir stellen wieder fest, auch hier, die D-Werte sind ja alle mindestens 0 und höchstens 2n, sogar echt kleiner 2n. Also kann Phi,
36:26
das Maximum über alle D-Werte, auch nur zwischen 0 und 2n liegen. Gut, also ein ähnliches Bild, wie wir es hier hatten, nur nicht mehr mit 2n Quadrat, sondern, wenn ich das einfach mal hier korrigiere, jetzt mit 2n, weil wir nicht mehr die Summe haben, sondern das Maximum. Fällt ein Faktor n weg.
36:48
So, wenn wir jetzt, auch hier, auch hier stehe ich nicht genau hinter diesem Satz. Ich mache mal weiter. So, hinter diesem ersten Satz, in einer
37:04
Phase ohne, nee, hinter welchem, hinter diesem zweiten Satz stehe ich nicht hier. Also gehen wir noch mal zurück. Der erste Satz. Eine Phase, in der keine Relabeloperation stattfindet, ist zunächst mal eine Phase, bei der kein
37:24
Label hochgesetzt wird, kein Label manipuliert wird, aber es kann wieder passieren, dass, oder was heißt das, dass kein Relabel passieren muss. Das heißt, es braucht kein Relabel passieren, weil sämtlicher Überschuss
37:44
von sämtlichen Knoten weiter geschickt worden sein konnte. Ja, dann muss kein Relabel passieren. Und dann haben wir wieder dieses Argument, was wir schon vorher hatten, was ich leider aber nicht mehr an der Tafel halten konnte, aus Platzgründen, nämlich das Argument, dass wir ja immer
38:23
nur von V nach W um ein, egal, W i sag ich mal, W 1, W 2, W 3 und so weiter,
38:42
dass wir immer diese Gleichung haben, dass wir nur dann Fluss rüber schicken, wenn das erfüllt ist, wenn das Gefälle gerade passt und das bedeutet, wenn dieser dieser Knoten ohne Relabel heißt, eine Phase ohne Relabel heißt, jeder der Knoten, die angefasst worden sind, kriegt seinen Überschuss weg hier und
39:05
dieses D, dieser D-Wert fällt weg, weil dieser Knoten nicht mehr aktiv ist, nur die die Werte, die D-Werte bleiben. Ja, sämtliche Knoten, die waren erfolgreich, den Fluss weiter zu schicken, um ein Wert, um ein
39:24
Höhenwert runter, das heißt, die maximalen Knoten, die maximalen Höhenwerte, von denen wir runter geschickt haben, was vorher maximal ist, die Knoten, bei denen vorher dieses Maximum angenommen worden ist, die sind alle aus dem Spiel und die neuen maximalen Knoten sind
39:41
höchstens, sind mindestens eins kleiner. Das steht hier, das ist das, was hier steht. So, hier hinter diesem Satz stehe ich nicht hundertprozentig, ist auch nicht notwendig. Was letztendlich benötigt wird, ist das, was hier unten steht. Sämtliche Phasen mit Relabel-Operationen zusammen
40:07
können phi höchstens um 2n² erhöhen. Mehr als das brauchen wir hier auch nicht. So, die Anzahl der Phasen, in denen wir ein Relabeling
40:21
haben können, ist höchstens 2n². Und die Phasen, die kein Relabeling haben können, das sind die hier, wo jeweils wir mindestens einen Schritt auf der Ostflanke machen, runter, können auch 2n² höchstens
40:40
sein. Insgesamt ergibt sich n² viele Phasen. Vielleicht ein bisschen starker Tobak, aber wenn Sie sich danach noch damit auseinandersetzen, glaube ich, insbesondere wenn Sie dann die Videoaufnahmen hoffentlich endlich dann haben, werden Sie, denke ich, wird das gar nicht so schwer
41:04
zu verstehen sein, wenn man das erst mal durchgestiegen ist. So, es ist immer dieselbe Argumentation. Wir haben auf der einen Seite bestimmte Operationen, die das phi hochtreiben, aber von denen wissen wir,
41:22
dass es nicht beliebig hochgehen kann. Und die Operationen, die wir abschätzen wollen, die treibt das phi immer runter. Und wir wissen, wenn es nicht beliebig hochgetrieben werden kann, kann es auch nicht beliebig häufig runtergetrieben werden. Und am Ende ist es Null.
41:42
So, damit haben wir das, FIFO, schon erledigt. Und wir kommen zu einer anderen, meines Erachtens sehr interessanten Idee. Die Grundidee von diesem Excess Scaling Variante ist, auch das ist eine Technik, die, ich glaube, wirklich hier zum ersten Mal eingeführt worden ist, die aber in vielen, vielen Stellen inzwischen verwendet
42:04
wird, weil sie einfach auch eine sehr natürliche logische Sache eigentlich ist. Die Idee ist, ich meine, wie gehen Sie heuristisch an irgendwas ran? Es gibt verschiedene Möglichkeiten, also irgendeine Problemstellung zu lösen. Sagen wir beispielsweise
42:24
irgendwelche Möbelstücke in einen Möbelwagen reinzutun. Wie gehen Sie da ran? In einer ersten Phase packen Sie die großen, dicken, schweren Möbelstücke rein. Und wenn Sie davon keine haben, dann nehmen Sie die mittelschweren und wenn Sie davon
42:40
keine mehr haben, dann nehmen Sie die leichten und am Ende kommen dann die Kinkerlitzchen. So würde man das machen. Nicht nur, damit die Kinkerlitzchen oben und die schweren Möbel unten sind, sondern Sie würden es auch dann machen, wenn es keine Probleme dieser Art gibt, weil Sie erst einmal, wenn Sie die großen, schweren Sachen mit
43:01
Überlegung in überschaubarer Größe, überschaubarer Anzahl verstaut haben, dann wird sich das mit den kleineren Sachen schon irgendwie packen lassen. Das wird schon klappen. Und das ist die Idee hier, dass wir zuerst nur die
43:20
Überschüsse weiterschicken, die groß sind, die richtig über Schuss haben und uns um kleine Überschüsse gar nicht kümmern und dann erst, wenn die so weit erledigt sind, dann gehen wir einen Schritt weiter, sorgen immer dafür, dass die Überschüsse nie ernsthaft größer werden. Wenn die
43:44
großen Überschüsse erledigt sind, dann gehen wir in die nächste Phase, nehmen die Überschüsse von der nächst kleineren Größe sozusagen und bearbeiten die, sorgen dafür, dass es keine, dass sie nirgendwo keine richtig großen Überschüsse wieder auflaufen. Es macht ja keinen Sinn, dass sie sämtliche Kinkerlitzchen so zusammenpappen
44:04
als Überschuss, dass das Ganze genauso groß wird wie ein großes Möbelstück, sondern dass sie die wirklich als Kinkerlitzchen dann verteilen und so weiter, bis sie am Ende gar nichts mehr haben, bis die Größe, die sie
44:23
betrachten, kleiner ist als die Größe der Kinkerlitzchen, die sie haben. Da gehen wir direkt zum Algorithmus. Wir gehen direkt zum Algorithmus, weil die Sachen, die dort jetzt vorher erklärt stehen, die erkläre ich Ihnen jetzt
44:42
auch mündlich, also brauchen wir sie nicht noch mal durchzugehen, aber dafür haben sie es trotzdem schriftlich, wenn sie es später damit befassen. So, wie das übliche. Wir haben gerichtet in Grafen D. Jetzt ist es nicht wirklich wichtig, aber schon sehr nützlich, dass wir ganzzahlige Kapazitäten haben. Nehmen wir jetzt als
45:02
gegeben hin. Sie wissen ja, es ist keine Einschränkung der Allgemeinheit von ganzseiligen Kapazitäten auszugehen. Source und Target natürlich. Und was wir wollen, ist wie üblich ein Maximalfluss von S nach T. Wir fangen wieder an mit dem üblichen, dass wir den Fluss initialisieren mit Null, dass wir die Distanzlabel
45:25
erst einmal vorberechnen, als die echten Distanzen von jedem Knoten nach T. Das ist nichts Neues. Das war bei allen bisherigen Varianten von Preflopush genau dasselbe. Auch das ist nichts Neues. Diese Zeile ist exakt dieselbe. Alle Kanten,
45:44
die aus S rausgehen, da setzen wir den Flusswert auf den Anschlag, sodass wir dann den ersten saturierten Schnitt haben, dass von S nach T tatsächlich kein Fluss erhöhender Pfad geht. Setzen wir die Höhe von S ist N. Die Höhe von T
46:03
ist Null, weil die D-Werte im Schritt 2 korrekt berechnet worden sind und die Entfernung von T zu T ist natürlich Null. Und hier ist jetzt die Größe, von der die Rede ist. Und Sie sehen schon durch diese merkwürdige Konstruktion. Was
46:22
ist denn das? In Worten. Damit meine ich jetzt nicht, das ist in Worten zu sagen, das ist zwei hoch obere Gaussklammer. Das meine ich nicht. Was ist die Semantik dieses Ausdrucks? Groß u war die größte die größte Kapazität.
46:51
Nein, was steht, was ist diese, was bedeutet diese Formel hier auf der rechten Seite? In
47:05
Worten. Genau. Die nächste höhere Zweierpotenz über dem höchsten Kapazitätswert von irgendeiner Kante. Und Sie sehen schon, das hat jetzt jemand gesagt, ich weiß nicht mehr wer, worauf das hinauslaufen wird. Wir werden selbstverständlich dann das. Diesen
47:21
nächste Potenz machen wir immer dann, wenn wir schrittweise halbieren. Damit wir dann immer eine ganze Zahl haben, bis wir dann bei 1 angekommen sind. Und danach, da wir ganze Kapazitäten haben, nachdem wir den Fall Delta gleich 1 abgehandelt haben, ist nichts mehr zu tun. So, da sehen Sie,
47:46
dass die weil das wir, wir haben eine Weilschleife drumherum gelegt. Vielleicht mal ganz kurz spicken. Sie sehen, weil Delta Größe gleich 1, Delta gesetzt, Delta halbe. Das ist die Struktur. Wir haben eine Weilschleife drumherum
48:00
gesetzt, wo wir in jeder Iteration eine bestimmte Delta Größe jeweils betrachten. Und im Prinzip ist das, was da drin ist, der generische Prifel-Push-Algorithmus wie davor, nur mit einer kleinen Unterscheidung hier bei der Formel fürs Push. Und bei der Ausfall hier. So, wir
48:23
suchen uns einen aktiven Knoten. Hier steht with large excess mit hohem Überschuss. Das bedeutet einfach mindestens die Hälfte von Delta. Ja, wir gucken uns immer nur die Überschüsse an, die mindestens Delta halbe groß sind. Ja, wir wissen, sie
48:42
sind höchstens Delta groß. Das ist am Anfang klar, weil wir das Delta am Anfang so gesetzt haben, dass das dann nichts anderes passieren kann. Also, dass wir da nie was verschieben können, was mehr als Delta ist. Und wir werden dafür sorgen, dass wir
49:01
auch später nie mehr als das jeweils aktuelle Delta irgendwo als Überschuss erreichen. Das wäre also wenn wir einen Bereich zwischen einem Delta und einem zugehörigen Delta halbe erledigt haben und dann einen Schritt runter gehen mit halbiertem Delta, dass wir nie wieder Überschuss erzeugen
49:21
zwischendurch, der dann in einem alten Bereich drin ist. Ja, das wäre ja witzlos, sondern wir wollen diese Größenordnung zwischen Delta und Delta halbe wollen wir einmal erledigen und danach gucken wir uns nur noch kleinere Größenordnung an. Wir müssen aber dafür sorgen, dass wenn wir uns kleine Größenordnung angucken, nie wieder ein Überschuss passiert in dieser Größenordnung.
49:43
So, wir nehmen uns also Knoten, einen aktiven Knoten, also einen Überschussknoten mit großem Überschuss her, mit mindestens Delta halbe. Nicht irgendeinen, sondern einen speziellen, nämlich einen unter denen einen mit kleinsten D-Wert. Das hat einen
50:04
Grund, auf den wir noch zu sprechen kommen werden, warum es jetzt nicht irgendein beliebiger Knoten mit großem Überschuss ist. So, und was wir jetzt machen, ist hier dasselbe wie vorher. Falls wir eine admissible arc
50:23
haben, exakt dasselbe wie vorher, dann schicken wir einen bestimmten Flusswert rüber, ansonsten machen wir eine Label. Nur der Flusswert, den wir rüber schicken, der hat sich noch ein bisschen eingeschränkt, so wie bisher auch. Nicht mehr als der Überschuss, der an dem Knoten dran ist. Es wird nicht mehr Überschuss weiter gereicht, als
50:40
an dem Knoten dran ist. Natürlich nicht mehr als Restkapazität auf der Kante ist, über die wir Fluss rüber schicken. Diese beiden Argumente der Minimumsbildung waren vorher schon drin. Jetzt kommt ein neues Argument hinzu, dafür zu sorgen. Wir müssen natürlich dafür sorgen, dass das, was an Überschuss an den Knoten, wo es hinkommt, akkumuliert wird, dass es nicht größer ist als das D.
51:02
Das ist das, was ich eben gesagt habe. Wenn wir einmal einen Bereich von Überschussgrößen zwischen D halbe und D verlassen haben und dann zu D Viertel, D halbe übergehen und D Achtel, D Viertel und so weiter, das wird dann nie wieder ein Überschuss erzeugen, der in den Bereich D halbe D, Delta halbe Delta
51:22
ist. Und deshalb, das müssen wir hier eingrenzen, damit auch der Überschuss bei diesen Zielknoten nicht größer als Delta wird, dass höchstens Delta minus dem aktuellen Überschuss höchstens das verschoben wird. Und das ist die ganze Änderung. Das machen wir
51:41
eingekleidet in diese große Weilschleife. Für jeden Delta Wert beginnt bei dem hier, bei dem ersten, bis wir bei eins gelandet sind. Einmal. Das heißt, wenn ich das jetzt als Delta hernehme, wenn ich sage, das ist das Delta, dann
52:00
heißt es zuerst, der Bereich Delta halbe Delta wird betrachtet, Überschüsse in dem Bereich, dann Delta Viertel, Delta halbe, dann Delta Achtel, Delta Viertel, dann Delta Sechstentel bis Delta Achtel und so weiter und sofort. So was wissen wir jetzt über diesen Algorithmus?
52:22
Zunächst einmal wissen wir, dass jeder nicht saturierende Push, sie ändern sich, es geht immer vor allem um die Abschätzung der nicht saturierenden Push-Schritte, weil die Label-Schritte und die saturierenden Push-Schritte, die hat man so gut im Griff von Anfang an, von unserer ersten Betrachtung an, für den
52:40
generischen Algorithmus schon, die hat man so gut im Griff, wie man sie überhaupt noch haben kann. Also gucken wir uns immer die nicht saturierenden Push- schritte an und was wir erstmal feststellen, ist, dass jeder nicht saturierende Push-Schritt eine mindestens Delta halbe Einheiten rüberschickt. Warum? Wenn er nicht saturierend ist, wenn, wenn der Push-Schritt nicht saturierend ist, dann ist
53:01
die Restkapazität nicht der Flaschenhals, sondern entweder ist E von V der Flaschenhals oder Delta minus E von W. Aber,
53:22
Entschuldigung, aber das hier ist größer Delta halbe und das hier ist auch größer Delta halbe und deshalb fließt mindestens Delta halbe rüber. Und wir haben dafür gesorgt durch dieses dritte Argument, was ich eben schon gesagt hatte, dass wir niemals wieder
53:40
über die Delta rüber, über das Delta rüber kommen mit dem Überschuss. So, jetzt ist die Behauptung, die Anzahl der nicht saturierenden Pushes pro Phase, pro Scaling-Phase, aber also für jedes Delta,
54:00
ist ein Quadrat. Und wie viele Phasen haben wir? Natürlich logarithmisch viele, ja, damit quäle ich immer die Studierenden GDI 2 mit dem Logarithmus, ja. Schrittweise Halbierung bedeutet logarithmische Tiefe. Ist bekannt.
54:21
Also kommt die Anzahl der Scaling-Phases das Logarithmus von U und höchstens n Quadrat viele nicht saturierende Pushschritte. Und das müssen wir jetzt noch beweisen. Ja, das steht jetzt erst mal da. Das müssen wir erst mal beweisen, dass in jeder Scaling-Phase
54:40
höchstens n Quadrat viele nicht saturierende Pushschritte passieren und noch eine schöne Potenzialfunktion, diesmal noch eine etwas hübschere. Also sehen, damit kann man eine ganze Menge anfangen, nicht nur bei Max Flow, auch ganz allgemein, wenn sie, dass sie eine Funktion finden. Sie haben verschiedene Arten von Schritten im Algorithmus.
55:01
Die eine Art von Schritten, die haben sie gut unter Kontrolle, was die Worst-Case-Komplexität angeht. Die andere wollen sie unter Kontrolle kriegen. Und wenn sie schaffen, eine Funktion zu basteln, sodass die einen die Funktion hochtreiben und die anderen die Funktion runtertreiben, dann kriegen sie damit auch diese,
55:22
diese andere Art der Schritte unter Kontrolle. Das ist die Grundidee. So. Das ist die Potenzialfunktion. Was passiert da? Wir summieren über alle Knoten diesen Wert jeweils aus und dieser Wert ist ein bisschen,
55:42
das kann man auch ein bisschen transparenter formulieren, diese Formel der Potenzialfunktion. Was die eigentliche Idee ist, kommt vielleicht besser raus,
56:00
wenn ich so schreibe. E v durch Delta mal d von v. Ja, die beiden, das sind die Überschussgrößen, die hängen natürlich zusammen. Und das hier ist immer kleiner gleich eins. Und da wir nur die die large,
56:21
die großen Überschüsse betrachten, ist es mindestens größer, ist es mindestens eineinhalb dieser Quotient hier. So. Gut, das haben wir eben schon gesehen. Logarithmus von u viele Scaling Phasen.
56:42
Diese Funktion Phi, die Sie da einfach mal vom Himmel gefallen als gegeben annehmen, die ist größer gleich null. Sämtliche sämtliche Werte hier sind größer gleich null.
57:00
Also das gesamte Phi größer gleich null. 2 n, Phi ist kleiner gleich 2 n Quadrat. Da geht das ein, was ich hier aufgezeichnet habe, dass dieser Quotient immer kleiner gleich eins ist. Das heißt also, wenn Sie in Gedanken e von v geteilt durch Delta durch eins ersetzen, bleibt wieder die Summe dv übrig. Hatten wir schon gesehen, dass die höchstens
57:21
2 n Quadrat ist. So. Jetzt wird es ein bisschen komplizierter. Eine Relabeling-Operation,
57:42
die einen dieser D-Werte um irgendwas erhöht, ein bisschen unglücklich, dass hier ein Epsilon steht. Bei Epsilon denke ich zumindest immer an was sehr kleines. Ist hier vielleicht schlecht. Denken Sie also ausnahmsweise mal nehmen Sie Epsilon hier bitte für eine natürliche Zahl.
58:06
Kennen Sie auch den kürzesten Mathematiker jetzt? Sehr Epsilon kleiner null. So, wenn wir, wenn ein Relabeling-Operation
58:21
den D-Wert um irgendwas erhöht, dann kann auch diese gesamte Phi-Funktion hier nur um diesen Wert erhöht werden. Denn E von V ist kleiner gleich Delta. E von V geteilt durch Delta ist kleiner gleich eins. Das heißt also, Phi können wir auch hier wieder nur
58:41
insgesamt um höchstens 2 n Quadrat erhöhen. Über alle, sogar über alle Scaling-Phasen hinweg. Da kommt nicht mal das Logo Atmos U als Faktor noch dazu. Also die Erhöhungen von Phi dieser Funktion durch Relabeling-Operationen sind wieder mal schön. Die Westflanken sind mal schon wieder
59:04
erhöht. Sind wir hier mal schön begrenzt. So, jetzt ist ein bisschen andere Situation als vorher, wo immer die saturierenden Schritte, Push-Schritte ebenfalls die Funktion erhöht haben. Hier ist es sogar bequeme Situation, die das sämtliche Push-Schritte saturierend oder nicht saturierend
59:22
Ostflanken bilden, also wo Phi runtergeht. Warum? Das liegt an, hier kommt jetzt der Punkt ins Spiel, wo ich gesagt habe, dazu kommen wir noch. Hier in
59:41
Zeile 6. Wir nehmen nicht irgendeinen Knoten her, mit großem Überschuss, sondern einen unter allen Knoten mit großem Überschuss, einen, der, der, der kleinste, kleinstes D-Wert hat. Ja, das bedeutet,
01:00:03
noch mal zur Erinnerung, jetzt muss ich aber noch mal hier was Platz machen.
01:00:25
Das bedeutet, Sie erinnern sich, wir schieben Fluss immer rüber, nur wenn die Bedingung erfüllt ist, ich reite immer wieder drauf rum, dass das so gilt
01:00:41
und das bedeutet, wenn wir das minimal gewählt haben, V gewählt haben, sodass D von V unter allen Knoten mit großem Überschuss, mit Überschuss mindestens Delta halbe, unter allen diesen Knoten der minimalen D Wert hat, dann bedeutet das, dass W
01:01:02
keinen Large Excess hat. So haben wir V gerade gewählt. Deshalb ist hier in dieser, bei dieser Minimumsbildung in Zeile 7
01:01:21
hat kein Large Excess, deshalb können wir hier auch mindestens Delta halber rüber schicken, wenn das hier der Flaschenhals ist, Delta minus E von W. Das hatte ich vorhin gesagt, ich hatte versäumt zu begründen, warum das ist, aber da Sie alle das anscheinend geschluckt haben, habe ich dann auch die Begründung verschoben bis jetzt, wo ich eh auf das Thema zu sprechen komme.
01:01:43
Kein Large Excess, das heißt, jetzt muss ich noch mal gucken,
01:02:01
wo sind wir hier stehen geblieben, ach nee, nur dort, wo ich es eben gesagt habe, nur dort war die Begründung notwendig, hier ist die Begründung gar nicht notwendig, sondern hier gibt es sich automatisch, wenn ich,
01:02:21
hier gibt es sich automatisch aus dieser Bedingung, dV gleich dW plus 1, ohne die ganze Sache, die ich dazu gesagt habe, das war nur notwendig für die andere Stelle, aber hier ist es nur notwendig dV gleich dW plus 1, denn das bedeutet, dass Überschuss von V, wenn das nach W geht,
01:02:41
dann geht es zu einem von einem Knoten mit Wert dV, zu einem Knoten mit Wert dV minus 1, das heißt, dementsprechend wird V reduziert. So, hatten wir festgestellt, ein nicht saturierender Push sendet
01:03:02
mindestens delta halbe Einheiten, dafür brauchten wir diese Argumentation, dass W kein Large Excess hat, dass das garantiert gesichert ist, dass das mindestens delta halbe Einheiten sind, was dann eben entsprechend ergibt,
01:03:22
um mindestens 0,5 wird das V vermindert. Gut, das ist nochmal die Argumentation, dass in jeder Scalingphase das höchstens so hoch gehen kann.
01:03:44
Und wenn es höchstens so hoch gehen kann und auf der anderen Seite die nicht saturierenden Push-Schritte so viel schon wieder vom Runter-G-Potenzial aufgefuttert haben, bleibt dann so viel vom Runter-G-Potenzial übrig für die nicht saturierenden Push-Schritte.
01:04:02
Nee, umgekehrt, eher falsch rum, ja. Wenn jeder mindestens um 0,5, Entschuldigung, falsch, wenn jeder nicht saturierenden Push-Schritt mindestens 0,5 Einheiten das V vermindert, dann heißt das,
01:04:21
hier im Zähler ist das, um was es höchstens erhöht werden kann insgesamt. Jeder einzelne Schritt muss es um mindestens 0,5 vermindern. Das heißt nur so viele Schritte bleiben insgesamt übrig, die nicht saturierende Push-Schritte sein können. Und damit haben wir die Behauptung bewiesen, dass es quadratisch viele sind.
01:04:43
So, es fehlt noch was. Ich hab noch was unterschlagen, beziehungsweise die Folien haben was unterschlagen und ich hab's mit unterschlagen. Wie kriegen wir diese Distanz-Label? Gehen wir nochmal zurück zum Algorithmus. Hier. Von allen aktiven Knoten
01:05:01
mit großem Überschuss, mindestens delta halb Überschuss, wählen wir einen Knoten aus, der einen kleinsten D-Wert hat. Von allen denen. Jetzt müsst ihr Alarmglück geschrien. Achtung, da braucht man wieder aufwendige Datenstrukturen, Parallel-EU und so weiter. Das kostet wieder mindestens einen logarithmischen Faktor obendrauf oder so.
01:05:21
Aber die Behauptung ist hier, dass da kein logarithmischer Faktor noch obendrauf kommt. Sondern, wie wir das gemacht, ähnlich wie wir das schon mal in anderer Situation hier irgendwann am Anfang der Vorlesung hatten, in einem der ersten Termine, da ging's um, worum ging's denn da, um kürzeste Pfade,
01:05:54
dass wir ein Array haben,
01:06:02
0, 1, 2, mit den typischen Indizes mit 0 beginnt und dass wir in jedem i uns speichern, sämtliche Knoten speichern, die großen Überschuss haben, also die in irgendeine Frage kommen
01:06:22
und deren D-Wert gerade i ist. Und dann können wir erst einmal von links nach rechts durchgehen, um zum ersten zu kommen. Entscheidender Punkt ist jetzt der, ich muss immer wieder drauf rumreiten, wenn wir tatsächlich irgendwo, wenn irgendwo tatsächlich was passiert,
01:06:43
also entweder es gibt ein Re-Label, dann geht's weiter, dann wandert dieser Knoten weiter nach rechts, steuert uns nichts weiter auf unserem Weg von links nach rechts, kommen wir halt später an ihm vorbei, aber wir verpassen ihn nicht. Was aber passieren kann, ist, dass ein Knoten plötzlich großen Überschuss bekommt,
01:07:02
der kleiner ist als dieses Label, also linker Hand ist, und wenn wir jetzt stur immer rechts weiter gehen, dann würden wir den verpassen. Die Idee ist, stur von links nach rechts durchzugehen, einmal durchzugehen und dann nie wieder, das ist die Grundidee,
01:07:21
aber ganz so einfach kann es nicht gehen mit Re-Label-Schritten, wenn das die einzigen Schritte wären, die D-Werte ändern, dann wäre das kein Problem, dann kommen wir halt später bei dem Knoten nochmal wieder vorbei, aber es kann passieren, dass plötzlich dieser Knoten, der vorher nicht in dem Array drin war, jetzt rein gehört ins Array,
01:07:41
weil er nämlich großen Überschuss bekommt, den er vorher nicht hatte, aber weil dV gleich dW plus eins ist, das ist das worauf ich immer wieder rumreite hier in dem Kapitel, wissen wir, wenn so ein Knoten passiert, wo wir ihn zu suchen haben, nämlich gerade eins links zurück. Das heißt also, unser Zeiger geht in der Generaltendenz von links nach rechts,
01:08:04
aber jedes Mal, wenn es ein Push möglich ist, wenn Re-Label passiert, dann geht dieser Knoten weiter, aber der Zeiger bleibt hier, wenn aber ein Push passiert, dann geht der Zeiger wieder eins links zurück, und wenn von da aus wieder ein Push möglich ist, geht er halt dann wieder eins nach links zurück,
01:08:20
und wenn da und so weiter, wenn Fluss bis nach T gereicht werden konnte, dann wandert er heim auf diese Art und Weise zurück. Haben Sie irgendwo mal die Turing-Maschine gesehen? Sie können das mit dem Band immer hin und her gehen. Daran erinnert mich das irgendwie, dunkel. Und auf die Art und Weise können Sie,
01:08:46
bis auf den einmaligen Aufwand, dass wir das doch einmal durchschaffen, von links nach rechts, insgesamt können Sie die Anzahl der Schritte, wie das weitergeht,
01:09:01
begrenzen durch die Anzahl der Push-Schritte, und damit sind Sie in der asymptotischen Komplexität drin, die Sie sowieso haben. Sie kriegen keine asymptotische Komplexität obendrauf. Was man so alles mit Frickelkramdatenstruktur machen kann.
01:09:21
So, damit sind wir mit Excess Scaling insgesamt fertig. Das ist nichts anderes als das, was ich eben gesagt habe hier. Nur noch als als Feststellung zum Schluss, dass das die Laufzeit des Algorithmus ist.
01:09:41
n mal m plus n² log u für Graphen, für Instanzen, für Eingaben, die dünn besetzt sind, wo die Kantenzahl in der Größenung der Knotenzahl ist, und wo die Kapazitäten auch nicht brutal hoch sind, sind wir praktisch quadratisch auf einmal.
01:10:02
Quadratisch in der Anzahl der Knoten. Das ist doch schonmal ordentlich, oder? Haben wir es schon gut weit runtergekriegt. Zu den Kapazitäten, wenn Sie sich vorstellen, reale Netzwerke mit Kapazitäten,
01:10:22
also typischerweise haben Sie ja bei Kapazitäten irgendwie bestimmte Größenordnung. Sie haben eine Kapazität von 10, eine Kapazität von 20, eine Kapazität von 30 ausgelegt. Ich fabuliere nochmal. Das bedeutet, dass Ihr Groß-U ist 3. Weil Sie den größten gemeinsamen Teiler nehmen können.
01:11:00
In der Realität reden wir von relativ kleinem U. Das ist jetzt nicht unbedingt 3, aber vielleicht genauso wie bei den Distanzen, die wir betrachtet haben, wenn Sie Navi-Distanzen betrachten. Von welchen Größenordnung reden Sie denn? Selbst wenn Sie gesamtes Kartenmaterial bis Singapur und Kapstadt haben,
01:11:22
reden Sie von Distanzen von höchstens 15.000 Kilometern insgesamt in Granularität 100 Meter. Das sind auch nur 150.000. Ja, das ist noch, gemessen an der Gesamtgröße des Netzes, was Sie da an Knoten und Kanten haben, ist das läppisch.
01:11:45
So, ob das jetzt wirklich eine Verbesserung ist, dieser Algorithmus, den Ahuja Orlin und Tarjan da vorgeschlagen haben, darüber gehen die Meinungen durchaus ein bisschen auseinander.
01:12:00
Also generell ist es so als Faustregel, wenn ein Algorithmus eine Aufwandsabschätzung hat, die schwierig ist, dann ist dieser Algorithmus meistens auch schwierig zu implementieren. Und schwierig zu implementieren heißt, wenn Sie ihn doch implementieren, ist die Wahrscheinlichkeit groß, dass Sie Fehler dabei machen, die Sie dann irgendwie langwierig ausbügeln müssen.
01:12:25
So, was kann man noch alles machen? Hier, das ist jetzt ein Punkt, sehe ich das richtig? Ja, das ist ein Punkt, zu dem ich nicht allzu viel sage, weil es eine Übungsaufgabe ist.
01:12:42
Ich will nur den einen Punkt, die Illustration des Ganzen, sagen. Die Intuition, die dahintersteht und alles andere, fregeln Sie bitte selber raus.
01:13:12
Ich hatte ja auch heute, nicht zum ersten Mal, so ein Bild gezeichnet, wie man sich so die Situation vorstellen kann.
01:13:21
Natürlich nicht einfach so baumartig, sondern das kann durchaus irgendwie so alles aussehen. Überall kann es Überschuss geben. Auch mittendrin gibt es mal Überschuss. Natürlich hier an den Enden gibt es Überschuss. Das ist so meine Intuition, wie so ein Schnappschuss vom Präfektbüsch-Algorithmus aussieht.
01:13:42
Dass es eben so wie eine Flüssigkeit von S nach T ausfließt, dass es sich da durch sämtliche Ritzen im Grafen hindurch vorwärts bewegt. So, und ich hatte auch gesagt, naja, früher oder später wird der Algorithmus,
01:14:04
wenn diese Überschussknoten, wenn der Fluss nicht mehr bis T weiter gereicht werden kann, weil dazwischen eine Barriere ist, ein Flaschenhaltschnitt, und aller Fluss, der darüber gehen kann, ist schon rübergegangen, dann wird das früher oder später, wenn diese Überschussknoten alle so hoch labelt werden,
01:14:24
dass sie höher sind als S, und dann wird der Fluss rückwärts zurückfließen. Das geht auf jeden Fall, weil ja hier, mindestens auf diesen Wegen, kann der Fluss rückwärts gehen. Aber das wird der Algorithmus nicht unbedingt machen. Der wird potenziell den Fluss nicht hier auf demselben Weg wieder zurückbringen,
01:14:45
sondern der wird vielleicht einen anderen Weg wählen, so hier lang, und hier vielleicht weitergehen, und dann bleibt hier ein Zykel übrig. Ja, das Ergebnis kann Kraut und Rüben aussehen.
01:15:02
Und die heuristische Idee, um die es auf dieser Folie und auf der nächsten Folie geht, ist, dass wir das eben gerade nicht zulassen, sondern, dass wir den Algorithmus zwingen, durch eine kleine Modifikation, dass er immer nur auf den Kanten wieder, wenn es soweit ist, dass der Fluss zurück nach S fließen muss,
01:15:23
was wir an der Labelhöhe erkennen, dass es mindestens so hoch wie S geworden ist, dass er dann wirklich nur Kanten verwendet zum Rückfließen lassen, über die der Fluss tatsächlich gekommen ist, also Rückwärtskanten.
01:15:42
Das ist die Idee hier dabei. Und das Ganze ist leider nicht ganz so einfach zu beweisen, dass das Ganze wirklich funktioniert. Da muss man ein bisschen hier mit den steilen Kanten argumentieren,
01:16:01
aber wie Sie das sehen, das Ganze ist eine Übung, dem will ich hier nicht vorgreifen. So, eine weitere heuristische Verbesserung ist halt,
01:16:22
also das ist nur eine heuristische Verbesserung, damit kriegt man keine bessere Worst-Gaze-Komplexität hin, aber man kriegt in der, die Praxis sagt, Experimente sagen, dass es tatsächlich den Algorithmus in der verbrauchten CPU-Zeit beschleunigt. Eine weitere Sache ist, wir haben ganz am Anfang des Algorithmus
01:16:44
die echten Distanzen von jedem Knoten nach T gesetzt als D-Werte und danach haben wir es eben laufen lassen mit Relabel und Bush. Diese heuristische Verbesserung hier besagt, dass man hin und wieder mal,
01:17:03
vielleicht wenn m die Kantenzahl ist, vielleicht alle 10m mal oder alle 100m mal oder vielleicht nur alle 2m mal, weiß ich mal, immer mal wieder zwischendurch die Distanz-Labels auffrischt, dass man sagt, okay, für die jetzige Situation berechnen wir wieder
01:17:23
die Distanzen, die Anzahl der Kanten, die man braucht, um von jedem Knoten nach T einen Fluss erhöhen zu kommen, also mit Restkapazitäten, oder wenn das nicht mehr geht, wenn das Label schon so hoch ist, also wenn klar ist, dass es nicht mehr nach T gehen kann, dann eben n plus die Distanz nach S zurück.
01:17:49
Also die Knoten hier auf der Seite, die Überschuss haben, da berechnen wir dann die echten Distanzen nach T und die Knoten auf der Seite, die so hohe Distanzwerte haben,
01:18:05
mindestens n, dass klar ist, da kann kein Fluss mehr rübergehen nach T, die setzen, da gucken wir, was ist die minimale Distanz nach T zurück in der Anzahl der Kanten, Fluss erhöht, und das setzen wir als neue D-Werte hier hin.
01:18:23
Er gibt wieder ein valid Labeling, das hatten wir schon mal nur für diese Seite nachgeprüft, dass das so ist, das gilt natürlich für die Seite genauso, können Sie, wenn Sie wollen, noch mal im Stellenkämmerlein nachprüfen, aber es ist identisch. Das heißt also, dass wir zwischendurch einfach mal ne kurze Phase einschieben, wo wir alle Label so hochsetzen,
01:18:46
wie wir wissen, dass sie auf jeden Fall gesetzt, dass wir sie setzen können, ohne dass wir was falsch machen. Ja, ich hatte ja eingangs gesagt, diese D-Werte sind in gewisser Weise eine faule Version, eine lazy Version der echten Distanzen nach T
01:19:08
und was man tun kann, ist einfach zwischendurch, dass man wieder die Werte alle so hochsetzen, wie die echten Distanzen sind, und dann wieder weiterzumachen. Wenn man das nicht allzu häufig macht, dann bleibt der Gesamtaufwand in der asymptotischen Komplexität drin,
01:19:23
die man sowieso schon hat, dann verändert das die asymptotische Komplexität nicht. Das ist das, was hier gesagt wird. Sonst alle sonst so oft mal zehnmal Anzahl der Kanten oder hundertmal Anzahl der Kanten mal diesen Zwischenschritt einschieben, um mal wieder die Distanzlabel alle ein bisschen hochzutreiben
01:19:42
und einfach ein bisschen Aufwand zu sparen, dass diese Distanzlabel unnötigerweise also nach und nach und Schritt für Schritt hochgetrieben werden. Letzte, glaube ich, Verbesserung geht direkt wieder auf dieses Bild.
01:20:05
Es schreit ja fast danach zu sagen, okay, wir machen zwei Phasen daraus. In der ersten Phase versuchen wir so viel wie möglich Fluss von S nach T zu schicken. Und wenn wir feststellen, es geht nichts mehr, dann machen wir mit der ersten Phase Schluss
01:20:23
und schicken dann so viel wie möglich Fluss wieder nach S zurück. Das ist in der jetzigen Version, in der bisherigen Version vom Privelpush-Algorithmus nicht so in Phasen getrennt, sondern das ist so ein bisschen Kraut und Rüben. Von manchen Knoten wird noch versucht nach T weiterzuschicken, bei anderen geht es schon wieder nach S zurück,
01:20:41
je nachdem wie hoch die Distanzlabel sind. Die Idee ist hier wirklich einen echten Schnitt zu machen, erst alles nach T und wenn dann nichts mehr geht, dann alles nach S. Wie geht das? Zunächst einmal in der ersten Phase betrachten wir nur die Knoten, die noch unter der Höhe von S sind, also die noch Kandidaten sind,
01:21:04
wo der Überschuss vielleicht bis T kommen kann. Und wenn diese Knoten beendet sind, dann gehen wir in die zweite Phase. Wenn es keinen Knoten mehr gibt, dessen Höhe kleiner als N ist,
01:21:25
dann haben wir mehrfach gesagt, das ist unser Indikator dafür, dass es keinen zusätzlichen Überschuss mehr nach T geschickt werden kann.
01:21:44
Und dann gucken wir uns an, schmeißen sämtliche Knoten raus, die auf der T-Seite sind hier, die sind alle nicht mehr aktiv. Weil wenn sie aktiv wären, hätten sie ein Label kleiner als N. Die können wir rausschmeißen und alle anderen Knoten, die lassen wir drin
01:22:07
und von denen schicken wir wieder den Fluss nach S zurück. Drehen das sozusagen um, wie ich das eben gesagt habe, nehmen jetzt S als die Senke her, nicht mehr T, sondern S ist die Senke,
01:22:21
berechnen von da aus die Distanzwerte zurück und machen dann dasselbe weiter, wobei das Ziel jetzt eben nicht mehr T ist, sondern S ist. Aber das ist okay, weil wir haben so viel nach T geschickt, wie noch irgendwie geht.
01:22:41
Ach, und noch eine Heuristik, eine haben wir noch. Die kennen wir aber schon, in dem Zusammenhacken mit Kürzeste Wege, Wenn wir eine Schichthöhe haben, die leer ist, das will ich jetzt nicht nochmal wiederholen, wir haben das alles schon mal betrachtet, das können Sie gerne dann transferieren,
01:23:04
das sollte sich eins zu eins transferieren lassen auf diese Situation. Wenn Sie eine Schichthöhe haben, in der kein einziger Knoten drin ist, dann ist dort an dieser Stelle ein schon saturierter Schnitt.
01:23:35
Und genau, dann ist an der Stelle schon ein saturierter Schnitt,
01:23:41
hier ist so eine Lücke, an der Stelle ist ein saturierter Schnitt, alle hier kleiner als dieser Wert K, alle hier größer als der Wert K, und das heißt, wir können die alle, das ist jetzt die heuristische Verbesserung,
01:24:01
wir können die alle auf Höhe N erhöhen und es bleibt weiterhin Valid Labeling, und die fangen dann an, Fluss wieder nach S zurück zu schicken. Es geht immer um dieselbe Sache. Es geht bei den Heuristiken immer wieder darum, zu verhindern, dass kleinteilig Schritt für Schritt Relabels passieren
01:24:23
und dazwischen durch die entsprechenden Pushes hin und her und hin und her, sondern dass man möglichst häufig Relabelings macht, eben mit Gewalt, hier in diesen verschiedenen heuristischen Techniken, die einen großen Sprung hochmachen, sodass man sich diese vielen kleinteiligen Schritten mit den Relabeling Schritten,
01:24:41
mit den dazugehörigen hin und her Pushes, einfach heuristisch spart. Wie gesagt, keine Verbesserung an der asymptotischen Komplexität, deshalb steht da auch nur heuristik, aber eine durchaus empirisch ernsthafte Verbesserung.
01:25:02
So, damit bin ich mit diesem Kapitel maximale Flüsse für heute durch. Frage? Ja, es gibt auch Algorithmen von O von M mal M.
01:25:21
Jetzt muss ich nochmal nachdenken, der basiert auch auf Briefle-Push-Idee. Bitte? Genau, man kam immer näher an O von M mal M ran, aber hat es nie erreicht. Ich müsste nochmal nachschlagen, was genau die Idee bei dem Algorithmus war,
01:25:42
dass er mich daran, dass ich das entsprechende Standardwerk über Netzwerkflüsse mal wieder einfordern müsste von demjenigen, dem ich es ausgelehnt habe. Es basiert aber prinzipiell auf der Briefle-Push-Idee. Also die Briefle-Push-Idee hat sich am wirkmächtigsten herausgestellt.
01:26:02
Alle anderen haben so ihre Grenzen und kommen nicht darüber hinaus, und die Grenzen aller anderen Ansätze sind eben deutlich über N mal M. Es gibt sogar unter N mal M ein bisschen, ein ganz kleines wenig drunter. Also N mal M geteilt durch eine sehr langsame wachsende Funktion. Das gibt es auch noch.
01:26:23
Aber die Sachen werden dann auch sehr kompliziert, deshalb sind sie hier ausgelassen. Das sind noch die einfachen Varianten. Gut, ich denke, es macht keinen Sinn, heute mit dem nächsten Thema anzufangen. Dann verbleiben wir so und wir sehen uns hoffentlich beim nächsten Mal wieder.
01:26:45
Okay, bis dann.