WEBVTT 00:05.050 --> 00:07.450 Ich begrüße Sie zu Algorithmen 2. 00:07.650 --> 00:09.650 Ich entschuldige mich für die Verspätung. 00:09.750 --> 00:14.950 Ich war wieder in einer hochschulpolitischen Diskussion verstrickt, wo 00:14.950 --> 00:19.410 man manchmal den Eindruck hat, dass da irgendwie die Zeit anders 00:19.410 --> 00:19.750 läuft. 00:19.830 --> 00:20.530 Weiß ich auch nicht. 00:22.590 --> 00:25.950 Wir hatten uns beim letzten Mal einen, wie ich finde, sehr spannenden 00:25.950 --> 00:30.450 Algorithmus zur Berechnung maximaler Flüsse angeschaut, nämlich den 00:30.450 --> 00:32.810 Preflow -Push-Algorithmus. 00:32.810 --> 00:43.790 Der von dieser sehr grobkörnigen Berechnung vom DINITS-Algorithmus 00:47.590 --> 00:51.290 die entgegengesetzte Richtung geht praktisch und sehr feinkörnig 00:51.290 --> 00:55.610 operiert, nämlich immer nur Fluss entlang einzelner Kanten verschiebt. 00:55.730 --> 00:58.810 Und damit das in einem konsistenten Art und Weise möglich ist, haben 00:58.810 --> 01:02.250 wir zwei Techniken angewendet. 01:02.250 --> 01:07.050 Erst einmal, wir relaxieren die Erfordernis, dass wir zu jedem 01:07.050 --> 01:11.610 Zeitpunkt mit einem zulässigen Fluss arbeiten, insofern, als dass wir 01:11.610 --> 01:18.090 einen Preflow zulassen, bei dem es erlaubt ist, dass Knoten einen 01:18.090 --> 01:21.910 Exzess haben, also dass da mehr reinfließt als rausfließt. 01:22.370 --> 01:28.170 Und damit das sinnvoll ist, haben wir eine Distanzfunktion, die so 01:28.170 --> 01:31.930 etwas Ähnliches ist wie eine Abschätzung der Entfernung zum 01:31.930 --> 01:33.190 Senkenknoten. 01:34.550 --> 01:48.290 Wir hatten uns dann eine Analyse angeschaut, die zeigt, dass mehr oder 01:48.290 --> 01:54.790 weniger beliebige Implementierungen dieses Algorithmus, also unter 01:54.790 --> 01:59.710 sehr allgemeinen Annahmen, eine Laufzeit von O von n² mal m kriegen. 02:00.450 --> 02:03.850 Ich hatte dann gesagt, wenn man das ein bisschen konkretisiert, 02:04.390 --> 02:09.690 insofern, dass man sagt, dass man eine FIFO-Regel verwendet, bei der 02:09.690 --> 02:16.210 man die aktiven Knoten in einer FIFO-Queue verwaltet, dann kriegt man 02:16.210 --> 02:19.630 eine etwas bessere Schranke für dichte Graphen von O von n³. 02:21.250 --> 02:26.730 Ich möchte Ihnen aber heute etwas noch besseres zeigen, zumindest im 02:26.730 --> 02:31.590 Worst -Case, nämlich Highest-Level-Preflow-Push, wo man O von n² mal 02:31.590 --> 02:33.990 Wurzel m zeigen kann. 02:36.890 --> 02:41.630 Vielleicht zunächst mal zur Implementierung. 02:41.630 --> 02:46.230 Man kann das effizient mit einer Bucket-Priority-Queue implementieren, 02:46.830 --> 02:50.490 sodass dann der Overhead dafür, dass man jetzt nicht mehr so etwas 02:50.490 --> 02:54.550 Einfaches wie eine FIFO hat, sondern eine Art Priority-Queue, 02:55.670 --> 02:56.850 eigentlich sehr klein ist. 02:58.230 --> 03:02.650 Das Spannende ist, wie zeige ich denn jetzt diese verbesserte 03:02.650 --> 03:05.470 Laufzeit, weil wir ja doch einen relativ komplexen Algorithmus haben. 03:06.750 --> 03:10.270 Aber wenn wir uns das hier angucken, gibt es schon mal einen Hinweis, 03:10.270 --> 03:19.250 dass nämlich der begrenzende Faktor hier waren, dieser n² mal m-Term 03:19.250 --> 03:21.370 für die nicht-saturierenden Push-Operationen. 03:21.410 --> 03:25.690 Also es waren Push-Operationen, die den kompletten Exzess aus einem 03:25.690 --> 03:31.650 Knoten rausschiebt, aber die Kante entlang der dieser Fluss geschoben 03:31.650 --> 03:33.970 wird, wird dadurch nicht saturiert. 03:34.090 --> 03:35.750 Also die hat weiterhin Restkapazität. 03:37.150 --> 03:41.690 Das ist die im Worst-Case häufigste Operation von dem Arbitrary 03:41.690 --> 03:45.250 Preflow -Push und die müssen wir jetzt runterkriegen. 03:46.250 --> 03:49.670 Und darauf werden wir uns dann entsprechend konzentrieren. 03:50.170 --> 03:52.110 Beispiel hatte ich schon vorgeführt. 03:57.470 --> 04:03.890 Im Endeffekt müssen wir zeigen, dieses Lemma 12, dass wir höchstens O 04:03.890 --> 04:07.410 von n² mal Wurzelm nicht-saturierende Push-Operationen brauchen. 04:16.870 --> 04:20.910 Wir verwenden wieder so ein Potentialfunktions-Argument, aber diesmal 04:20.910 --> 04:23.190 eine etwas kompliziertere Potentialfunktion. 04:27.730 --> 04:36.590 Wir definieren nämlich die Strich von V als die Anzahl von V 04:36.590 --> 04:37.930 -dominierter Knoten. 04:38.030 --> 04:42.990 Damit meine ich die Anzahl Knoten W, die ein gleiches Level haben. 04:43.810 --> 04:48.590 Und dann wird das obskurerweise noch mit einem Tuning-Faktor K 04:48.590 --> 04:49.170 skaliert. 04:50.110 --> 04:55.870 Wir werden später sehen, dass K gleich Wurzelm zu den besten 04:55.870 --> 04:57.350 asymptotischen Schranken führt. 04:58.190 --> 05:01.250 Aber wir werden jetzt erstmal mit irgendeinem beliebigen K arbeiten, 05:01.430 --> 05:04.250 dann sind die Formeln auch kürzer und am Ende ist das dann 05:04.250 --> 05:04.790 offensichtlich. 05:06.550 --> 05:11.110 Und die Potentialfunktion V ist dann einfach die Summe dieser d Strich 05:11.110 --> 05:14.110 -Werte summiert über alle aktiven Knoten. 05:14.830 --> 05:21.450 Und wir werden den Buchstaben d Stern brauchen, das ist der größte 05:21.450 --> 05:24.150 Abstandswert eines aktiven Knotens. 05:24.710 --> 05:32.810 Wir definieren eine Phase als die Push-Operationen zwischen zwei 05:32.810 --> 05:35.670 aufeinanderfolgenden Änderungen von d Stern. 05:35.810 --> 05:39.810 Also die Beobachtung ist jetzt, wenn ich highes Level mache, dann 05:39.810 --> 05:44.490 arbeite ich immer mit den Knoten, die diesen Wert d Stern haben und ab 05:44.490 --> 05:45.430 und zu ändert er sich. 05:46.650 --> 05:50.610 Und während er konstant bleibt, kann ich aber bestimmte Schlüsse 05:50.610 --> 05:55.250 ziehen, wie wir später sehen werden, darüber, wie sich die 05:55.250 --> 05:57.110 Potentialfunktion ändert. 05:58.050 --> 06:01.930 Ich kann aber auch abschätzen, wie oft er sich ändert und aus der 06:01.930 --> 06:05.930 Gesamtsache davon ergibt sich dann eine Abschätzung für die 06:05.930 --> 06:06.790 Gesamtlaufzeit. 06:08.290 --> 06:12.090 Also ich gucke mir immer Phasen an, in denen dieser d Stern-Wert 06:12.090 --> 06:12.950 konstant bleibt. 06:14.210 --> 06:17.290 Und ich unterscheide außerdem noch teure und billige Phasen. 06:17.430 --> 06:21.390 Teure Phasen sind die, bei denen ich mehr als k Push-Operationen habe 06:21.390 --> 06:25.110 und billige waren welche mit kleiner gleich. 06:26.310 --> 06:27.790 Gibt es Fragen zu diesen Definitionen? 06:29.170 --> 06:32.970 Also das ist natürlich so, auf solche Definitionen zu kommen, das ist 06:32.970 --> 06:35.790 dann der kreative Teil einer Algorithmenanalyse. 06:37.910 --> 06:40.890 Die kommt man dann wahrscheinlich auch eher über irgendwelche Umwege. 06:40.990 --> 06:44.350 Manchmal probiert man vielleicht auch ein bisschen rum und fragt sich, 06:44.470 --> 06:47.450 was kann ich denn zeigen, was ist die Art Fortschritt, die ich mache 06:47.450 --> 06:51.170 und versucht das dann zu kodieren in so einer Funktion. 06:51.710 --> 06:56.070 Das erwarte ich aber jetzt nicht von Ihnen als Übungsaufgabe oder so, 06:56.130 --> 07:00.090 sondern ich möchte einfach mal demonstrieren, wie fortgeschrittene 07:00.090 --> 07:01.970 Algorithmenanalysen aussehen können. 07:01.970 --> 07:02.450 Ja? 07:04.670 --> 07:11.650 So, der Beweis setzt sich jetzt aus einer relativ kleinen Zahl von 07:11.650 --> 07:18.010 Behauptungen zusammen, die wir halt separat zeigen, die in Sicht 07:18.010 --> 07:22.470 vielleicht auch wieder teilweise ein bisschen obskur sind. 07:22.550 --> 07:23.450 Wie kommt man da drauf? 07:23.890 --> 07:25.790 Aber keine davon ist jetzt wirklich schwierig. 07:26.030 --> 07:28.190 Also wir müssen uns einfach jetzt nur da durchhangeln. 07:29.690 --> 07:34.870 Und so ein bisschen ist es auch ähnlich wie das, was wir bei der 07:34.870 --> 07:38.570 arbitrary Preflow Push-Analyse schon gemacht haben, dass wir halt so 07:38.570 --> 07:41.790 verschiedene Ereignisse abschätzen müssen, wie oft das passiert. 07:43.350 --> 07:47.890 Also insbesondere hatten wir bereits bei der alten Analyse gezeigt, 07:48.030 --> 07:53.090 dass es höchstens zwei n² Relabel-Operationen gibt und höchstens n mal 07:53.090 --> 07:55.270 m saturierende Push-Operationen. 07:55.270 --> 07:59.770 Und das werden wir jetzt wieder brauchen als zusätzliche Lämmerter. 08:02.110 --> 08:07.090 Genau, also die Claims sind, wir haben höchstens vier n² mal k nicht 08:07.090 --> 08:12.270 saturierende Push-Operationen in billigen Phasen. 08:16.750 --> 08:21.950 Zweitens, Potentialfunktionswert ist immer größer gleich null und aber 08:21.950 --> 08:23.890 kleiner gleich n² durch k. 08:25.810 --> 08:28.270 Ob wir es dazu geschrieben haben, können Sie sich jetzt schon 08:28.270 --> 08:30.270 überlegen, aber wir gehen da gleich Stück für Stück durch. 08:30.750 --> 08:38.990 Dann eine Relabel- oder saturierende Push-Operation erhöht phi 08:38.990 --> 08:40.650 höchstens um n durch k. 08:41.630 --> 08:46.550 Eine nicht saturierende Push-Operation erhöht phi nicht. 08:47.550 --> 08:49.950 Das ist irgendwie ein bisschen schwach, weil wir wollen eigentlich 08:49.950 --> 08:51.950 irgendwas haben, was das phi mal senkt. 08:52.740 --> 08:54.710 Aber da kommen wir jetzt zu. 08:55.350 --> 09:02.350 Nämlich in einer teuren Phase mit k nicht saturierenden Push 09:02.350 --> 09:07.230 -Operationen, mit q größer gleich k nicht saturierenden Push 09:07.230 --> 09:12.310 -Operationen, senken wir phi um mindestens q. 09:12.950 --> 09:20.050 Das bedeutet im Endeffekt, dass man im Mittel pro konstanter Zeit, die 09:20.050 --> 09:24.530 man in den teuren Phasen verbringt, eben das phi um 1 senkt. 09:25.190 --> 09:28.030 In den billigen Phasen stellt sich heraus, das ist sowieso nicht so 09:28.030 --> 09:30.450 ein großes Problem und dann hat man das Problem gelöst. 09:31.170 --> 09:35.410 Aber jetzt gucken wir uns mal etwas genauer an, wie man daraus 09:35.410 --> 09:38.370 zusammensetzt, was wir eigentlich haben wollen. 09:46.480 --> 09:49.100 Die gesamte Erhöhung, die wir kriegen, 09:52.760 --> 09:58.240 ist hier n durch k pro Relabel und saturierender Push-Operationen. 09:58.280 --> 09:59.620 Das ist dieses n durch k. 10:00.240 --> 10:04.120 Das ist die Relabel-Operation oder eine obere Schranke dafür und das 10:04.120 --> 10:06.120 sind die saturierenden Push-Operationen. 10:06.520 --> 10:09.440 Das ist also die Erhöhung, die wir aus Relabels und saturierenden 10:09.440 --> 10:10.160 Pushes kriegen. 10:10.800 --> 10:15.040 Und aus dem Claim 1 kommt, dass wir am Anfang vielleicht schon n² 10:15.040 --> 10:15.960 durch k haben. 10:17.120 --> 10:20.260 Und das ist sozusagen die Gesamterhöhung, die wir kriegen. 10:22.740 --> 10:26.600 Das, was da passiert, was den Viehwert erhöht, muss sich irgendwie 10:26.600 --> 10:30.320 wieder senken und das passiert in den teuren Phasen. 10:40.910 --> 10:43.990 Wenn ich das hier ausmultipliziere, steht da das hier. 10:46.630 --> 10:49.730 Und das 5 liefert uns im Wesentlichen, dass das dann auch eine 10:49.730 --> 10:52.750 Schranke für die nicht saturierenden Push-Operationen in den teuren 10:52.750 --> 10:53.530 Phasen ist. 10:57.410 --> 11:01.570 Und dann kommen da noch die billigen Phasen dazu. 11:08.990 --> 11:13.130 Das ist das hier, der Claim 1 im Endeffekt, der kommt dann dazu. 11:14.050 --> 11:17.070 Und jetzt sieht man, warum wir da einen Trade-Off haben für diesen 11:17.070 --> 11:17.950 Tuning -Parameter. 11:18.550 --> 11:22.290 Also in den teuren Phasen haben wir das hier durch k. 11:22.290 --> 11:26.190 In den billigen Phasen haben wir das hier mal k. 11:26.650 --> 11:30.370 Und jetzt wähle ich halt ein k, das diese Summe minimiert. 11:30.530 --> 11:34.130 Und asymptotisch ist das Wurzel-M so ein Wert. 11:36.730 --> 11:38.650 Und damit habe ich mein Theorem gezeigt. 11:39.090 --> 11:41.330 Also das Einzige, was jetzt noch bleibt, ist, dass ich diese fünf 11:41.330 --> 11:43.090 komischen Claims zeigen muss. 11:43.410 --> 11:46.290 Die werde ich jetzt nacheinander durchgehen. 11:48.610 --> 11:54.290 Also ich behaupte, ich habe vier n-Quadraten mal k nicht-saturierende 11:54.290 --> 11:57.350 Push -Operationen in den billigen Phasen. 11:59.850 --> 12:05.190 Dafür müssen wir im Wesentlichen zeigen, dass wir höchstens vier n 12:05.190 --> 12:06.450 -Quadrat -Phasen haben. 12:07.630 --> 12:10.750 Weil eine billige Phase ja nach Definition höchstens k-nicht 12:10.750 --> 12:12.690 -saturierende Push-Operationen enthält. 12:13.410 --> 12:14.950 Was war noch meine Phase? 12:14.950 --> 12:20.910 Naja, das war die Operation zwischen zwei Veränderungen von D-Stern, 12:21.070 --> 12:24.190 also dem höchsten Level eines aktiven Knotens. 12:24.510 --> 12:26.090 Also wie oft kann sich der ändern? 12:28.210 --> 12:30.170 Naja, und die Beobachtung ist eigentlich ganz einfach. 12:30.290 --> 12:36.030 Der ändert sich höchstens, wenn wir eine Relabel-Operation machen. 12:41.280 --> 12:43.900 Aber wir haben bereits gesehen, dass es 12:49.910 --> 12:56.470 das war das Lemma 7, das war einfach die Anzahl Relabel-Operationen, 12:56.570 --> 12:57.630 das sind zwei n-Quadrat. 12:59.490 --> 13:04.490 Achso, genau, der D-Stern-Wert erhöht sich nur, wenn ich ein Relabel 13:04.490 --> 13:04.770 mache. 13:05.930 --> 13:09.050 Also habe ich zwei n-Quadrat-Erhöhungen von dem D-Stern. 13:10.550 --> 13:13.810 Und dann kann es aber auch nicht mehr Senkungen geben, weil sonst 13:13.810 --> 13:16.910 würde der D-Stern-Wert auf einen negativen Wert gehen. 13:16.910 --> 13:21.230 Also insgesamt vier n-Quadrat-Veränderungen von D-Stern als obere 13:21.230 --> 13:22.150 Schranke. 13:22.690 --> 13:26.750 Und den Rest liefert uns die Definition einer billigen Phase. 13:26.910 --> 13:28.070 Frage zu Claim 1. 13:29.050 --> 13:33.230 Oder vielleicht hier nochmal Frage dazu, wie man aus diesen fünf 13:33.230 --> 13:37.790 Claims die Anzahl saturierender Pushs ableitet. 13:39.610 --> 13:43.150 Claim 2 habe ich geschrieben, das ist obvious, aber überlegen wir es 13:43.150 --> 13:43.590 uns mal. 13:44.950 --> 13:46.690 Warum ist das Größer-Gleich-Null? 13:46.770 --> 13:47.650 Kann mir das jemand sagen? 13:47.810 --> 13:49.790 Warum ist die Potentialfunktion Größer-Gleich-Null? 13:56.690 --> 13:59.250 Weil es eine Größe einer Menge ist. 13:59.990 --> 14:02.210 Wir summieren über Größen einer Menge. 14:03.290 --> 14:08.930 Warum ist es kleiner-gleich-n-Quadrat-durch-k? 14:10.150 --> 14:11.730 Kann mir das auch jemand sagen? 14:12.470 --> 14:16.490 Wie groß kann eine Knotenmenge maximal werden in einem Graphen mit N 14:16.490 --> 14:17.530 Knoten und M Kanten? 14:19.050 --> 14:19.530 N. 14:21.670 --> 14:25.090 Das D-Strich kann höchstens N werden und es können höchstens alle 14:25.090 --> 14:26.250 Knoten aktiv werden. 14:26.370 --> 14:27.570 Dann hat man N mal N. 14:28.250 --> 14:29.130 Das ist n-Quadrat. 14:29.510 --> 14:32.970 Aber ich teile das Ganze durch k, also steht da n-Quadrat-durch-k. 14:34.450 --> 14:35.790 Das ist einfach. 14:36.510 --> 14:37.710 Was war der dritte Claim? 14:39.610 --> 14:43.930 Eine Relabel-Operation oder ein saturierender Push erhöht phi 14:43.930 --> 14:45.690 höchstens um N durch k. 14:50.850 --> 14:52.950 Jetzt nehmen wir erst mal den Relabel-Fall. 14:53.270 --> 14:56.710 Wir sagen, ein Knoten V wird relabelt. 14:57.970 --> 15:01.190 Dann erhöht sich sein D-Wert. 15:01.830 --> 15:05.030 Und das kann natürlich die Anzahl Knoten, die er dominiert, erhöhen. 15:05.030 --> 15:09.130 Und jetzt ist es wieder trivial, schlimmstenfalls um N Knoten. 15:09.610 --> 15:11.870 Aber ich skaliere wieder durch k, also N durch k. 15:12.490 --> 15:16.170 Und nirgendwo sonst ändert sich was an den D-Strichwerten. 15:17.130 --> 15:24.050 Insbesondere da das D von V ja erhöht wird, fällt er aus anderen D 15:24.050 --> 15:27.450 -Strichs höchstens raus, aber kann nie da reinkommen. 15:32.010 --> 15:40.270 Bei einer saturierenden Push-Operation verändert sich der Level des 15:40.270 --> 15:41.530 Knoten ja nicht. 15:41.650 --> 15:46.910 Und der bleibt auch aktiv, aber es kann sein, dass der Zielknoten des 15:46.910 --> 15:48.150 Pushs aktiviert wird. 15:51.270 --> 15:52.850 Und da ist wieder das gleiche Spiel. 15:52.930 --> 15:55.810 Der kann bestenfalls alle anderen dominieren und dann haben wir einen 15:55.810 --> 15:59.730 Wert von N durch K für diesen Knoten und an allen anderen ändert sich 15:59.730 --> 16:00.810 nichts. 16:07.920 --> 16:10.580 Genau das habe ich eigentlich gesagt. 16:10.720 --> 16:11.840 Fragen zu Claim 3? 16:13.640 --> 16:14.600 Das war Claim 4. 16:15.840 --> 16:21.800 Ein nicht-saturierender Push erhöht V nicht. 16:22.880 --> 16:24.120 Woran liegt das? 16:25.760 --> 16:29.680 Ein nicht-saturierender Push deaktiviert einen Knoten. 16:32.520 --> 16:36.880 Das könnte sogar zu einer Verringerung des Potentials führen, weil aus 16:36.880 --> 16:38.940 der Summe ein Knoten rausfällt. 16:39.820 --> 16:44.160 Das ist nicht ganz gesagt, weil der kann ja den Zielknoten des Pushs 16:44.160 --> 16:49.160 aktivieren, aber da das ein Downward-Push ist, kann der Zielknoten 16:49.160 --> 16:53.840 niemals mehr Knoten dominieren als der Quellknoten des Pushs. 16:54.500 --> 16:56.720 Deshalb kann das nicht erhöhen. 16:57.940 --> 16:58.920 Fragen dazu? 17:00.960 --> 17:01.820 Und Nummer 5? 17:03.440 --> 17:05.460 Das ist vielleicht der wichtigste Claim. 17:06.240 --> 17:11.480 Wir müssen jetzt zeigen, eine teure Phase mit Q, nicht-saturierenden 17:11.480 --> 17:15.080 Push -Operationen, verringert V um mindestens Q. 17:17.420 --> 17:20.520 Hier können wir jetzt ausnutzen, dass sich während der Phase D-Stern 17:20.520 --> 17:21.620 ja nicht ändert. 17:25.100 --> 17:31.170 Ein nicht-saturierender Push verringert die Anzahl aktiver Knoten. 17:31.460 --> 17:35.740 Und zwar sind das alles aktive Knoten mit dem Level D'. 17:35.740 --> 17:45.540 Also da fällt immer einer aus diesem höchsten Level raus. 17:49.260 --> 17:53.900 Und wenn wir jetzt Q-Stück dieser Operation haben, fallen halt Q 17:53.900 --> 17:55.360 -Knoten aus dem Level raus. 17:56.400 --> 17:59.560 Und jetzt ist es wichtig zu sehen, dass wir dieses D'. 18:01.760 --> 18:04.040 Wo ist die Definition von dem D'? 18:04.040 --> 18:04.800 Die hole ich nochmal. 18:06.080 --> 18:09.760 Die ist definiert als die Anzahl Knoten mit einem Level kleiner 18:09.760 --> 18:10.560 gleich. 18:11.020 --> 18:14.260 Und dafür ist es auch nicht wichtig, ob diese Knoten w-aktiv sind oder 18:14.260 --> 18:14.660 nicht. 18:15.400 --> 18:16.580 Das ist hier ganz wichtig. 18:17.060 --> 18:20.840 Das bedeutet nämlich, die ganzen Knoten in dem Level, die dominieren 18:20.840 --> 18:21.900 sich gegenseitig. 18:21.960 --> 18:22.960 Die zähle ich alle mit. 18:24.100 --> 18:27.460 Und jetzt schmeiße ich da immer welche raus, dass ich deren 18:27.460 --> 18:30.540 Mengengröße nicht mehr mitzähle. 18:34.300 --> 18:37.360 Aber in den anderen Summen taucht sie immer mit auf. 18:38.060 --> 18:44.220 Das bedeutet, jedes Mal fliegt ein Zähler raus, der mindestens so groß 18:44.220 --> 18:48.120 ist, wie die Größe dieses Levels am Anfang der Phase. 18:49.200 --> 18:50.960 Und das ist mindestens Q. 18:53.100 --> 18:56.360 Und deshalb verringert sich das Ganze um... 19:01.010 --> 19:02.550 eigentlich um Q². 19:06.960 --> 19:10.560 Jeder nicht-saturierende Push verringert die Anzahl aktiver Knoten. 19:10.560 --> 19:13.160 Das wird jetzt einfach ganz grob abgeschätzt. 19:14.080 --> 19:15.580 Ich habe Q dieser Operation. 19:16.200 --> 19:18.120 Eigentlich verändert sich es um Q². 19:19.220 --> 19:21.180 Das ist aber größer gleich K². 19:21.980 --> 19:24.580 Und dann teile ich es nochmal durch K und dann steht da K. 19:26.700 --> 19:28.820 Das ist größer gleich Q². 19:28.920 --> 19:30.500 Das schätze ich ab durch Q mal K. 19:30.620 --> 19:33.440 Das teile ich durch K und dann ist es größer gleich Q. 19:35.820 --> 19:39.480 Und wenn ich das jetzt pro nicht-saturierenden Push mache, ist das 19:39.480 --> 19:42.600 dann sozusagen einer pro nicht-saturierenden Push. 19:43.340 --> 19:45.080 Damit habe ich alle Claims gezeigt. 19:45.220 --> 19:46.240 Das Lemma ist gezeigt. 19:46.440 --> 19:50.340 Und damit ist auch die Laufzeit von dem Highest-Level-Preflow-Push 19:50.340 --> 19:51.160 gezeigt. 19:53.520 --> 19:54.880 War da jetzt noch was? 19:55.900 --> 19:58.160 Ah ja, ich habe das jetzt nur nochmal zusammengestellt. 19:59.360 --> 20:00.380 Damit sind wir fertig. 20:00.560 --> 20:01.820 Gibt es da noch Fragen dazu? 20:02.720 --> 20:03.720 Ist irgendwas übersehen? 20:05.480 --> 20:06.420 Nicht der Fall. 20:07.460 --> 20:10.880 Genau, es gibt noch ein paar andere Auswahlregeln. 20:11.020 --> 20:14.180 Zum Beispiel Modified FIFO. 20:14.760 --> 20:17.980 Das ist dann eigentlich keine FIFO, sondern eine DAC, eine Double 20:17.980 --> 20:18.920 -Ended Queue. 20:19.100 --> 20:24.780 Wo man sagt, wenn ich eine Relabel-Operation auf einem Knoten mache, 20:24.940 --> 20:27.980 dann tue ich sozusagen am Anfang, also der wird immer wieder 20:27.980 --> 20:28.740 angeschaut. 20:29.540 --> 20:36.480 Während wenn ich durch einen Push einen anderen Knoten aktiviere, dann 20:36.480 --> 20:37.260 kommt er ans Ende. 20:38.460 --> 20:41.020 Das habe ich jetzt nur eingeführt, weil ich jetzt mal ein bisschen was 20:41.020 --> 20:43.320 über experimentelle Ergebnisse berichten möchte. 20:47.140 --> 20:50.420 Und das habe ich aus dem Lederbuch gemacht. 20:51.140 --> 20:54.400 Und da wird halt diese Auswahlregel auch untersucht. 20:55.600 --> 20:58.140 Und die ist tatsächlich auch ein bisschen besser als FIFO. 20:58.280 --> 21:03.180 Und wir werden sehen, dass der Vergleich M-FIFO, Highest-Level ein 21:03.180 --> 21:04.200 bisschen komplexer ist. 21:04.200 --> 21:06.220 Was ich aber auch ganz interessant finde. 21:07.260 --> 21:11.820 Dann ist es ganz wichtig, die Algorithmen, so wie wir sie jetzt 21:11.820 --> 21:14.440 vorgestellt haben, die sind eigentlich nicht besonders gut. 21:15.020 --> 21:16.140 Das muss man sich klar machen. 21:16.740 --> 21:20.260 Es gibt einen ganzen Sack voll heuristischer Optimierungen und einige 21:20.260 --> 21:24.500 davon muss man einfach einbauen, um zu vernünftiger Leistung zu kommen 21:24.500 --> 21:25.400 für praktische Instanzen. 21:26.160 --> 21:29.560 Das kann man sich zum Beispiel überlegen, nehmen wir mal an, wir haben 21:29.560 --> 21:35.480 einen trivialen Graphen, einen Pfad der Länge N-1 mit 21:35.480 --> 21:38.080 Kantenkapazitäten 1. 21:38.900 --> 21:42.280 Da würde der Ford-Falkaschen-Algorithmus lineare Zeit brauchen. 21:43.180 --> 21:47.800 Alle Algorithmen, die wir bisher gesehen haben für Push-Relabel, 21:47.940 --> 21:51.680 brauchen mindestens quadratische Zeit auf diesem trivialen Graphen. 21:52.840 --> 21:58.360 Einfach weil diese Relabel-Operationen, die immer nur einzeln 21:58.360 --> 22:02.120 hochzählen, kann man sich überlegen, dass die erst funktionieren, wenn 22:02.120 --> 22:09.720 ich dann mühsam in quadratischer Zeit so eine schräge Ebene gebaut 22:09.720 --> 22:13.260 habe, die wirklich das zum Ziel führt, die Daten. 22:16.800 --> 22:23.100 Das kann man aber relativ leicht umgehen mit einer ganz einfachen 22:23.100 --> 22:28.480 Heuristik, die nennt man Aggressive Local Relabeling, dass man statt 22:28.480 --> 22:33.160 einem Relabel, das wirklich den Wert nur um 1 erhöht, sich überlegt, 22:33.380 --> 22:36.500 das ist eine Active Node. 22:36.660 --> 22:40.500 Durch ein Relabel bleibt der auch aktiv. 22:40.960 --> 22:44.300 Also kann ich den immer wieder relabeln, solange es keine Eligible 22:44.300 --> 22:46.380 Edges gibt, die da rausgehen. 22:46.480 --> 22:48.100 Dann kann man sich überlegen, was ist das dann? 22:48.860 --> 22:54.080 Der Wert, den ich dann am Ende kriege, das ist einfach 1 plus der 22:54.080 --> 23:03.080 kleinste Level einer in GF-Inzidentenkante zu V. 23:03.900 --> 23:10.120 Das heißt, ich muss nur durch die inzidenten Kanten iterieren, mir den 23:10.120 --> 23:13.300 kleinsten Level merken und dazu 1 addieren. 23:14.100 --> 23:18.100 Und dann habe ich in bestimmten wichtigen Fällen ganz viele Relabel 23:18.100 --> 23:22.120 -Operationen in der Laufzeit gemacht, die einfach nur proportional zum 23:22.120 --> 23:25.720 Ausgangsgrad des Knotens sind und für unseren Pfad dann in konstanter 23:25.720 --> 23:26.120 Zeit. 23:27.800 --> 23:34.840 Also hier ist ein Beispiel, hier ist ein Knoten auf Level 5 mit Exzess 23:34.840 --> 23:38.860 15, der würde vielleicht sogar noch weiter gehen und nicht nur 23:38.860 --> 23:41.040 Relabels machen, sondern auch so ein Exhaust. 23:41.740 --> 23:48.880 Also der iteriert einmal durch seine inzidenten Kanten, sagt dann, 23:49.280 --> 23:55.940 aha, das ist ein Downward Edge, schön, da kann ich Fluss 7 entlang 23:55.940 --> 24:00.380 routen, dann bleibt Exzess 8, dann gucke ich mir den an, das ist auch 24:00.380 --> 24:05.520 ein Downward Edge, 3 raus, dann bleibt Exzess 5. 24:07.980 --> 24:13.660 Und jetzt hier, der geht nicht, merke ich mir, aha, Level 8, dann 24:13.660 --> 24:17.280 müsste ich 9 werden, dann gucke ich mir den noch an, Level 7, das ist 24:17.280 --> 24:21.620 kleiner, das ist das Minimum, aha, dann muss ich 7 plus 1 gleich 8 für 24:21.620 --> 24:22.580 meinen Level machen. 24:23.260 --> 24:28.160 Und dann hat er sozusagen mit einmal inspizieren aller inzidenten 24:28.160 --> 24:33.620 Kanten mehrere Push-Operationen gemacht und mehrere Relabel 24:33.620 --> 24:34.340 -Operationen. 24:34.640 --> 24:38.140 Und insbesondere ist er dann hier direkt von 5 auf 8 gesprungen. 24:38.960 --> 24:39.660 Fragen dazu? 24:40.680 --> 24:41.160 Genau. 24:42.900 --> 24:47.880 Dann gibt es etwas, was noch viel mächtiger ist, Global Relabeling. 24:50.320 --> 24:52.660 Das macht man vor allem einmal ganz am Anfang. 24:53.280 --> 25:00.100 Man macht nämlich eine Rückwärtsbreitensuche vom Zielknoten und 25:00.100 --> 25:02.240 berechnet dann exakte Levels. 25:02.280 --> 25:06.500 Wir hatten ja gesagt, das soll eine Approximation des Abstands zu T 25:06.500 --> 25:09.440 sein und jetzt ist es halt in dem Moment am Anfang zumindest keine 25:09.440 --> 25:11.420 Approximation, sondern der exakte Wert. 25:13.600 --> 25:19.060 Und das ist auch, kann man sich leicht überlegen, zulässig, man könnte 25:19.060 --> 25:24.000 da auch eine Folge von Relabel-Operationen durchführen, die das 25:24.000 --> 25:28.640 zeigen, dass das irgendwie nur eine bestimmte spezielle 25:28.640 --> 25:33.320 Implementierung des arbitrary-flow-push-Algorithmus ist. 25:33.600 --> 25:37.100 Aber es geht halt in linearer Zeit und man hat danach viel mehr 25:38.220 --> 25:40.940 Informationen darüber, in welche Richtung die Flüsse eigentlich 25:40.940 --> 25:42.400 geroutet werden sollen. 25:44.800 --> 25:50.100 Dann gibt es eine Spezialbehandlung von Knoten mit einem Level größer 25:50.100 --> 25:50.660 gleich N. 25:52.860 --> 25:56.400 Es ist nämlich so, wenn ein Knoten ein Level größer gleich N hat, dann 25:56.400 --> 26:01.280 gilt das gleiche Argument, wo wir gesagt haben, das ist der Level N 26:01.280 --> 26:02.320 des Quellknoten. 26:02.320 --> 26:08.400 Von da kann man niemals wieder Flow zum Ziel routen. 26:08.480 --> 26:11.140 Das heißt, das Einzige, was mit den Knoten noch passiert, ist, dass 26:11.140 --> 26:14.800 deren Exzess irgendwann zurück zur Senke geroutet wird. 26:15.520 --> 26:18.320 Und das verschiebt man bis ganz ans Ende sozusagen. 26:18.900 --> 26:23.780 Und wir hatten ja gezeigt, dass das Exzess, den man einmal irgendwo 26:23.780 --> 26:26.340 hingeroutet hat, den kann man auch direkt wieder zurückrouten. 26:26.860 --> 26:29.280 Das heißt, das kann ich auch in linearer Zeit erledigen. 26:29.960 --> 26:33.380 Das heißt, alle Level größer gleich N wird man in der Praxis gar nicht 26:33.380 --> 26:33.880 anfassen. 26:38.160 --> 26:42.480 Dann gibt es noch eine sogenannte Gap-Heuristik, die im Prinzip diese 26:42.480 --> 26:44.140 Beobachtung auch nochmal generalisiert. 26:44.240 --> 26:51.650 Wenn es irgendeinen Level gibt, der leer ist, also einen Distanzwert, 26:55.290 --> 26:57.490 der überhaupt nicht vergeben ist, 27:00.850 --> 27:05.790 dann ist von den Knoten mit einem Level größer I es auch nicht mehr 27:05.790 --> 27:08.270 möglich, Fluss zur Senke zu routen. 27:08.330 --> 27:09.850 Das kann man relativ leicht zeigen. 27:10.690 --> 27:13.750 Und dann kann man sozusagen die auch dieser Spezialbehandlung 27:13.750 --> 27:16.570 unterziehen und nur noch die kleineren Level sich anschauen. 27:16.870 --> 27:19.850 Das ist eine Heuristik, wo wir in den Experimenten sehen werden, dass 27:19.850 --> 27:21.070 die sehr selten was bringt. 27:21.530 --> 27:24.610 Aber bei einigen Instanzfamilien bringt sie halt dann doch was und sie 27:24.610 --> 27:25.610 ist relativ billig. 27:27.250 --> 27:30.190 Bei dem Global Relabeling ist es jetzt so, das macht man einmal am 27:30.190 --> 27:33.010 Anfang und dann hat man so ein Trade-Off. 27:35.690 --> 27:38.750 Man könnte natürlich sagen, irgendwie sorge ich dafür, dass ich immer 27:38.750 --> 27:41.290 die exakten Abstände habe, aber das wäre sehr teuer. 27:42.210 --> 27:45.110 Was man deshalb macht, ist, dass man so ein Amortisierungsargument 27:45.110 --> 27:45.670 wiederbringt. 27:46.210 --> 27:50.150 Man sagt sich, naja, es dauert Zeit O von M, diese Labels zu 27:50.150 --> 27:50.690 berechnen. 27:52.690 --> 27:56.530 Also zähle ich irgendwie mit, wie viele andere Operationen ich gemacht 27:56.530 --> 27:56.870 habe. 27:57.350 --> 27:59.330 Vermutlich Push- und Relabel-Operationen. 27:59.550 --> 28:04.330 Und immer wenn dieser Zähler größer einer Konstante mal M ist, werfe 28:04.330 --> 28:05.690 ich das Global Relabeling an. 28:07.470 --> 28:10.710 Und diese Konstante ist dann ein Tuning-Faktor, der aber nicht so 28:10.710 --> 28:11.510 empfindlich ist. 28:12.590 --> 28:16.750 Das machen die meisten erfolgreichen Implementierungen von Maximum 28:16.750 --> 28:17.390 Flow auch noch. 28:20.330 --> 28:27.070 Ich berichte jetzt über die Experimente aus dem Buch von Melon und 28:27.070 --> 28:27.350 Nea. 28:27.630 --> 28:30.130 Die haben sich drei Instanzfamilien angeschaut. 28:30.230 --> 28:36.690 Das eine sind so etwas wie Zufallsgrafen. 28:40.670 --> 28:43.450 Zwei N plus M Edges. 28:46.620 --> 28:52.700 Achso, genau, da gibt es N Knoten, einen speziellen Quell- und 28:52.700 --> 28:53.420 Zielknoten. 28:53.600 --> 28:56.220 Die Quelle ist mit allen anderen Knoten verbunden. 28:56.760 --> 28:58.480 Die anderen Knoten alle mit der Senke. 28:59.020 --> 29:01.160 Und dann gibt es noch... 29:01.160 --> 29:02.940 Das sind diese zwei N Knoten. 29:03.540 --> 29:06.020 Und dann gibt es noch M zufällig gewählte Kanten. 29:07.520 --> 29:11.840 Ich weiß jetzt gerade nicht, was die für Kapazitäten haben. 29:11.920 --> 29:14.140 Das ist entweder Unit oder Random, denke ich. 29:15.760 --> 29:20.260 Dann gibt es zwei Graffamilien von Czerkawski und Goldberg. 29:21.280 --> 29:23.740 Und eine von Ahuja, Magnanti und Orlin. 29:24.160 --> 29:27.280 Und das sind so Dinger, die man sich im Endeffekt überlegt hat, um 29:27.280 --> 29:32.400 einfachen Algorithmen das Leben schwer zu machen, sage ich mal. 29:32.660 --> 29:35.760 Wo es dann nicht so offensichtlich ist, wo man augmentierende Pfade 29:35.760 --> 29:36.500 suchen sollte. 29:36.920 --> 29:39.720 Oder wo vielleicht auch FIFO-Preflow-Push nicht gut funktioniert. 29:43.400 --> 29:46.320 Das sind keine realistischen Instanzen. 29:46.480 --> 29:47.680 Das muss man jetzt dazu sagen. 29:48.540 --> 29:50.540 Da werde ich gleich noch ein bisschen mehr dazu sagen. 29:53.280 --> 30:00.720 Ich werbe jetzt erstmal eine Serie von Folien, wo für relativ kleine 30:00.720 --> 30:04.840 Instanzen sich angeguckt wird. 30:04.920 --> 30:07.900 Also hier Zufallsgrafen mit M gleich 3 N Kanten. 30:07.900 --> 30:12.820 Und jetzt haben wir hier eine Vielzahl von Varianten. 30:18.930 --> 30:24.530 In den Spalten steht die Auswahlregel. 30:25.270 --> 30:28.730 Das hier ist FIFO, Highest Level und dann dieses Modified FIFO. 30:32.390 --> 30:36.750 Also wenn ich eine Algorithm-Engineering-Qualifikationsarbeit vergeben 30:36.750 --> 30:40.290 würde, ich würde darum bitten, das ein bisschen anders darzustellen. 30:40.430 --> 30:41.930 Aber so ist es halt jetzt da in dem Buch. 30:43.970 --> 30:47.290 Und dann hier sind diese ganzen Heuristiken drin. 30:48.430 --> 30:51.270 Basic ist sozusagen nichts Zusätzliches. 30:52.370 --> 30:59.650 LN ist Spezialbehandlung von Knoten, die das Ziel nicht mehr erreichen 30:59.650 --> 30:59.990 können. 31:00.130 --> 31:02.950 Local Relabeling Heuristik steht LRH. 31:04.190 --> 31:06.210 GH ist Global Relabeling Heuristik. 31:07.630 --> 31:11.570 Und Leda ist dann die Implementierung, die in dieser Library of 31:11.570 --> 31:14.730 Efficient Data Types und Algorithms drin ist, wo sie dann im 31:14.730 --> 31:18.230 Wesentlichen ein Highest Level Algorithmus haben, mit all diesen 31:18.230 --> 31:20.590 Tricks und noch einem Ding, das sie nicht verraten. 31:21.050 --> 31:25.230 Wahrscheinlich um sich so einen gewissen Competitive Edge da nicht zu 31:25.230 --> 31:25.630 vergeben. 31:26.270 --> 31:29.350 Wir werden aber sehen, dass dieser Edge gar nicht so riesig ist. 31:31.970 --> 31:36.770 Und die zwei Zeilen untereinander sind dann die 1000 Knoten und 2000 31:36.770 --> 31:37.570 Knoten. 31:37.970 --> 31:42.830 Und ich habe jetzt immer fettrot gefärbt, die kürzeste 31:42.830 --> 31:43.350 Ausführungszeit. 31:44.390 --> 31:48.710 Das ist jetzt für die kleinen Graphen, aber das ist analog auch für 31:48.710 --> 31:50.510 die größeren, wie wir hier jeweils sehen. 31:51.090 --> 31:54.170 Und da sehen wir, naja, also da ist diese Modified FIFO die beste. 31:57.090 --> 32:01.270 Man braucht Global Relabeling und da ist ein großer Sprung. 32:01.610 --> 32:07.650 Also Basic, LN, Local Relabeling, das bringt alles Verbesserungen, 32:07.790 --> 32:08.430 aber nicht viel. 32:08.530 --> 32:09.970 Oder das ist sogar eine Verschlechterung. 32:10.590 --> 32:14.430 Aber dann hier so, päng, geht es plötzlich um zwei Größenordnungen die 32:14.430 --> 32:15.090 Laufzeit runter. 32:15.270 --> 32:17.530 Also Global Relabeling ist wirklich ganz, ganz wichtig. 32:17.710 --> 32:17.930 Frage? 32:19.110 --> 32:19.570 Additiv. 32:19.650 --> 32:21.350 Also da kommt immer eine Heuristik dazu. 32:22.100 --> 32:22.370 Genau. 32:23.850 --> 32:26.150 Ja, das wäre überraschend, wenn da zwei komplett verschiedene 32:26.150 --> 32:27.950 Heuristiken zum gleichen Ergebnis führen. 32:28.230 --> 32:29.850 Das ist eher so, GAP bringt nichts. 32:33.310 --> 32:36.430 Hier bei Highest Level bringt GAP durchaus was. 32:37.810 --> 32:40.170 Also da habe ich durch GAP eine deutliche Verbesserung. 32:40.630 --> 32:45.010 Das liegt wahrscheinlich daran, das wäre jetzt meine Hypothese 32:45.010 --> 32:48.390 tatsächlich, dass GAP irgendwie mit dem Highest Level was zu tun hat. 32:48.390 --> 32:51.710 Weil da mache ich oben Dinge und dann könnten unten was ausgedünnt 32:51.710 --> 32:53.930 werden, während das bei FIFO wahrscheinlich einfach gar nicht 32:53.930 --> 32:56.470 passiert, dass diese Gaps auftreten. 32:58.810 --> 33:02.590 Genau, bei FIFO bringt GAP auch nichts, aber bei Highest Level bringt 33:02.590 --> 33:02.850 es was. 33:02.950 --> 33:04.110 Das ist schon mal interessant zu sehen. 33:04.630 --> 33:09.170 Dann dieser Tchaikowsky-Goldberg-Instanzen-Familie 1. 33:10.930 --> 33:14.470 Da ist Leder am besten. 33:14.470 --> 33:21.230 Also Highest Level mit Leder, aber es ist keine deutliche Verbesserung 33:21.230 --> 33:25.490 gegenüber FIFO oder Modified FIFO. 33:25.670 --> 33:27.670 Das sind so 10%. 33:28.610 --> 33:32.370 Hier bringt GAP sogar eine Verlangsamung, eine kleine. 33:33.590 --> 33:37.150 Einfach, weil das überhaupt mitzuhalten, ob dann GAP ist, kostet was 33:37.150 --> 33:38.690 und es ist scheinbar nie anwendbar. 33:39.620 --> 33:45.730 Und das gilt hier auch für die Highest Level-Horistik. 33:45.810 --> 33:50.010 Aber die anderen bringen auch nichts. 33:50.190 --> 33:54.430 Nur das Global Relabeling hat wieder ein bis zwei Größenordnungen 33:54.430 --> 33:55.530 Beschleunigung gebracht. 33:59.920 --> 34:04.260 Interessanterweise hier bei dem großen Graphen, der verhält sich ganz 34:04.260 --> 34:05.340 anders als der kleine. 34:07.180 --> 34:09.440 Aber wir bleiben jetzt mal bei dem Kleinen. 34:11.040 --> 34:19.020 Bei dem CG2 ist es wieder so, dass Leder am besten ist. 34:22.540 --> 34:25.740 Aber auch der Modified FIFO ist es nicht. 34:27.220 --> 34:28.400 Nee, das ist Quatsch. 34:29.140 --> 34:35.380 Genau, also das ist der einzige, wo Leder mit Abstand am besten ist 34:35.380 --> 34:39.300 und wo außerdem der Highest Level mit Abstand besser ist als die 34:39.300 --> 34:40.300 anderen Algorithmen. 34:42.980 --> 34:45.060 GAP bringt nichts oder wenig. 34:46.640 --> 34:51.720 Also dieses Cherkassky-Goldberg-2 ist scheinbar eine Instanzfamilie, 34:51.860 --> 34:54.180 die schlecht ist für die FIFO-Regel. 34:54.560 --> 34:56.320 Wo Highest Level dann wirklich was bringt. 34:58.800 --> 35:01.580 Die Frage, die man sich dann immer stellen muss, sind die Instanzen, 35:01.660 --> 35:02.660 die man in der Praxis hat. 35:02.960 --> 35:04.340 Haben die auch die Eigenschaft? 35:05.700 --> 35:07.240 Und das ist dann kompliziert. 35:08.900 --> 35:11.060 Und das ist jetzt von Ahuja-Magnanti-Orlean. 35:11.460 --> 35:15.920 Da sind jetzt die besten Laufzeilen irgendwie weit gestreut über alle 35:15.920 --> 35:17.080 Auswahlheuristiken. 35:18.400 --> 35:22.380 Wobei halt die Highest Level nur mit der obskuren Lederoptimierung was 35:22.380 --> 35:22.780 bringt. 35:24.640 --> 35:25.120 Und... 35:26.440 --> 35:27.780 Oh Moment, hier... 35:29.260 --> 35:32.660 Es ist tatsächlich so, dass Global Relabeling hier was kostet. 35:33.400 --> 35:35.600 Da habe ich mich vertan, da war das das Beste. 35:36.740 --> 35:37.800 Das ist interessant, ne? 35:38.660 --> 35:42.760 Also das ist der einzige Fall, wo das Global Relabeling nichts bringt. 35:43.620 --> 35:45.160 Aber, ja, überraschend. 35:45.320 --> 35:47.880 Könnte auch ein Übertragungsfehler sein, frage ich mich gerade. 35:48.840 --> 35:50.660 Weil das dann doch so überraschend ist. 35:50.660 --> 35:51.780 Genau, das ist auch so was. 35:51.860 --> 35:57.180 Wenn Sie Experimente machen, dann sollten Sie sich überlegen, verstehe 35:57.180 --> 35:57.660 ich Daten? 35:58.380 --> 36:02.980 Und wenn Sie welche nicht verstehen, das ist wichtig, dass Sie dann 36:02.980 --> 36:03.720 nachprüfen. 36:04.220 --> 36:05.740 Haben Sie da Daten falsch übertragen? 36:06.300 --> 36:08.780 Oder sind Sie vielleicht sogar einer großen Entdeckung auf der Spur? 36:09.440 --> 36:11.480 Also da muss man dann genau hingucken. 36:11.660 --> 36:15.340 Und im allerschlimmsten Fall, wenn Sie das nicht machen, bezichtigt 36:15.340 --> 36:16.660 man Sie dann hinterher der Datenfälschung. 36:17.580 --> 36:18.920 Auch wenn es nur ein Versehen war. 36:20.660 --> 36:23.780 Aber zum Glück in einer Vorlesung muss ich mich da wahrscheinlich 36:23.780 --> 36:26.040 nicht so hart prüfen lassen. 36:27.220 --> 36:30.120 Und wir sehen halt, es sind sehr stark unterschiedliche Laufzeiten. 36:30.320 --> 36:34.360 Also das ist so ein Maximum Flow, ist so ein bisschen kitzliges 36:34.360 --> 36:36.080 Problem, was Laufzeiten angeht. 36:36.520 --> 36:38.240 Weil es eben sehr instanzabhängig ist. 36:39.060 --> 36:42.780 Dann haben die hier mal etwas größere Instanzen noch angeschaut. 36:42.840 --> 36:44.560 Bis zu 20.000 Knoten. 36:46.140 --> 36:49.340 Und jetzt wieder über diese vier Instanzfamilien. 36:49.340 --> 36:53.140 Ich habe hier wieder die Regeln. 36:53.840 --> 36:56.260 FIFO heißt Label Modified FIFO. 36:56.980 --> 37:00.040 Und hier Global Relabeling Gap. 37:01.400 --> 37:04.820 Und ich habe mir jetzt nur die mit allen Heuristiken eingeschaltet 37:04.820 --> 37:07.840 angeschaut und die größte Instanz jeweils. 37:08.180 --> 37:13.480 Und da sehen wir, dass für Random ist es halt dieser Modified FIFO. 37:14.440 --> 37:17.100 Allerdings mit geringem Abstand über die anderen. 37:17.100 --> 37:23.460 Für CG1 ist es die Leder-Implementierung von Highest Level. 37:23.600 --> 37:25.880 Für CG2 ist es wieder Highest Level. 37:26.680 --> 37:29.260 Und jetzt mit deutlichem Abstand. 37:29.460 --> 37:34.680 Da haben die, also mit einem kleinen Abstand gegenüber der, ich sage 37:34.680 --> 37:36.200 mal Disclosed Highest Level. 37:36.680 --> 37:39.060 Aber die anderen sind zwei Größenordnungen langsamer. 37:39.660 --> 37:43.620 Also das ist wieder ein interessantes Zeichen, dass da bei CG2 37:43.620 --> 37:44.900 interessante Dinge passieren. 37:45.820 --> 37:50.340 Und bei Ahuja Magnanti Orlin passiert eigentlich überhaupt nichts 37:50.340 --> 37:50.760 Spannendes. 37:50.880 --> 37:51.860 Die sind irgendwie alle gleich gut. 37:52.920 --> 37:54.140 Fragen zu den Messungen? 37:55.740 --> 37:56.120 Gut. 37:59.960 --> 38:09.740 Ein neueres Ergebnis, das ich jetzt doch mal nennen wollte, ist, wenn 38:09.740 --> 38:15.020 man sich diese Algorithmen auf realistischen Instanzen anschaut, dann 38:15.020 --> 38:17.040 kann man wieder fragen, was sind realistische Instanzen? 38:17.140 --> 38:18.580 Das kommt auf die Anwendung an. 38:19.000 --> 38:20.540 Aber wir haben das gesehen für Bildverarbeitungsinstanzen. 38:21.280 --> 38:22.860 Wir brauchen es für Graph-Partitionierung. 38:24.460 --> 38:29.160 Da war das eigentlich immer so, dass die Highest Level Regel 38:29.160 --> 38:30.460 schlechter ist als FIFO. 38:31.840 --> 38:34.560 Und was noch spannender ist, dass es andere Algorithmen gibt, die 38:34.560 --> 38:36.100 nochmal viel schneller sind. 38:37.440 --> 38:41.100 Die dann gar keine so guten Worst-Case-Schranken haben. 38:41.240 --> 38:42.640 Die sind vergleichbar mit DINITS. 38:43.680 --> 38:46.680 Und deshalb wollte ich da mal den Titel von diesem relativ neuen 38:46.680 --> 38:48.760 Papier nennen, das das macht. 38:49.060 --> 38:53.040 Fast and More Dynamic Maximum Flow by Incremental Breath First Search. 38:53.100 --> 38:54.100 Das klingt harmlos. 38:54.940 --> 38:56.500 Der Algorithmus ist aber relativ kompliziert. 39:00.840 --> 39:04.920 Insbesondere verallgemeinert er diese Idee der Pre-Flows nochmal 39:04.920 --> 39:07.480 zusätzlich zu sogenannten Pseudo-Flows. 39:07.600 --> 39:10.680 Da ist es jetzt auch erlaubt, dass Knoten ein Defizit haben. 39:10.960 --> 39:13.800 Also dass da mehr rausfließt als rein. 39:14.400 --> 39:15.700 Und dann wird das Ganze viel symmetrischer. 39:16.320 --> 39:19.240 Da werden Abstände auch zur Quelle und zur Senke verwaltet. 39:20.540 --> 39:25.220 Es ist für mich als Nicht-Experten ein bisschen schwer 39:25.220 --> 39:27.440 nachzuvollziehen, was da genau passiert. 39:28.120 --> 39:31.780 Aber offenbar ist das für realistische Instanzen deutlich schneller 39:31.780 --> 39:33.500 als Preflow Push. 39:34.660 --> 39:35.600 Was ganz spannend ist. 39:35.680 --> 39:39.240 Und da ist dann sicherlich auch ein interessantes offenes Problem für 39:39.240 --> 39:43.220 das Algorithm Engineering, wie man Lücken zwischen Theorie und Praxis 39:43.220 --> 39:43.600 schließt. 39:43.680 --> 39:47.040 Kann man da irgendwie vielleicht eine Variante von dem Algorithmus zum 39:47.040 --> 39:49.960 Beispiel herleiten, die beweisbar besser ist als das. 39:50.900 --> 39:53.100 Zum Beispiel so gut wie Highest Level Preflow Push. 39:54.680 --> 39:56.320 Meine Vermutung wäre ja. 39:56.700 --> 40:00.000 Aber wahrscheinlich ist es nicht genau der Algorithmus, den die da 40:00.000 --> 40:00.940 implementiert haben. 40:01.080 --> 40:03.280 Und das ist sicherlich ein schwieriges Problem. 40:04.360 --> 40:07.200 So, dann sind wir am Ende des Kapitels zu Flows und Matchings 40:07.200 --> 40:07.840 angekommen. 40:08.260 --> 40:09.560 Die nochmal zusammenfassen. 40:10.080 --> 40:13.300 Das ist eine natürliche Verallgemeinerung von kürzesten Wegen. 40:13.400 --> 40:15.720 Wir gehen von einem Pfad zu vielen Pfaden. 40:15.720 --> 40:18.700 Ist aber auch ein logischer nächster Schritt in so einer Vorlesung. 40:19.320 --> 40:20.600 Es gibt viele Anwendungen. 40:21.100 --> 40:26.160 Und es ist so eines der allgemeinsten Grafenprobleme, die man noch mit 40:26.160 --> 40:29.560 kombinatorischen Algorithmen in Polynomialzeit lösen kann. 40:30.000 --> 40:32.880 Es gibt nochmal ein paar Verallgemeinerungen davon, dann auch mit Min 40:32.880 --> 40:37.700 -Cost -Flows, Multicommodity-Flows etc., die aber alle wieder ähnliche 40:37.700 --> 40:40.660 Techniken verwenden, sodass sie da schon einen großen Schritt in die 40:40.660 --> 40:41.620 Richtung gemacht haben. 40:41.620 --> 40:46.200 Dieses Zwischenreicht zwischen, ich sag mal, trivialen Problemen wie 40:46.200 --> 40:52.960 kürzesten Wegen und NPH-Problemen sich anzueignen, liefert schöne 40:52.960 --> 40:55.520 Beispiele für nicht-triviale Algorithmenanalyse. 40:55.960 --> 40:59.500 Insbesondere die Potentialmethode, die Sie nicht verwechseln sollten 40:59.500 --> 41:03.720 mit Knotenpotentialen, die wir ja auch kennengelernt haben. 41:05.220 --> 41:08.060 Wir haben ein schönes Beispiel für Algorithmen-Engineering, wo wir 41:08.060 --> 41:11.320 sehen, praktische Instanzen verhalten sich nicht wie Worst-Case 41:11.320 --> 41:12.000 -Instanzen. 41:14.800 --> 41:17.960 Heuristiken, Details, Eingabe-Eigenschaften sind wichtig. 41:18.720 --> 41:22.460 Und wir haben wieder Beispiele für Datenstrukturen gesehen, Bucket 41:22.460 --> 41:27.140 Queues, geschickte Graph-Repräsentationen und zumindest erwähnt, diese 41:27.140 --> 41:31.040 Dynamic -Tree-Data-Structure, mit denen ich in logarithmischer Zeit, 41:31.100 --> 41:34.200 in langer Pfade, Augmentierungen durchführen kann. 41:35.740 --> 41:38.560 Weitere Fragen zum Flow-Kapitel? 41:40.740 --> 41:45.000 Damit sind wir dann auch am Ende unseres großen Teils über Graphen 41:45.000 --> 41:48.560 -Algorithmen und werden dann nächste Woche mit randomisierten 41:48.560 --> 41:52.000 Algorithmen weitermachen und der Sebastian macht jetzt mit der Übung weiter.