Ja, guten Tag, wir haben beim letzten Mal angefangen, uns über
minimale Spannbäume zu unterhalten.
Also, wie wähle ich aus einem ungerichteten Graphen mit gewichteten
Kanten eine Kantenmenge minimalen Gesamtgewichts, sodass die Knoten
durch diese ausgewählten Kanten trotzdem alle verbunden sind.
Das ist ein Baum, wie man sich leicht überlegen kann.
Und wie finde ich den?
Und das ist halt eins der ganz wenigen fundamentalen kombinatorischen
Optimierungsprobleme auf Graphen, die man effizient lösen kann und hat
auch viele Anwendungen und deshalb schauen wir uns das im Detail halt
an.
Wir hatten dann zunächst mal zwei mathematische Eigenschaften
festgestellt, die sozusagen Bausteine liefern, um daraus konkrete
Algorithmen zu konstruieren.
Das war die Schnitteigenschaft, wenn wir den Graphen in zwei Teile
schneiden, dann wissen wir, dass die leichteste zerschnittene Kante
Teil eines minimalen Spannbaums sein kann und umgekehrt, die schwerste
Kante auf einem Kreis wird nicht benötigt.
Dann hatten wir den Algorithmus von Jarnik und Prim kennengelernt, der
so einen Spannbaum wachsen lässt, ausgehend von einem beliebigen
Startknoten und das Spannende war dann, das war fast genau Dijkstra's
Algorithmus für kürzeste Wege, die Unterschiede waren extrem
übersichtlich, also ein Unterschied war, dass wir einen beliebigen
Startknoten wählen können,
ein anderer war, dass die Distanz, was anderes bedeutet, die bedeutet
nämlich die Entfernung der Kante von dem Baum und nicht vom
Startknoten und wird durch ein einzelnes Kantengewicht bestimmt und
wir haben dann Distanz 0 heißt, der Knoten ist schon in dem Baum und
wir hatten dann hier die Bedingung, aha, wir gucken uns eine Kante an,
von einem neu zu scannenden Knoten und wenn diese Kante leichter ist
als die leichteste Kante, die diesen Knoten vorher erreicht, dann
brauchen wir die und das ist dann auch das Gewicht, während bei
Dijkstra's Algorithmus war das die Summe von dem Gewicht der Kante und
der kürzesten Fahrtlänge nach U, das ist vielleicht der wichtigste
Unterschied zwischen den beiden Algorithmen.
Ja, Analyse verläuft eigentlich sehr ähnlich wie bei Dijkstra's
Algorithmus, hat die gleiche Komplexität eigentlich, zumindest wenn
man die Prioritätslisten verwendet, die wir kennengelernt haben,
insbesondere die binären Heaps.
Das gilt auch für diesen Fibonacci-Heap, den wir in Algorithmen 2
machen werden.
Es gibt allerdings Prioritätslisten, die nur funktionieren, wenn die
Eingaben monoton sind, das heißt, das Minimum der Prioritätsliste
verändert sich nicht und das gilt aber nicht mehr beim Janik-Priem
-Algorithmus.
Insofern kann es dann passieren, dass der Janik-Priem-Algorithmus
sogar ein bisschen langsamer ist, als der Dijkstra-Algorithmus, wenn
man solche Prioritätslisten einsetzt.
So, dann wollen wir einen zweiten Algorithmus kennenlernen, das ist
Kruskals Algorithmus, ausnahmsweise hat ihn der Herr Kruskal 1956
erfunden und es hat noch kein Tscheche vorher gemacht.
Und der ist mindestens genauso fundamental wie dieser Janik-Priem
-Algorithmus und auch in der Praxis ganz nett und wir lernen da eine
spannende Datenstruktur kennen, das ist also alles Grund genug, um
Ihnen noch einen zweiten Algorithmus zur Konstruktion minimaler
Spannbäume zu zumuten.
Hier ist der Ansatz, dass wir nicht einen einzelnen Baum wachsen
lassen, sondern einen Wald.
Also was da passiert, ist, dass da am Anfang, also ein Wald ist ja
eine Kollektion von Bäumen, und am Anfang haben wir sehr einfache
Bäume, nämlich nur die Knospen, jeder Knoten ist sein eigener Baum,
und die wachsen jetzt immer weiter zusammen.
Also entsteht dann ein Dickicht, das irgendwann bis zu einem Baum
zusammenwächst.
Ja, das steht hier auch, wir initialisieren die Menge der Baumkanten
zur leeren Menge.
Und was wir jetzt machen, ist, wir schauen uns alle Kanten an, und
zwar in der Reihenfolge aufsteigenden Gewichts, also die leichteste
Kante zuerst.
Und jedes Mal, wenn wir uns so eine Kante UV anschauen, fragen wir,
okay, wie ist das denn mit dem Wald, den wir im Moment haben, liegt
die Kante innerhalb eines Baums, oder verbindet sie zwei Bäume von T?
Wenn sie innerhalb eines Baums liegt, lassen wir sie weg, ich erkläre
gleich noch, warum.
Wenn sie zwei verschiedene Bäume verbindet, dann fügen wir sie ein,
und damit hat der Wald sich in Zukunft so verändert, dass er jetzt
einen Baum weniger hat, nämlich diese beiden vorher getrennten Bäume
sind jetzt durch diese Kante zusammengeführt worden.
Und am Ende gebe ich diesen Baum zurück.
Muss man sich jetzt überlegen, warum das korrekt ist, werde ich gleich
tun, aber machen wir erstmal ein Beispiel.
Hier ist ein vollständiger Graf mit vier Knoten, die leichteste Kante
ist die hier mit Gewicht 2.
Naja, die verbindet offenbar zwei Bäume, weil das sind ja zwei
triviale Bäume.
Dann füge ich die hinzu und danach ist das ein Baum und die beiden
sind zwei triviale weitere Bäume in unserem Wald.
Hat jemand schon eine Idee, warum das korrekt ist?
Wie kann man das beweisen?
Diese Kante hier ist eine minimale Spannbaumkante.
Naja, ich habe hier mal so einen Cut eingezeichnet von der B, vom
Resttrend, und das ist tatsächlich die leichteste Kante, die da
durchgeht.
Was jetzt nicht so überraschend ist, das ist ja sogar global die
leichteste Kante.
Dann machen wir mal weiter.
Die zweitleichteste Kante ist die hier und hat Gewicht 3.
Die verbindet diesen Baum mit diesem Baum.
Also sagt der Cross-Cut-Algorithmus, die tun wir rein.
Warum ist das korrekt?
Wir können uns zum Beispiel diesen Schnitt hier anschauen.
Da ist das die leichteste rausgehende Kante.
Und vielleicht sehen wir jetzt schon Muster, also wir wollen jedes
Mal, wenn wir eine Kante rein tun, mithilfe von Cross-Cut-Algorithmus,
einen Schnitt identifizieren, sodass uns die Schnitteigenschaft
beweist, dass das korrekt war, was wir gemacht haben.
Und wie geht das?
Das ist ja ganz einfach, wir haben ja hier, die Kante fügt zwei Bäume
zusammen, dann können wir einfach einen Schnitt betrachten, der einen
der Bäume vom Rest des Grafen isoliert.
Und jetzt behaupte ich, die leichteste Kante, die über diesen Schnitt
geht, ist gerade die Kante, die wir gerade betrachten.
Weil, stellen Sie sich vor, es gäbe eine leichtere Kante, dann wäre
die ja vorher schon betrachtet worden.
Wir gucken ja die Kanten in aufsteigender Gewichtsreihenfolge an,
folglich wäre die dann vorher schon eingefügt worden und die wären
bereits in einer Komponente, diese beiden Bäume.
Folglich sind alle anderen Kanten schwerer oder genauso schwer wie die
Kante, die wir gerade haben.
Dann machen wir mal weiter, also wir sind uns jetzt vielleicht einig,
dass das eine MST-Kante ist.
Die nächstleichtere Kante hat Gewicht 4 und die verbindet zwei Knoten,
also wir haben ja jetzt hier einen trivialen Baum und da einen Baum
mit drei Knoten und die liegt innerhalb dieser Komponente CBD.
Dann lassen wir sie weg.
Warum ist das korrekt?
Kann mir das jemand erklären?
Ja, okay, was sagen Sie da?
Ja, genau, also im Endeffekt ist es das, haben Sie beide so ähnlich
gesagt.
Oder ich würde es jetzt noch stärker koppeln an diese
Kreiseigenschaft.
Wir haben ja gesagt, die schwerste Kante in einem Kreis wird nicht
benötigt.
Und das ist jetzt tatsächlich so, wenn ich einen Baum habe und da eine
zusätzliche Kante dazu tue, dann schließe ich immer einen Kreis und
diese Kante ist jetzt die schwerste Kante in diesem Kreis, weil alle
Kanten, die ich vorher betrachtet habe, sind ja leichter.
Genau, also jetzt habe ich mir diese Kante angeschaut, dann ist die
nächstschwerere Kante hier die 6.
Wenn ich mir diesen Schnitt anschaue, ist das da auch wieder die
leichteste.
Aha, das ist tatsächlich korrekt, ich bringe den dazu.
Jetzt habe ich nur noch eine Komponente, jetzt wird nichts mehr
passieren.
Also jetzt gucke ich mir danach natürlich noch die Kanten mit Gewicht
7 und 9 an, aber die sind alle innerhalb eines Baumes, werden nicht
mehr benötigt.
Ich habe den minimalen Spannbaum identifiziert.
Jetzt hier nochmal etwas formaler den Korrektheitsbeweis.
Wir müssen im Endeffekt zwei Fälle unterscheiden.
Wenn hier die beiden Knoten in verschiedenen Teilbäumen sind, dann
benutze ich die Schnitteigenschaft, und die sagt uns, diese Kante ist
die leichteste Kante in dem Schnitt, der definiert wird durch die
Komponente von U und dem Rest des Graphen.
Wir hätten hier genauso gut schreiben können, Komponente von V, weil
das ist ja völlig symmetrisch, aber das führt auch zu dem gleichen
Ergebnis.
Hm?
Deshalb sagt uns die Schnitteigenschaft, dass U, V im minimalen
Spannbaum ist.
Sonst, also U, V sind in einem Teilbaum, dann ist U, V die schwerste
Kante in einem Kreis, und zwar der Kreis sieht so aus, das ist einmal
die Kante, ich fange bei U an, gehe zu V, und dann weiß ich ja, in
einem Baum gibt es eben einen Pfad von V nach U, und das schließt
diesen Kreis.
Also eine Eigenschaft eines Baums, haben Sie auch noch in der Übung
letztes Mal gesehen, ist ja, dass es zwischen zwei beliebigen Knoten
einen Pfad gibt.
Fragen dazu?
Also eigentlich ein relativ simpler Algorithmus, wir müssen uns jetzt
nur noch überlegen, wie implementiere ich denn das effizient?
Also auf den ersten Blick klingt das so, aha.
Ich habe Knoten U, Knoten V, und dann müsste ich eigentlich jetzt,
wenn ich das naiv mache, einen Weg von U nach V suchen in diesem Baum.
Was dann bedeutet, dieser Baum, der kann bis Theta N Knoten enthalten,
müsste ich da irgendwie Tiefensuche oder Breitensuche auf diesem Baum
machen, dann würde ich einen Algorithmus kriegen, der sowas wie
Laufzeit m mal n hat.
Das möchte ich nicht.
Und es gibt tatsächlich eine viel effizientere Datenstruktur, die man
dafür verwenden kann und die auch noch viele andere Anwendungen hat,
das ist die sogenannte Union Find Datenstruktur.
Die hat ihren Namen daher, weil sie Operationen unterstützt, die Union
und Find heißen.
Was das ist, sage ich gleich.
Was wir da verwalten, ist eine Partition einer Menge.
Wir nehmen jetzt OBDA an, diese Menge ist einfach die Menge der ganzen
Zahlen 1 bis N.
Eine Partition zerlegt eine Menge in Teilmengen, M1 bis MK, mit der
Eigenschaft, dass die Vereinigung der Teilmengen die gesamte
Ursprungsmenge ist, also in dem Fall 1 bis N, und dass die Mengen
paarweise disjunkt sind.
Man nennt diese Teilmengen dann auch Blocks einer Partition.
Und Union Find ist jetzt eine relativ spezialisierte Datenstruktur,
die eigentlich nur zwei Operationen auf so einer Partition zulässt.
Also am Anfang habe ich die triviale Partition, wo jeder Knoten sein
eigener Block ist.
Und dann gibt es zwei Operationen in Union, ich gebe zwei Elemente an,
die liegen im Allgemeinen in zwei Blöcken und die werden jetzt
zusammengefügt zu einem größeren Block.
Und dann gibt es noch die Find-Operation, da gebe ich ein Element und
die gibt mir einen eindeutigen Bezeichner für diesen Block.
Wie man das im Detail implementiert, hat man jetzt eine gewisse
Freiheit.
Aber wir wollen jetzt eine sehr konkrete, sehr einfache
Implementierung weiterverfolgen, die folgendermaßen funktioniert.
Ich habe das jetzt als eine Klasse mal deklariert, die wird
initialisiert, indem man ihr einfach eine ganze Zahl übergibt und die
sagt dann, okay, das ist jetzt sozusagen die Größe dieser Partition
und die Elemente werden repräsentiert durch die Zahlen 1 bis N.
Ich habe einen Array von Parent-Indizes, das sind in diesem Fall auch
einfach wieder ganze Zahlen zwischen 1 und N.
Und die Idee ist die folgende, für jeden Block unserer Partition haben
wir einen Repräsentanten.
Also wir wählen eine beliebige Zahl, die in diesem Block drin ist, aus
und sagen, du repräsentierst diesen Block und die wird hinterher
dieser eindeutige Bezeichner dieses Blocks sein.
Und die Idee ist, dass diese Parent-Referenzen hier uns zu diesem
Repräsentanten führen.
Also am Anfang ist das ganz klar, da verweist jeder auf sich, ich bin
mein eigener Repräsentant.
Und später kann es aber größere Blöcke geben und dann wollen wir, dass
wenn wir hier ein Find auf so eine Zahl i machen, dass wenn wir diesen
Referenzen folgen, solange bis sie auf sich selbst verweisen, dass wir
dann beim Repräsentanten ankommen.
Insofern ist die Operation Find ganz einfach, da übergibt man halt
irgendeine Zahl zwischen 1 und N und die fragt sich, bin ich bereits
der Repräsentant, das sieht man daran, dass Parent i gleich i ist,
dann bin ich fertig.
Und sonst übergebe ich Find von Parent von i.
Also ich habe das jetzt rekursiv formuliert, wir werden gleich noch
sehen, warum.
Und wenn diese Verweise tatsächlich diese Eigenschaft haben, dass ich
da im Endeffekt so einen Wurzelbaum habe, mit einer eindeutigen
Wurzel, dann wird das ja auch irgendwann terminieren.
Das sagt uns aber diese Invariante schon.
Die sagt uns nur, dass man irgendwann beim Repräsentanten landet und
das reicht uns auch schon.
Also dann wird es jedenfalls so sein, wenn ich denen lange genug
folge, lande ich irgendwann bei so einem Self-Loop, das finde ich
hiermit fest und dann gebe ich eben diesen Repräsentanten zurück.
Fragen dazu?
So, jetzt muss man sich noch überlegen, wie die Union-Operation
funktioniert, dafür definiere ich erstmal noch eine Hilfsfunktion,
Link, die ist sowas ähnliches wie Union, nur dass ich jetzt zusätzlich
verlange, dass die beiden Parameter i und j Repräsentanten
verschiedener Blöcke sind.
Das ist sozusagen der spannende Fall.
Und das mache ich ganz einfach, ich kann jetzt einfach, wenn ich sage,
i und j sollen jetzt im gleichen Block liegen, um diese Invariante
hier aufrecht zu halten, lasse ich einfach den Parentref von i auf j
zeigen.
Ich hätte es auch umgekehrt machen können, j auf i, aber wie ich es
auch mache, damit wird diese Invariante hier hergestellt und ich habe
tatsächlich diese Blocks zusammengefügt mit einer einfachen Zuweisung
im Endeffekt.
Genau,
also diese i und j sind Repräsentanten verschiedener Blöcke, das ist
ein Spezialfall, aber der allgemeine Fall Union ist dann jetzt so,
dass ich erstmal teste, sind find i ungleich find j, dann muss ich gar
nichts machen, ist find i gleich find j, dann liegen die im gleichen
Block, dann ist nichts zu tun, und sonst mache ich halt eine Link
-Operation auf find i, find j.
Mit find i finde ich ja den Repräsentanten von i, mit find j finde ich
den Repräsentanten von j, die werden zusammengelinkt und fertig.
Also das erklärt jetzt die Semantik, das ist eine super einfache
Datenstruktur, also wie viele Zeilen Code haben wir hier?
Eigentlich nur 1, 2, 3, 4 Zeilen plus ein paar Deklarationen.
Und damit wird jetzt schon eine Datenstruktur, die was Nützliches
macht, definiert, ist leider noch nicht so schnell, wie wir es gerne
hätten.
Also Union ist zwar sehr schnell, braucht nur konstante Zeit, aber das
Find könnte jetzt lineare Zeit brauchen, im schlechtesten Fall, also
wenn ich so sehr lange Ketten hier aufbaue, ist das nicht gut.
Und deshalb verfeinert man diese Union-Find-Datenstrukturen durch
Maßnahmen, um diese Pfade beim Find kurz zu halten.
Und da gibt es zwei Techniken, die ich Ihnen jetzt vorstellen möchte.
Das eine ist die Pfadkompression, hier ist jetzt einfach wieder diese
Klassendeklaration, wir haben jetzt nur die Operation Find
ausgetauscht, das ist aber auch der alte Code, außer dieser einen
Zeile hier.
Also wir erinnern uns, der alte Code war Rekursiv, wenn ich fertig
bin, bin ich fertig, okay.
Jetzt habe ich erstmal eine temporäre Variable i' eingefügt, die macht
das Find von Parent i, berechnet also das eigentliche Ergebnis, das
könnte ich jetzt direkt zurückgeben, aber ich mache jetzt was
Zusätzliches, das nennt sich Pfadkompression.
Wenn ich jetzt schon mal den Aufwand da reingesteckt habe, den
Repräsentanten von i zu finden, dann kann ich mir das ja fürs nächste
Mal merken und setze einfach Parent i auf i'.
Und das ist jetzt der Grund, wieso ich das hier Rekursiv gemacht habe,
das passiert ja auf jeder Rekursionsebene.
Das heißt, wenn ich einmal für i und so eine lange Kette das aufrufe,
dann werden nach dem Aufruf alle Verweiser auf diesem Pfad direkt auf
den Repräsentanten verweisen.
Das heißt, ich habe jetzt einmal große Kosten gehabt, aber danach nie
wieder sozusagen.
Wenn es das jetzt schon war, wenn ich genau an der Stelle nochmal
zugreife, haben die alle Kosten von 1, nur um eine Parentreferenz
nochmal nachzuverfolgen.
Gibt es dazu Fragen?
Eine zweite Maßnahme ist Union by Rank.
Dafür muss ich ein bisschen mehr machen, also hier hatte ich nur eine
Zeile eingefügt.
Hier brauche ich ein bisschen mehr, ich brauche zusätzliche Daten.
Das ist so ein Array von Rängen in dem Fall, aber eine ganz kleine
Zahl zwischen 0 und Log N brauche ich da nur.
Passt in ein paar Bits und es gibt sogar Tricks, um die sozusagen als
Untermieter in den Parent Array unterzubringen.
Aber da will ich hier nicht drauf eingehen.
Es ist einfacher zu sagen, wir haben ein weiteres Array Rank.
Wird auf 0 initialisiert.
Die Idee ist so ein bisschen, ich merke mir, wie groß oder wie viel
wurde mit diesen Blöcken schon gemacht und hänge dann die kleineren
Blöcke an die größeren dran und nicht umgekehrt.
Das ist die Idee hier.
Gucken wir uns mal an, wie das genauer läuft.
Also am Anfang sind die Ränge alle 0.
Die Link-Operation funktioniert jetzt so, die gleiche Variante wie
vorher.
Wenn i einen kleineren Rang hat als j, dann wird i an j gehängt.
Sonst wird j an i gehängt.
Also Parent i gleich j oder Parent j gleich i, abhängig davon, ob der
Rang kleiner oder größer ist.
Wenn es sogar so ist, dass der Rang gleich ist, dann hätte ich
natürlich auch beides machen können, dann wird der Rang inkrementiert.
Also wenn ich was Kleines an was Großes hänge, ist das sozusagen nicht
der Rede wert, das verändert den Rang des Größeren nicht.
Wenn ich aber zwei Bäume vom gleichen Rang aneinander hänge, dann
erhöht das deren Rang.
Und das wollen wir uns jetzt mal angucken, was das bewirkt.
Wir machen also jetzt eine Analyse nur für Union bei Rank.
Fahrtkompressionen wären mir nicht so viel zu machen.
Naja, und das ist jetzt im Wesentlichen wieder eine schöne
Übungsaufgabe, ich werde das hier nicht im Detail vorrechnen.
Es gibt eigentlich zwei Invarianten, die wir hier aufrechterhalten.
Das eine ist, der Pfad zu einem Repräsentanten X hat höchstens die
Länge Rang von X.
Warum ist das so?
Gucken wir uns das mal an.
Das stimmt am Anfang, am Anfang sind alle ihre eigenen Repräsentanten,
der Pfad hat Länge 0.
Wenn wir den Fall haben, nehmen wir mal irgendeinen Knoten in dem
kleineren Baum.
Der hat nach Indektionsvoraussetzungen Länge höchstens Rang I.
Und dann muss er noch eine zusätzliche Referenz verfolgen, nämlich die
Referenz von I nach J.
Also hat der Rang I plus 1.
Das ist aber, weil der Rang I kleiner Rang J ist, immer noch kleiner
gleich der Rang von J.
Und in dem Teilbaum von J hat sich eigentlich nichts geändert, weil
die haben ja ihren Repräsentanten behalten, folglich gilt da weiter
die Induktionsvoraussetzung, dass die Pfade höchstens längere Rang von
J haben.
Das ist die eine Invariante.
Die andere Invariante ist, wenn ich einen Repräsentanten X habe, dann
ist die Menge, die er repräsentiert, hat mindestens 2 hoch Rang von X
Elementen.
Und das kann man sich auch wieder relativ leicht überlegen, das gilt
am Anfang, da haben wir ja triviale Blöcke mit Größe 1, das ist gerade
2 hoch 0, also 2 hoch Rang von I für alle I.
Da kann sich nur was ändern, wenn sich irgendein Rang verändert und
das passiert aber nur an dieser Stelle, hier werden zwei Bäume mit
gleichem Rang vereinigt.
Naja, aber die Induktionsvoraussetzung sagt uns ja, diese beiden Bäume
haben mindestens 2 hoch Rang von I gleich 2 hoch Rang von J Elemente,
die füge ich zusammen, dann haben sie 2 mal Rang hoch I Elemente und
dann darf ich das auch inkrementieren, weil danach hat dieses Ding
halt 2 hoch Rang von I plus 1 Elemente.
Und das könnte man jetzt als Übungsaufgabe nochmal im Detail
durchführen.
Fragen dazu?
So, wenn ich diese Invarianten habe, dann folgt unmittelbar, das Feind
braucht höchstens Zeit von Log N.
Weil wenn ich irgendwo länger als Log N Referenzen verfolgen würde,
hieße das ja, ich habe auch irgendwo einen Teilbaum mit mehr als 2
hoch Log N Elementen, das kann aber nicht sein, es gibt ja nur N.
Damit habe ich jetzt die Zeit für eine Feindoperation auf O von Log N
reduziert, die Laufzeit vom Union bleibt hier erhalten, also dann
hätte ich sowas wie logarithmische Laufzeit für meine Basisoperation.
Wenn man aber jetzt Pfadkompressionen alleine nimmt, kommt man auf das
Gleiche.
Also man könnte nur Union bei Rang nehmen, kriegt logarithmische Zeit
für einen Feind.
Man könnte nur Pfadkompressionen nehmen, dann kriegt man auf Log N
amortisierte Zeit für Feind.
Eine spannende Frage ist, also der Beweis dazu, der ist jetzt nicht
schwierig, aber ein bisschen technisch, deshalb lasse ich den in der
Vorlesung weg, ihr könnt den im Buch finden, und die richtig spannende
Frage ist, was passiert, wenn ich beides mache?
Und da kommt dann das erste Mal was ziemlich Esoterisches raus.
Was aber trotzdem praktische Auswirkungen hat, also ich werde Ihnen
jetzt die Aussage erklären, aber nicht den Beweis.
Das würde uns wahrscheinlich mindestens eine komplette Vorlesung
kosten, diesen Beweis komplett zu erklären, und ich glaube, im zweiten
Semester haben Sie viele andere Sachen am Hut, das ist eher was für,
könnte man in Algorithmen 2 machen, aber eher was für eine
Spezialvorlesung.
Aber Sie sollten zumindest dieses Ergebnis mal gesehen haben, das ist
nämlich sehr spannend.
Also wir sagen, wenn ich M-Feind-Operationen und N-Link-Operationen
habe, das ist übrigens genau die Anzahl der Operationen, die Kruskalz
-Algorithmus auf dem Graph mit M-Kanten und N-Knoten hat, dann
brauchen wir dafür Zeit, M mal Alpha-T, M,N.
Was ist denn das für eine komische Funktion?
Das ist die sogenannte inverse Ackermann-Funktion, wer hat davon schon
mal gehört?
Die wenigsten, ne?
Deshalb erkläre ich es hier ja auch.
Alpha-T, M, N ist definiert als das kleinste i, sodass die Ackermann
-Funktion von i und M durch N aufgerundet größer gleich log N ist.
Wer weiß, was die Ackermann-Funktion ist?
Schon ein paar mehr, aber auch nicht so viele, das kommt eigentlich
auch erst im nächsten Semester Grundlagen theoretischer Informatik
dran.
Das ist eine Funktion, die man sich eigentlich ausgedacht hat, als
eine extrem theoretische Konstruktion, so nach der Devise.
Es gibt sogenannte primitiv-rekursive Funktionen, das sind eben
Funktionen, die durch sehr einfache Formen von Rekursionen definiert
sind, mit denen ich aber fast alles darstellen kann, was so typische
kombinatorische Ausdrücke oder so sind.
Binomial-Koeffizient, Exponentiation und 2 auf 2 auf 2 auf 2 auf 2, N
mal, das ist alles primitiv-rekursiv.
Und dann hat man sich überlegt, aha, aber es gibt auch so
doppeltrekursive Funktionen, ich werde da gleich ein Beispiel angeben,
die verhalten sich ganz komisch.
Und dann hat nämlich der Herr Ackermann irgendwann auch in den 30er
-Jahren oder so eine Funktion angegeben, die schneller wächst als jede
primitiv -rekursive Funktion.
Eigentlich eine Funktion, die eher auf den ersten Blick nach einem
mathematischen Spielzeug aussieht, wo man also sehr fundamentale
Einsichten mitgewinnt.
Wirklich so die theoretischen Aspekte der theoretischen Informatik,
sollte man meinen.
Aber irgendwie schöne mathematische Puzzles, aber man hätte eigentlich
nicht erwartet, dass solche Funktionen irgendwie in der Realität
auftreten.
Das ist eigentlich ein mathematisches Konstrukt.
So, und jetzt hat man aber gemerkt, aha, dieses Ding taucht
tatsächlich in so einer Datenstrukturanalyse auf und hat in dem Fall
auch positive Auswirkungen.
Warum ist das so?
Also, das ist erstmal diese Ackermann-Funktion, da gibt es
verschiedene Varianten von, aber das hier ist die, die tatsächlich für
die Analyse von diesem Union-Find-Datenstruktur verwendet wird.
Die heißt im Wesentlichen gut, also, die hat zwei Parameter und das
ist sozusagen so eine Gangschaltung.
Es geht erst langsam los mit erster Parameter, erster Gang, A1,j ist 2
hoch j.
Das wächst schon exponentiell, ist aber für die Maßstäbe der Ackermann
-Funktion Pille-Palle.
Zweiter Gang, A von 2,1, naja, muss ich gucken, das sehen wir gleich,
aber wir sehen schon, wenn Sie den kleinstmöglichen Parameter als
zweiten Parameter haben, und hier dieses i als ersten, dann kommen Sie
gerade mal einen weiter runter hiermit und dafür wird der da auf zwei
geschoben, das sieht jetzt noch harmlos aus, und jetzt kommt der
eigentlich komplizierte Teil, der das Ganze nicht primitiv-rekursiv
macht, A i,j ist A i minus 1 und dann der zweite Parameter ist wieder
ein rekursiver Aufruf, also Sie haben hier eine geschachtelte
Rekursion.
Und das ist bei einer primitiv-rekursiven Funktion gerade nicht
erlaubt und das führt zu dieser Explosion.
Und wir werden gleich sehen, das kann ich Ihnen auch beweisen, ohne
dass wir jetzt tiefere Einsichte brauchen, wenn man das hier glaubt,
das hier ist diese Laufzeit, man kann dann relativ leicht sehen, dass
die inverse Ackermann-Funktion eigentlich immer Werte kleiner gleich 4
annimmt, für alle Werte von m und n, die irgendwie physikalisch
realisierbar sind.
Und das werde ich Ihnen gleich demonstrieren.
Das heißt, wenn wir diesen Satz hier glauben, heißt das, die Laufzeit
ist höchstens 4 mal O von m.
Also eigentlich quasi linear.
Es gibt auch Linearzeitalgorythmen, echte Linearzeitalgorythmen, die
leider irgendwo da nochmal einen Laufzeitfaktor 20 drin haben, und
dann wundert man sich nicht, dass das hier in der Praxis dann doch
schneller ist.
Verstehen wir nochmal, was hier passiert.
Also die inverse Ackermann-Funktion, die wächst umso langsamer, je
schneller die normale Ackermann-Funktion selber wieder steigt.
Warum ist das so?
Also wir nehmen hier das kleinste i, das man links bei der Ackermann
-Funktion einsetzen muss, so damit dann der Gesamtwert größer gleich
log n ist.
Und dann ist dieses m durch n noch irgendein Parameter, da kann man
sich dann überlegen, aha, m durch n aufgerundet ist ja mindestens 1,
also im leeren Graphen brauche ich keine minimalen spannenden Wälder
suchen, eigentlich sogar mindestens 2, wenn man sagt, das ist ein
zusammenhängender Graph.
Nee, stimmt nicht, es könnte ja genauso viel Knoten wie Kanten geben,
also es ist 1 oder 2 mindestens.
Und ich habe ja gesagt, das hier ist diese Gangschaltungsparameter, es
wächst immer schneller.
In welchen Gang muss ich gehen von dieser Funktion, um größer log n zu
sein?
Log n ist halt, wenn ich höchstens 2 hoch 64 Eingaben da unterscheiden
kann, höchstens 64, also wie groß muss ich den linken Parameter
machen, selbst wenn der hier sehr klein ist, damit ich einen Wert
größer 64 kriege.
Und jetzt gucken wir uns mal an, wie sich diese Ackermann-Funktion
verhält.
Erster Gang ist direkt definiert, a1,j gleich 2 hoch j.
Das ist einfach nur nochmal die Definition.
Was ist der zweite Gang?
a2,1 ist ja nach dieser Definition, 2,1 ist a, das ist a1,2.
a1,2 ist einfach 2 hoch 2, ist 4.
Prima, kein supergroßer Wert, noch nicht viel passiert.
Was ist denn a2,2?
Da haben wir jetzt das erste Mal den allgemeinen Fall.
Das ist a1, a2,1.
a2,1 kennen wir schon, das ist 2 hoch 2.
Also, a1, das hier ist nach der Definition 2 hoch a2,1.
Und a2,1 ist 2 hoch 2, also 2 hoch 2 hoch 2.
a2,3 ist a1, a2,2.
a2,2 kennen wir schon, das ist 2 hoch 2 hoch 2.
a1 ist hier definiert a, 2 hoch 2 hoch 2 hoch 2.
Wie viel ist das?
2 hoch 2 ist 4, 2 hoch 4 ist 16, 2 hoch 16 ist 65.536.
Das reicht schon, um größer zu sein als log n, für alle denkbaren n.
Aber es ist noch eine überschaubare Zahl.
Machen wir mal weiter, a2,4 ist a1, a2,3.
Also 2 hoch a2,3, also 2 hoch 2 hoch 2 hoch 2 hoch 2.
Das ist jetzt schon ziemlich groß, das ist nämlich 2 hoch 65.536.
Und das ist jetzt schon eine Zahl, die größer ist als die Anzahl
Elementarteilchen im Universum.
Nach unserem Wissen.
Könnte jetzt sein, dass es irgendwie so viele Paralleluniversen gibt,
dass das dann noch mehr ist, aber das tangiert uns dann vermutlich
nicht, außer die Physiker finden da nochmal was.
Also das ist eine große Zahl, hier sind wir fertig.
a2,5 und so müssen wir uns nicht mehr anschauen.
Wie ist es mit dem nächsten Gang?
a3,1 ist nach der Definition hier a2,2.
Das kann ich nachschauen, das ist einfach 2 hoch 2 hoch 2.
Das ist also eine harmlose Zahl.
a3,2, ich habe hier nur einen Ticken hoch gemacht.
Naja, das ist nach Definition a2, a3,1.
Das ist a2,16.
A2,4 war schon astronomisch groß oder superastronomisch groß und jetzt
steht hier eine 16 statt einer 4.
Fragen Sie mich nicht, wie man sowas schreiben soll.
Das ist jetzt der Trick, das ist keine primitiv-rekursive Funktion,
das ist schon irgendwas absurd Großes.
Kann man nicht mehr hinschreiben.
Aber sicherlich größer als das da.
Jetzt machen wir mal weiter, a4,1.
Das ist nach der Definition a3,2.
Und das haben wir hier auch schon stehen, das ist dann auch schon so
eine große Zahl.
Geschweige denn a4,2 und so weiter.
Und das hier ist sicherlich alles größer als log n.
Also bleibt dieser Wert immer unter 4.
Ich glaube sogar kleiner gleich 3.
Also nochmal, wir haben hier diesen Satz.
mFind und nLink-Operationen brauchen im Wesentlichen Linearzeit.
Aber eben ein außergewohnt Mathematiker sagt, nein, nein, nein, nein,
das ist nicht Linearzeit, das wächst schneller.
Und dann kommt der Nächste und sagt, ja, aber ich kann den Logarithmus
davon erreichen als Laufzeit.
Ist dann auch egal.
Also wir haben hier ein Beispiel für eine recht simple Datenstruktur.
Das war wie viel Code?
Ich hatte gesagt, was war das hier?
Sowas wie 4 Zeilen, richtiger Code.
Plus eine macht 5.
Plus 2, 3, irgendwie 10 Zeiler.
Macht was Nützliches, ist super simpel.
Und die Analyse braucht aber 2, 3 Stunden, sie nur zu erklären.
Geschweige denn das auch selber so einen Beweis zu finden.
Das ist eine spannende Sache, dass man sowas zumindest mal gesehen
hat.
Also das hat ursprünglich Tarjan 75 gezeigt, und ich habe hier einen
Beweis von Seidel und Scharje zitiert, weil der noch einigermaßen
verständlich ist.
Diesen Beweis von Tarjan komme ich nicht wirklich mit zurecht.
Fragen dazu?
So, jetzt wenden wir das an für die Implementierung vom Kruskal
-Algorithmus.
Das ist jetzt eigentlich ziemlich simpel.
Also wir repräsentieren unsere Knotenmenge wieder durch die Zahlen 1
bis N.
Wir haben hier eine Datenstruktur TC, so eine Union-Find-Datenstruktur
mit N Elementen.
Jetzt haben wir wieder dieses Durchgehen der Kanten, und das dominiert
jetzt eigentlich die Laufzeit.
Dafür müssen wir alle Kanten sortieren, das braucht Zeit, M log M
zumindest im Vergleichsbasierten sortieren.
Aber der Rest ist dann simpel, weil wir haben hier Fals-Find-U
-ungleich -Find-V.
Das sind jetzt zwei M-Find-Operationen, die ich insgesamt durchführe.
Dann habe ich eine minimale Spannbaumkante gefunden, also Find-U
-ungleich -Find-V gibt ja die Repräsentanten.
Wenn die den gleichen Repräsentanten haben, heißt das, sie sind im
gleichen Block.
Und diese Blöcke repräsentieren diese Bäume.
Und damit habe ich das, was ich haben will.
Wenn die also in verschiedenen Blöcken sind, ist es eine MST-Kante,
ich gebe sie aus und ich rufe hier diese Union-Operation auf.
Oder genauer gesagt könnte ich hier auch einfach das Link aufrufen,
weil die Voraussetzungen für Ausführen von Link ja bereits abgetestet
wurden.
Laufzeit ist M log M durch das Sortieren.
Wenn ich ganzzahlige Gewichte hätte und Radixort oder sowas einsetzen
kann, dann sogar eben diese fast lineare Laufzeit, nämlich M mal
Inverse -Ackermann-Funktion von diesen komischen Parametern.
Hier sind so ein paar konzeptionelle Sachen, die man sich merken
sollte, also das sieht jetzt schön straightforward auf und man kann
ein paar Sachen übersehen.
Das eine ist die Graph-Repräsentation.
Wir haben beim Janik-Priem-Algorithmus gesagt, wir brauchen eigentlich
diese Adjacenz-RL-Repräsentation, weil wir mussten von den gegebenen
Knoten alle inzidenten Kanten finden.
Das ist hier nicht mehr nötig.
Ich kann irgendeine Kantenliste nehmen und ich muss die halt
sortieren.
Aber das vereinfacht die Datenstruktur deutlich und wir haben
Experimente gemacht.
In der Praxis ist es so, dass aus einer Kantenliste eine Adjacenz-RL
-Repräsentation eines Graphen zu machen, dauert im Allgemeinen länger,
als Kruskals-Algorithmus auszuführen und den MST direkt zu berechnen.
Das heißt, wenn Sie die Eingabe nur als Kantenliste haben, ist im
Allgemeinen Kruskal schneller als Janik-Priem.
Zumindest so, wie unsere Konversionsfunktion funktionierte.
Die kann man wahrscheinlich beschleunigen, aber dann muss man einiges
tun.
Dann eine kleine Subtilität ist, wir haben ja hier auf der
mathematischen, abstrakten Ebene betrachtet Kruskal ja so etwas wie
einen Wald.
Und ich gucke mir eine Kante an und frage immer, verbindet dieser Wald
zwei Bäume?
Und ich habe tatsächlich eine 1 zu 1-Beziehung zwischen den Bäumen im
minimalen spannenden Wald, der bereits betrachteten Kanten, und den
Blöcken in dieser Partition.
Und außerdem ist es noch so, dass jeder dieser Blöcke der Partition
repräsentiert wird, eigentlich durch einen anderen Baum, nämlich diese
Wurzelbäume.
Der Trick ist, das sind nicht die gleichen Bäume, also diese Bäume
sind nicht die gleichen wie hier.
Und das liegt unter anderem daran, dass ich auf den Dingern ja diese
Fadkompressionen durchführe.
Es ist jetzt denkbar, dass der Baum, den ich hier repräsentiere, eine
ganz lange Kette von Knoten ist.
Und ich will keinesfalls den direkt durch so eine lineare Liste
repräsentieren, weil dann die Feindoperationen immer ganz langsam
sind.
Die Fadkompression lässt das Zusammenschnurren zu einem Stern im
Idealfall.
Ich habe also hier eine kleine Subtilität, dass diese Bäume nicht das
gleiche sind wie diese Bäume, aber der Algorithmus ist trotzdem
korrekt, weil mich interessiert ja gar nicht, wo jetzt Fade lang gehen
in den Bäumen.
Ich muss nur wissen, die sind in der gleichen Zusammenhangskomponente
und diese Invariante wird durch die Fadkompression nicht verletzt.
Also das sollte man sich merken, dass diese Bäume eine andere Struktur
haben als diese Bäume.
Fragen dazu.
Nochmal ein Beispiel.
Das ist der gleiche Graph wie eben, jetzt gucken wir uns nur an, was
die Unified Datenstruktur damit macht.
Am Anfang war hier die leichteste, also ganz am Anfang haben wir hier
die Knoten 1 bis 4, die sind alle ihre eigenen Repräsentanten.
Und Repräsentanten sind hier immer schwarz und alle weiteren Knoten
hellblau.
Jetzt habe ich hier diese Kante eingeführt, also 2 und 4 werden
zusammengefügt und ich habe das jetzt so rum gemacht, die haben ja
beide Rang 0, das kann ich mir dann aussuchen, dass jetzt der Knoten 4
Rang 1 kriegt und der Knoten 2 hier drauf verweist.
Das ist doch eine etwas andere Eingabe.
Jetzt kommt diese Kante hier, Gewicht 3, die macht sowas ähnliches,
die 3 verweist auf die 1.
Das ist noch nicht so spannend.
Die nächste Operation ist hier die Kante mit Gewicht 4 wird eingefügt,
da verweist jetzt die 3 auf die 1 und ich füge die beiden, ach genau,
ich mache diese Kante rein, die beiden Repräsentanten sind ja 2 und 3.
Also das ist ein Repräsentant und das ist ein Repräsentant.
Also ich mache ein Find für die 3, der findet die 3.
Ich mache ein Find für die 4, der findet die 2.
Und jetzt sorgt das Link dafür, dass das 3 auf die...
Ich mache mal gerade das Funknetz aus.
Ich bin jetzt nicht ganz sicher, ob ich hier einen Fehler habe.
Jedenfalls müssen die jetzt aufeinander verweisen, ich habe ja den
Repräsentanten 1, der wird hier übernommen und den Repräsentanten 3,
der verweist halt auf die 1.
Aber nee, das stimmt nicht.
Ah Quatsch, der 3, 1 hatte ich vorher schon.
Und die 1 verweist jetzt auf die 4, so genau.
Also ich mache jetzt den hier zum Repräsentanten, für beide zusammen,
damit verweist die 3 auf die 1 und die 1 auf die 4.
Ja?
Und die 2 hatte vorher schon auf die 4 gezeigt.
Das ist jetzt die Situation, die ich habe.
Und hier haben wir jetzt bei jeder Link-Operation, hier wurde 0 auf 1,
0 auf 1 der Rang erhöht und hier habe ich jetzt zwei Komponenten vom
Rang 1 zusammengefügt.
Dadurch kriegt der Repräsentant von den beiden Dingern den Rang 2.
Okay.
Jetzt kommt diese Kante hier, mit Gewicht 6,
die ist innerhalb einer Komponente, wie finde ich das raus?
Naja, ich mache für 3 und für 2 einen Feind.
Für die 2 ist das unproblematisch, die verweist ja direkt auf das
Ding, das dann Repräsentant ist, das kann auch so bleiben.
Aber für die 3 war das ja so, dass ich hier einen Pfad der Länge 2
habe, von 3 auf 1 und von 1 auf 4.
Und da mache ich jetzt eine Pfadkompression, sodass anschließend die 3
direkt auf die 4 verweist.
Und danach habe ich im Prinzip hier einen Repräsentanten für alle 4
Knoten, die verweisen alle direkt da drauf, also das ist so ein
sternförmiger Baum, der da entsteht, und damit bin ich auch fertig,
was die Union Feind-Datenstruktur angeht.
Natürlich würde ich dann noch weiter mir die Kanten hier mit Gewicht 7
und 9 anschauen, aber die werden halt sofort feststellen, dass sie
alle den gleichen Repräsentanten an ihren engen Punkten haben, und
dass da nichts mehr passiert.
Fragen dazu?
So,
dann vergleichen wir mal Janik Prim und Kruskal.
Vor- und Nachteile.
Also was für Janik Prim stricht, ist, dass er asymptotisch gut ist für
beliebige Werte von M und N, sage ich mal.
Und vor allem, wenn der Graph recht dicht ist, also M groß gegen N
ist, dann dominieren eigentlich diese Decrease-Key-Operationen und die
kann ich einigermaßen schnell implementieren.
Bei Binary Heaps gilt das im Average Case, und wenn ich diese
Fibonacci Heaps einsetze, auch im schlechtesten Fall.
Im Fall von Kruskal ist das ein ganz guter Algorithmus, wenn ich eine
lineare Anzahl von Kanten habe, also lineare Anzahl von Knoten, also M
gleich O von N, weil dann unterscheidet sich O von M log N nicht von M
plus N log N.
Dann asymptotisch das Gleiche.
Und er hat den großen praktischen Vorteil, dass ich nur eine
Kantenliste brauche.
Und wenn ich einen sehr schnellen Sortierer habe, der zum Beispiel
auch die Schlüssel ausnutzt, ganzzahlige Schlüssel nutzt, vielleicht
einen parallelen Sortierer, kann ich das alles problemlos mit
benutzen, um diese teuerste Operation, das Sortieren der Kantenliste
schnell zu machen.
Das heißt, ich kann zurückgreifen auf Algorithmen und Bibliotheken,
die das bereits schnell machen, während Janik Priem, gut, da kann ich
Prioritätslisten verwenden, aber sonst ist das irgendwie inherent
sequenziell, kann ich nicht mit modernen Parallelrechnern draufhauen
und so weiter.
Und was wir uns dann tatsächlich in unserer Forschung angeguckt haben,
wenn ich ein paar Verfeinerungen vornehme von Kruskals Algorithmus,
dann kann ich auch für dichtere Graphen, also für großes M durch N,
nochmal deutlich bessere Laufzeiten erreichen.
Da werde ich gleich noch ein paar Zahlen zu zeigen.
Jetzt wieder Blick über den Tellerrand, es gibt eine ganze Menge
weiterer spannender Ergebnisse zu minimalen Spannbaumalgorithmen.
Noch ein Tscheche hat nämlich 1926, das ist noch früher als Herr
Janik, einen Algorithmus gefunden, der auch in O von M log N läuft,
also asymptotisch wie Kruskals Algorithmus.
Ich glaube, den hat dann ein Herrn Sollin in den 50er-Jahren neu
entdeckt.
Aber da auch niemand den Herrn Sollin kennt irgendwie, hat hier der
Name Berufka sich eher durchgesetzt.
Dann gibt es Algorithmen, die asymptotisch noch viel besser sind,
nämlich in O von M-Zeit laufen, randomisierte Algorithmen, und das ist
natürlich für die theoretische Informatik sehr spannend, dass man dann
mit nicht-trivialen Methoden hier tatsächlich lineare Arbeit
hinkriegt.
Und dann stellt sich auch noch heraus, dass dieser Algorithmus
durchaus parallelisierbar ist, sich auf Speicherhierarchien anpassen
lässt, was also eigentlich gerade auch für moderne Architektur ein
sehr positives Ergebnis ist.
Leider ist der Algorithmus relativ kompliziert und er enthält einen
Schritt, der schwer zu implementieren ist, wo auch große konstante
Faktoren da sind, sodass in der Praxis das eigentlich noch nicht
eingesetzt wird.
Aber das ist, finde ich, ein spannendes Forschungsthema, inwieweit man
dieses schöne theoretische Ergebnis auch in die Praxis noch umsetzen
kann.
Und damit sind dann Theoretiker auch noch nicht zufrieden, das ist ein
randomisierter Algorithmus, wie ist es mit deterministischen
Algorithmen?
Da hat dann Herr Chazelle einen noch komplizierteren Algorithmus
gefunden, der übrigens gar nichts direkt mit Union-Find
-Datenstrukturen zu tun hat, soviel ich weiß, aber wo dann
spannenderweise die Laufzeit schon wieder M mal inverse Ackermann
-Funktion von M endet.
Also das scheint irgendwas Inherentes zu sein, was in diesem MST
-Problem drin ist und auch in Grafen, also schon spannend, dass so
eine komplizierte Funktion dann plötzlich überall auftaucht.
Und dann ist das vor allem für die Theoretiker jetzt eine böse Lücke.
Also hier steht ein randomisierter Linearzeitalgorithmus und da ist
ein deterministischer Algorithmus, der länger braucht, asymptotisch
länger, auch wenn das in der Praxis uninteressant ist.
Ja, wie ist denn das jetzt?
Geht es noch besser?
Und dann haben Petty und Ramachandran nochmal was draufgelegt an
theoretischer Sophistication, die haben gesagt, ja, hier ist ein
Algorithmus, der ist deterministisch und der ist asymptotisch optimal.
Das heißt erstens, er ist mindestens so gut wie der Algorithmus von
Herrn Chazelle und zweitens, falls irgendwann mal irgendein
Theoretiker herkommt und sagt, hier ist ein deterministischer
Linearzeitalgorithmus, dann machen die es wie Hase und Igel und sagen,
wir sind schon da, weil die beweisen, dass jeder MST-Algorithmus nicht
schneller sein kann als das, was die machen.
Also das finde ich schon eine sehr spannende theoretische Aussage.
Ja.
Aber man würde natürlich gerne den Algorithmus auch angeben können.
Also Sie würden trotzdem, wenn Sie sowas jetzt rausfinden, einen
deterministischen Linearzeitalgorithmus, da noch durchaus Lorbeeren
verernten in der Theorie-Community.
Wir kümmern uns da um etwas praktischere Sachen.
Wir waren die ersten, die einen Algorithmus angeben konnten, der in
der Praxis auch funktioniert und auf so großen Datenmengen einsetzbar
ist, dass die Daten nur auf die Festplatte passen.
Und dann haben wir eine Verbesserung vom Kruskal-Algorithmus
angegeben, der noch etwas besser parallelisierbar ist und nicht alle
Kanten sortieren muss.
Also der gerade in diesem Fall, wo Kruskal bisher schlecht war für
relativ dichte Graphen, zu deutlichen Verbesserungen führt.
Die Ergebnisse sind leider nur im Average-Case, also für zufällige
Kantengewichte beliebige Graphen bewiesen, aber ich gehe mal davon
aus, dass der auch in der Praxis ganz gut funktionieren würde.
Hier sind mal ein paar Laufzeiten.
Also was wir gemacht haben in diesem Experiment ist, wir haben uns den
Graphen mit, nicht 2 hoch 2 hoch 2, sondern 2 hoch 22 Kanten
angeguckt, also sowas wie 4 Millionen Knoten, und zufälligen Kanten,
also zwischen zufälligen Knotenpaaren und einem zufälligen Gewicht.
Und dann verschiedene Dichten uns angeschaut.
Also hier ist das Verhältnis Anzahl Kanten durch Anzahl Knoten.
Wenn das Verhältnis 1 ist, ist das der Durchschnittsgrad 2 der Knoten
und steigt dann halt weiter an.
Und hier findet man jetzt halt die Algorithmen aus der Vorlesung
wieder, aber auch ein paar andere noch.
Also zunächst mal hier Jarnik Prim, da haben wir zwei Varianten mit
zwei verschiedenen Prioritätslisten untersucht.
Das sind die langsamsten Algorithmen, vor allem für dünne Graphen.
Dann hier der Kruskal-Algorithmus, das ist der hier.
Moment, da sind hier mehrere Kurven übereinander, das ist diese Kurve
hier.
Ja gut, und wenn man die beiden Algorithmen vergleicht, kriegt man
ungefähr das, was man erwartet hat.
Also für dünne Graphen ist der Kruskal besser, es ist eine
logarithmische Skala, also eine erhebliche Verbesserung.
Statt 200 Nanosekunden pro Kante braucht der Jarnik Prim halt
irgendwie 800-900 Nanosekunden, Faktor 5.
Aber die nähern sich danach irgendwie an und wenn ich noch dichtere
Graphen nehme, jetzt ist plötzlich ab Durchschnittsgrad 32 der Jarnik
Prim sogar schneller als der Kruskal.
Ja und jetzt sehen Sie, es gibt auch noch Kurven, die weiter unten
laufen.
Und naja, da wir das in der Publikation von uns geplottet haben, ist
es nicht so unverständlich, dass die am weitesten unten liegende Kurve
unser Algorithmus ist, den nennen wir Filter-Kruskal.
Da gibt es jetzt mehrere Varianten davon, gucken wir uns erstmal den
sequentiellen an, der ist, das sind diese Vierecke, also der ist am
Anfang genauso schnell wie Kruskal, aber setzt sich danach deutlich
ab.
Und jetzt geht es noch um Parallelisierung, also man kann den Kruskal
parallelisieren, indem man diese Phase mit der Knotensortiererei
parallelisiert, also wir haben da einfach eine existierende
Algorithmenbibliothek genommen, die auch bei uns in der Arbeitsgruppe
entstanden ist, aber eben auch State-of-the-Art-Sortierer liefert und
haben die sowohl sequentiell als auch parallel eingesetzt.
Und da sieht man dann, dass man hier, was ist das, der Kruskal 8, das
ist diese Kurve hier, nee, diese hier, die ist halt deutlich schneller
als der normale Kruskal und setzt sich sogar noch weiter ab für große
Eingaben von dem normalen Kruskal und von Janik Primers recht, also da
kriegt man eine gewisse Parallelisierung, aber unser Filter Kruskal 8
ist also dann parallelisiert auf 8 Chors, ist dann nochmal deutlich
schneller und wie gesagt, logarithmische Skala, wir haben hier sowas
wie 90, 80, 70, 60, 50, 40, 30, irgendwie 25 Nanosekunden pro Kante
hier unten, während die, die ungefähr gleich schlecht sind, sowas wie
200 Nanosekunden, also fast ist das eine Faktor-8-Beschleunigung.
Und eben nicht nur wegen der Parallelisierung, sondern auch weil der
sequentielle Algorithmus auch schon einen deutlichen Faktor besser
ist.
Und jetzt muss ich natürlich noch dazu sagen, glaube nur den Plots,
die du selbst gefälscht hast, natürlich habe ich hier nicht den Plot
genommen, wo wir am schlechtesten aussehen.
Also es ist da so, dass man Graphen konstruieren kann, wo unsere
Heuristik irgendwie ins Leere läuft und da sind wir dann schlechter
als die anderen Algorithmen, aber nicht viel schlechter, sage ich mal.
Oder ich glaube, da sind wir dann so gut wie der normale Kruskal oder
sowas.
Also die Verbesserungen laufen dann ins Leere, aber schlechter sind
wir auch nicht, irgendwie sowas.
Dann fassen wir mal zusammen, was wir in diesem Kapitel gelernt haben,
das ist eigentlich eine ganze Menge, obwohl es ein kleines Kapitel
war.
Also wir haben gesehen, wie Schnitt- und Kreiseigenschaften die Basis
für abstrakte Algorithmen sind und das ist auch jenseits des minimalen
Spannbaumproblems eine wichtige Algorithmenentwurfstechnik.
Suche nach abstrakten Eigenschaften, aus denen du erstmal high-level
die Algorithmen konstruierst und in einem zweiten Schritt überlege dir
Datenstrukturen, mit denen man das Ganze dann effizient macht.
Dann Beweise durch Austauschargumente, treten ganz oft in
kombinatorischen Algorithmen auf, dann aber eben auch eine effiziente
Implementierung braucht dann effiziente Datenstrukturen, das ist auch
ein Entwurfsprinzip.
Dann diese überraschende Entdeckung, dass der Dijkstra-Algorithmus und
der Janek-Priem-Algorithmus, obwohl sie extrem ähnlich sind, zwei
komplett verschiedene Probleme lösen und das ist nicht so ein Zufall,
weil das ist eigentlich nur ein Beispiel für ein ganz wichtiges
Algorithmenentwurfsprinzip, nämlich Greedy-Algorithmen.
Baue eine Lösung schrittweise auf und benutze eine Prioritätsliste, um
effizient immer den besten nächsten Schritt auszuwählen.
Dann haben wir ganz konkret kennengelernt die Union-Find
-Datenstruktur, Optimierungstechniken wie Pfadkompression Union-by
-Rank und wir haben eben ein Beispiel gesehen für einen einfachen
Algorithmus mit hochgradig nicht-trivialer Analyse.
Fragen zu minimalen Spannbäumen.
Dann kommen wir jetzt zum letzten Kapitel der Vorlesung, das wird ein
bisschen länger werden.
Optimierungsalgorithmen und vor allem generische Ansätze, also weitere
Algorithmenentwurfsmuster, die man immer wieder einsetzen kann,
allerdings jetzt ein bisschen spezialisiert auf Optimierungsprobleme.
Das sage ich noch mathematischer später, aber wir haben im Prinzip
eine Menge potenzieller Lösungen, die sehr groß sein können und wollen
darunter die beste auswählen oder wenn uns das nicht gelingt, eine
gute Lösung.
Da werden wir mehrere Techniken kennenlernen, erstmal Blackbox, wir
spezifizieren das Problem deklarativ in einem geeigneten Formalismus
und dann gibt es halt eine Algorithmenbibliothek, die das dann löst.
Wenn wir Glück haben.
Dann Gridi-Algorithmen, habe ich schon erklärt, was das ist.
Wir werden dann eine weitere Technik vorstellen, dynamische
Programmierung.
Das ist im Wesentlichen, dass ich Lösungen für komplexe Probleme
zusammensetze aus Lösungen für einfache Probleme.
Das ist sowas ähnliches wie Divide and Conquer, aber flexibler.
Bei Divide and Conquer lege ich von vornherein fest, aus welchen
Teilproblemen ich die Lösung zusammensetze.
Bei der dynamischen Programmierung probiere ich ganz viele
Kombinationsmöglichkeiten aus.
Dann gibt es ein noch aufwendigeres Verfahren, systematische Suche.
Also im Endeffekt probiere alle möglichen Lösungen aus, zähle die
systematisch auf und überlege dir vielleicht Regeln, wie man bestimmte
Sachen nicht explizit angucken muss.
Kann man sich vorstellen, systematische Suche kann oft zu
explodierenden Laufzeiten führen, deshalb gibt es Abschwächungen
davon, insbesondere lokale Suche, wo ich sage, ich habe eine aktuelle
Lösung und die wird nur ganz punktuell verändert und das mache ich so
lange, bis ich zu einer befriedigenden Lösung bekommen bin.
Im Allgemeinen kann man damit dann nicht mehr beweisbar optimale
Lösungen finden, aber oft ist es halt das Beste, was man kann oder gut
genug.
Und eine Verallgemeinerung davon sind evolutionäre Algorithmen, wo man
nicht eine einzelne Lösung hat, an der man rummanipuliert, sondern
eine ganze Population von Lösungen, an denen Mutationsoperatoren
Veränderungen vorführen und wo auch Rekombinationsoperatoren aus zwei
alten Lösungen eine neue produziert, die hoffentlich besser ist als
die alte.
Ich werde dabei weitgehend ein durchgehendes Beispielproblem
verwenden, das Rucksackproblem.
Das ist auch der Grund für dieses Bild hier, wo Sie sich vielleicht
gefragt haben, was ist das?
Da kann man jetzt alternativ das für dieses handlungsreisende Problem
nehmen, da rennt jemand mit der Kiepe durch die Gegend und verkauft
was und muss halt ganz viele Kunden besuchen, oder vielleicht ist das
ja auch ein Schmuggler, das ist so die Motivation, die ich glaube ich
im Buch stehen habe, der rennt halt jede Nacht über die Berghänge des
Schwarzwalds und schmuggelt Sachen von Baden nach Württemberg oder so,
aber es gibt natürlich, wir sind ja im Musterländle, eine
Schmugglergewerkschaft, die sagt, nein, nein, kein Schmuggler darf
mehr als 20 Kilogramm pro Nacht transportieren.
Und da wir ja alle ertragsorientiert sind, überlegt er sich, naja,
aber wie kann ich denn dann meinen Profit maximieren?
Ich habe da jetzt mehrere Gegenstände im Keller liegen, die haben ein
bestimmtes Gewicht und einen gewissen Profit, wenn ich sie nach
Württemberg trage, welche wähle ich denn jetzt aus, um unter diesen 20
Kilos zu bleiben?
Das können wir uns ein bisschen mathematischer überlegen, wir haben N
Gegenstände mit Gewicht Wi, nehmen jetzt an, das sind ganze Zahlen,
weil dann einige Algorithmen etwas leichter zu formulieren sind, und
Profit Pi.
Ich will jetzt eine Teilmenge x der Gegenstände auswählen, mit der
Einschränkung, dass die Summe der Gewichte, die ich auswähle, kleiner
gleich dem erlaubten Gesamtgewicht m ist, und unter Einhaltung dieses
Konstraints will ich meinen Profit maximieren.
Also die Summe der Profite der Gegenstände, die ich reinpacke, soll
maximiert werden.
Das ist ein klassisches kombinatorisches Optimierungsproblem, sodass
es auch eine ganze Reihe Anwendungen gibt, und dass die Eigenschaft
hat, dass es immer noch sehr simpel ist und dass es ganz viele
Lösungsansätze gibt, die je nach Instanz alle Sinn machen, und das ist
ein sehr schönes Beispiel für unsere Vorlesung.
Fragen zu der Problemspezifikation.
Also ein konkretes Beispiel wäre jetzt hier, ich habe hier maximal
Gewicht 5, und ich habe Gegenstände, die mir Profit 10, 15, 20
einbringen, und unterschiedliche, ja, jetzt kann ich mir überlegen,
und die haben eine gewisse Größe, also das hier ist Größe 1, also
Gewicht 1, Gewicht 2, Gewicht 3 und Gewicht 4, und was kann ich jetzt
zusammenpacken?
Ich könnte hier das 10er und das 15er nehmen, macht 25, dann habe ich
ein Gesamtgewicht von 3, aber dann passt sonst nichts mehr rein.
Eine Möglichkeit, oder ich nehme hier das 15er und das 20er, das sind
2 plus 3, dann ist es gerade voll, und dann habe ich 35, das ist ja
schon mal besser.
Das ist relativ klar, dass man das da irgendwie nicht nehmen will,
weil dann passt nur noch das 10er drauf, dann bin ich nur 30, und man
kann sich jetzt verschiedene Kombinationen überlegen.
Und ich glaube, hier war es tatsächlich so, die beiden zusammen ist
jetzt das Optimum.
So, ganz allgemein, was ist ein Optimierungsproblem?
Man kann das jetzt als Maximierungsproblem oder als
Minimierungsproblem formulieren, ich schreibe es jetzt als
Maximierungsproblem hin, weil das Rucksackproblem diese Eigenschaft
hat.
In der Literatur ist es eigentlich meistens umgekehrt, da ist die
kanonische Form ein Minimierungsproblem.
Aber man kann sich leicht überlegen, dass die beiden Formulierungen
äquivalent sind.
Jedenfalls, es wird eigentlich spezifiziert durch eine Lösungsmenge L
und eine Zielfunktion F.
Genauer gesagt, es gibt so eine Grundmenge U von überhaupt denkbaren
Lösungen, davon ist aber nur eine Teilmenge zulässig.
F ist eine partielle Funktion, die die zulässigen Lösungen auf einen
Zielfunktionswert abbilden und mich interessieren halt optimale
Lösungen x-Stern, die die Eigenschaft haben, dass F von x-Stern größer
gleich F von x für alle x in L ist.
Es gibt sehr viele Optimierungsprobleme, das Spannende ist, dass die
meisten davon eigentlich NP-hard sind, also was das ist, lernen Sie ja
erst nächstes Jahr, jedenfalls haben die halt die Eigenschaft, dass
wir keine Ahnung haben, wie man die schneller löst als in
exponentieller Zeit, zumindest im schlechtesten Fall.
Wir müssen aber trotzdem uns diesen Problemen stellen, weil die halt
in Anwendungen immer wieder auftreten, und müssen dann
Lösungstechniken dafür entwickeln.
Fragen zur Definition von Maximierungsproblemen.
Dann gucken wir uns als erstes mal Blackbox-Löser an.
Wir werden uns hier konzentrieren auf die vielleicht klassischsten
Blackbox -Löser, nämlich lineare Programmierung, beziehungsweise
ganzzahlige lineare Programmierung.
Was das ist, sage ich gleich.
Nur nochmal wieder Blick über den Tellerrand.
Was man im Moment auch viel sich anschaut, ist, man kodiert das
Problem als aussagenlogische Formel und überprüft dann, ob diese
Formel erfüllbar ist.
Weil es eben sehr gute Löser gibt für das Erfüllbarkeitsproblem bei
aussagenlogischen Formeln.
Und dann gibt es eigentlich eine Verallgemeinerung von beiden, das
sogenannte Constraint Programming.
Da kann man also eine relativ reiche Anzahl von Bedingungen angeben,
man definiert also Variablen, die bestimmte Werte annehmen können,
meistens ganzzahlig oder diskret, einige davon kontinuierlich oder in
einem bestimmten Intervall, formuliert dann Bedingungen, die also
nicht nur diese linearen Bedingungen sein müssen, sondern auch sowas
wie die folgende Menge von Variablen muss unterschiedliche Werte haben
oder ganz komplexe Dinge.
Und dann gibt es aber trotzdem sehr allgemeine Löser, die dann mit
einer Vielzahl von Constraint-Typen einem dann Lösungen berechnen.
Wenn man Glück hat, werden die dann auch fertig, wenn man Pech hat,
läuft man in eine kombinatorische Explosion.
So, dann erkläre ich mal, was lineare Programmierung bedeutet.
Zunächst mal muss man hier so eine Begriffsverwirrung auflösen.
Der Begriff stammt aus den 50er Jahren.
Man würde das heute eigentlich lineare Optimierung nennen und nicht
lineare Programmierung.
Aber es ist halt historisch gewachsen, deshalb wollte ich Sie mal
damit konfrontieren.
Also in den 50er Jahren haben Mathematiker sozusagen Programm- und
Optimierungsprobleme zum Teil austauschbar benutzt.
Da muss man darauf achten, dass das manchmal was anderes bedeutet als
der heutige Sprachgebrauch in der Informatik.
Wir haben also ein lineares Programm, wird spezifiziert durch n
Variablen und m Constraints, also Bedingungen.
Und dadurch definiere ich ein Maximierungsproblem mit einer linearen
Kostenfunktion.
Also ich habe hier dieses x, das ist ein n-dimensionaler Vektor, also
ein Element von r auf n.
Und die Zielfunktion ist immer ein Skalarprodukt eines Vektors, eines
n -dimensionalen Vektors mit meinem Variablenvektor.
Also ich kriege dann eine Linearkombination meiner Variablen ist meine
Zielfunktion.
Da kommt der Begriff linear her und nicht nur die Kostenfunktion ist
linear, auch die Bedingungen.
Wir haben nämlich alle die Form, so ein Constraintvektor ai,
Skalarprodukt mit x, ist kleiner gleich, größer gleich oder gleich zu
einem skalaren Wert bi.
Das kann man dann auch in Matrixform hinschreiben und so weiter.
Und damit ist dann die Menge der zulässigen Lösungen, die Menge aller
Vektoren aus r auf n, mit der Eigenschaft, dass die Variablen alle
nicht negativ sind.
So eine Standardannahme, wenn man negative Variablen haben will, muss
man das Problem so umformulieren, dass das wieder gilt, das kann man
aber immer erreichen.
Und es soll halt für alle Constraints gelten, dass sie gelten.
Also Constraint i ist die Bedingung ai mal Skalarprodukt x ist kleiner
gleich bi zum Beispiel.
Oder größer gleich gleich, da kann man verschiedene Varianten haben.
Dann bezeichnen wir die j-Komponent des Vektors ai als aij.
Fragen zur Definition eines linearen Programms.
Also wir sehen, das ist jetzt ein Spezialfall dieses allgemeinen
Optimierungsproblems, weil hier wird ja keineswegs verlangt, dass ich
da eine lineare Zielfunktion habe und auch diese zulässigen Lösungen
können irgendwas sein.
Und jetzt sind die zulässigen Lösungen halt durch so eine Menge
linearer Bedingungen definiert.
Gucken wir uns mal ein Beispiel an, mit nur zwei Variablen x und y.
Wir haben immer diese impliziten Constraints nicht negativ, also a
priori ist erstmal nur der erste Quadrant dieses Koordinatensystems
zulässig.
Und jetzt habe ich zusätzliche Einschränkungen, zum Beispiel y kleiner
gleich 6 heißt nur alles unterhalb dieser Gerade ist zulässig.
Oder die Bedingung x plus y kleiner gleich 8 heißt alles links von
dieser Gerade, also höchstens das links von dieser Gerade ist
zulässig.
Oder ich habe ein Constraint 2x minus y kleiner gleich 8, das heißt
alles links von dieser Gerade ist nur zulässig.
Und insgesamt ist dann die Menge der zulässigen Lösungen, die
Schnittmenge dieser Halbräume, also jede dieser linearen Constraints
einschließlich dieser Positivitäts-Constraints definieren ja eine
Halbebene und die Menge der zulässigen Lösungen ist dann gerade eine
Schnittmenge von Halbebenen und das ist dann im Zweidimensionalen
gerade ein konvexes Polygon, das ich habe.
Und da können Sie sich vorstellen, das ist eine große Vereinfachung
gegenüber einem allgemeinen zweidimensionalen Optimierungsproblem, wo
halt die Menge der zulässigen Lösungen irgendwas beliebig Zerklüftetes
sein kann.
Hier habe ich eine sehr einfache Sache, ein konvexes Polygon.
Und warum mir das hilft, können wir uns jetzt auch mal überlegen.
Die Zielfunktion, die ist hier glaube ich x plus 4y, definiert
eigentlich eine Richtung, mit der Eigenschaft, wenn ich in diese
Richtung gehe, kriege ich immer bessere Lösungen.
Also zum Beispiel hier, wenn ich eine Zielfunktion habe mit positiven
Koeffizienten, dann ist es klar, es gibt immer natürlich diese
zulässige Lösung, wenn es überhaupt eine, nee, das stimmt gar nicht.
Also angenommen, ich habe irgendeine zulässige Lösung, ich habe
gemerkt, zum Beispiel der Ursprung ist zulässig, jetzt habe ich aber
diese Zielfunktion, die sagt, du willst eigentlich x und y größer
machen, um deinen Zielfunktionswert zu erhöhen, dann geh mal in diese
Richtung, die zeigt dieser Pfeil an, geh möglichst weit in diese
Richtung, aber bleib in diesem Bereich.
Jetzt nehme ich einfach die Gerade, die senkrecht ist zu diesem Pfeil,
ich glaube, das ist hier diese gestrichelte Linie, und schiebe die so
weit wie möglich raus.
Und irgendwann ist die dann nur noch an einer Ecke von diesem Polygon,
und das ist dann meine optimale Lösung.
Also zumindest im Zweidimensionalen ist es extrem intuitiv, dass die
optimale Lösung eines linearen Programms immer die Ecke dieses
Polygons zulässiger Lösungen, eine Ecke in diesem Polygons zulässiger
Lösungen ist.
Und die Lösungsverfahren, die ich dann verwende, nutzen das auch aus.
Die suchen sich irgendeine zulässige Lösung am Rand und hangeln sich
dann den Rand entlang zur optimalen Lösung.
Das ist zum Beispiel das am breitesten eingesetzte Verfahren für
lineare Optimierung.
Da werden wir auch noch ein bisschen was zu sagen.
Und im Höherdimensionalen wird das natürlich ein bisschen
komplizierter.
Also im Dreidimensionalen ist das dann halt ein dreidimensionales
Polyeder oder sowas, im Hochdimensionalen nennt man das dann ein
Polytop.
Eine Schnittmenge von Halbräumen, die hat aber eben immer noch schöne
Eigenschaften, insbesondere diese Konvexität, die Tatsache, dass die
optimale Lösung immer an einer Ecke liegt und man sich dann den Rand
entlang hangeln kann.
Und das ist vielleicht auch der Grund, warum man versucht, möglichst
viele Optimierungsprobleme in eine Form zu bringen, dass sie zu einem
linearen Programm werden.
Oder zumindest Näherungslösungen mithilfe der linearen Programmierung
berechnet.
Fragen zu diesem Beispiel?
Ich mach mal ein Beispiel, zum Beispiel das kürzeste Wegeproblem, kann
man auch als lineares Programm formulieren?
Das ist nicht völlig trivial, wäre mir auch nicht als erstes
eingefallen, diese Formulierung.
Ich habe Variablen für jeden Knoten, die nenne ich dV.
Meine Zielfunktion ist, maximiere diese dV-Werte, also das dV ist im
Endeffekt der kürzeste Wegeabstand von S nach V.
Maximiere die Summe der dV unter Einhaltung der Bedingungen, dass dS
gleich 0 ist, S ist der Startknoten, und für jede Kante vW im Graphen
gilt dW kleiner gleich dV plus Kantengewicht.
Eine Möglichkeit, diese Formulierung zu verstehen, ist wieder dieses
Bindfadenmodell für kürzeste Wege.
Wir machen das jetzt ein bisschen anders, also wir nehmen dieses
Gespinst, heben das hoch, halten hier den Startknoten fest und ziehen
dann die Hand weg.
Und jetzt fallen alle Knoten runter.
Wir versuchen jeder für sich dieses Maximierungsproblem lokal zu
maximieren, nämlich maximale Entfernung vom Startknoten zu erzielen,
aber diese Constraints sorgen dafür, dass sie nicht beliebig weit
runterfallen können.
Man kann keinen Bindfaden überdehnen, sagen diese Constraints.
Und dann kann man sich überlegen, wenn das der Fall ist, alle hängen
an straffen Faden von Bindfäden, dass ich dann die größte zulässige
Entfernung erreicht habe und das ist gerade die kürzeste
Wegeentfernung.
Das ist kein formaler Beweis, aber es gibt so ein bisschen Intuition,
was da passiert.
Fragen zu dem Beispiel?
Jetzt möchte ich mir noch eine konkretere Anwendung anschauen, die
tatsächlich in der gerade auch frühen Literatur zu linearer
Programmierung eine der Pilotanwendungen war und die ich besonders
plastisch finde, um zu verstehen, was da vorgeht.
Nehmen wir mal an, Sie sind ein Großbauer und Sie haben da 1000 Kühe
im Stall stehen und jetzt müssen Sie die füttern und das geht
natürlich heutzutage nach Profitmaximierung, möglichst billig.
Aber wenn Sie dann hergehen und nur Sojabohnen verfüttern oder sowas,
dann ist das vielleicht keine ausgewogene Ernährung, die Tiere wären
krank und das ist keine gute Idee.
Deshalb versuchen Sie das jetzt mathematisch zu modellieren.
Es gibt auf dem Markt N Futtersorten, die für Sie überhaupt in Frage
kommen.
Sie gehen zu Ihrem örtlichen Landhandel und fragen, was haben Sie denn
überhaupt für Kuhfutter?
Oder Sie gehen zu den Nachbarn, was könnt ihr mir verkaufen an Heu und
so weiter.
Und jetzt schreiben Sie auf, für jede Sorte, die es gibt, wie viel
Euro pro Kilogramm kostet die?
Das sagt dann schon die Zielfunktion.
Also die Variable sagt, wie viel kaufe ich von dieser Futtersorte?
Das ist das XI und dann ist die Summe XI mal CI und Sie minimieren in
dem Fall.
Also ein Minimierungsproblem, Ihre Gesamtkosten für Fütter, aber es
gibt Anforderungen an die Ernährung.
Sie müssen mindestens so und so viele Kalorien zuführen, so und so
viele Proteine, so und so viel Vitamin C, viele andere Dinge.
Und jetzt müssen Sie noch eine Erfahrung bringen in irgendwelchen
Tabellen, wo drin steht, aha, die Sorte I enthält AJI-Prozent des
täglichen Bedarfs pro Kilogramm bezüglich der Anforderung J.
Das definiert Ihnen Ihre Constraints.
So und jetzt, also diese ganzen Zahlen müssen Sie irgendwie in
Erfahrung bringen, schreiben Sie dieses lineare Optimierungsproblem
hin, in einem Format, das ein entsprechendes Werkzeug verlangt,
drücken auf den Knopf und er gibt Ihnen eine optimale Lösung.
Ist ja schon mal schön.
Gucken wir uns mal an, was kann man damit noch machen, Sie können dann
zum Beispiel obere Schranken einführen, für bestimmte Werte, zum
Beispiel Radioaktivität, Kuhhirngehalt, Ihrer Nahrung, solche
unschönen Dinge.
Beschränkte Reserven, also nehmen Sie an, Sie haben eigenes Heu, okay,
dann ist der Preis null, oder der Preis ist dann das, was Sie kriegen
würden, wenn Sie es verkaufen, was vielleicht ziemlich wenig ist, aber
Sie können natürlich nicht beliebig viel eigenes Heu verwenden, das
heißt, da gibt es dann einen zusätzlichen Constraint, die Anzahl
Kilogramms eigenes Heu ist kleiner gleich 375.
Vielleicht ist es auch so, dass die Kostenfunktionen nicht gleich
sind, also wenn zum Beispiel so ist, Sie wollen Heu einkaufen, dann
können Sie das von Ihrem Nachbarn vielleicht billiger kriegen, als von
dem Bauern im Nachbardorf und das ist billiger, als es aus Australien
zu importieren, also es gibt wachsende Transportkosten.
Aber man kann auch nicht alles mit linearer Programmierung ausdrücken,
wenn Sie zum Beispiel einen bestimmten Preis erst kriegen, wenn Sie
mindestens eine Tonne abnehmen, aber Sie haben leider nur einen Huhn
im Stall, dann lohnt sich das für Sie nicht.
Die meisten nicht-linearen Kostenfunktionen kriegen Sie nicht
abgebildet, wie gesagt, wenn Sie wenig Tiere haben, dann macht es
vielleicht auch einen Unterschied, ob Sie eine Kiste kaufen oder zwei
Kisten im Landhandel, aber die werden Ihnen vielleicht nicht 1,34
Kisten verkaufen wollen.
Da müssen Sie dann irgendwie runden.
Und was mir ganz wichtig ist, Garbage in, Garbage out.
Wenn Sie zum Beispiel anfangen, solche Constraints da reinzuschreiben,
dann passiert das, was zum Beispiel nach Zernobyl hier in Deutschland
passiert ist, da gab es dann Grenzwerte für Radioaktivität und dann
waren ganz schlaue Leute, die haben dieses super-billige Milchpulver
aus der Ukraine beschafft und das mit nicht ganz so billigem
Milchpulver aus Deutschland vermischt, solange bis die
Radioaktivitätswerte genau erfüllt waren.
Aber ob man das haben will, muss man sich dann schon noch überlegen.
Also die soziale und sonstige Verantwortung hängt in dieser
Formulierung des linearen Programms.
Der Optimierer löst nur noch das, was Sie da in Zahlen eingeben.
Aber wenn Sie da Müll reinformulieren, kriegen Sie auch Müll raus.
Das muss man sich öfter mal bewusst machen.
Das gilt heutzutage seltener bei Q-Hirn zum Glück, aber bei
Finanzprodukten.
Die Banken machen da ganz tolle Optimierungen, aber mit Modellen, die
alle nicht stimmen.
Und was rauskommt, sind Banken-Crashs.
Also das machen die vielleicht nicht unbedingt mit linearer
Programmierung, aber eben mit komplexen mathematischen Optimierern,
die sie nicht wirklich verstehen.
Und das ist eine Riesengefahr, der man sich immer bewusst sein sollte.
So, zurück zu konkreten Algorithmen.
Einer der Gründe, wieso man lineare Programme so gerne verwendet, ist,
dass man sie schnell lösen kann.
Insbesondere gibt es ein gefeiertes Ergebnis, das zeigt, dass man das
immer in polynomieller Zeit kann.
Die Kompliziertheit dabei ist jetzt wieder, was bedeutet das in der
Praxis.
Die besten Ergebnisse, die man im Moment kennt, brauchen im Worst-Case
so etwas wie Maximum von Anzahl Constraints und Variablen hoch 7
Halbe.
Also das wächst.
So etwas wie mit der dreieinhalbten Potenz der Eingabegröße.
Im schlimmsten Fall.
Andererseits ist es so, in der Praxis werden heute lineare Programme
gebaut, sagen einem die Werkzeughersteller, wenn du es in den Speicher
kriegst, kriegen wir es auch gelöst.
Das kann aber nicht sein mit einer Laufzeit, die mehr als kubisch ist.
Also in der Praxis sind lineare Programmierwerkzeuge viel schneller
als diese schlechtesten Fälle.
Was dazukommt ist, normalerweise verwendet man gar nicht diese
Polynomialzeit -Algorithmen, sondern welche, die im schlimmsten Fall
exponentielle Laufzeit haben, das in der Praxis aber nicht haben.
Das heißt, da gibt es noch sehr viel Forschungsbedarf zu verstehen,
wann sind lineare Programme schwierig, welche Algorithmen verwende ich
wann, wann treten schlechteste Fälle auf, wie kann ich die umfahren
und so.
Dazu kommt jetzt eine wirklich robuste Implementierung, da sind auch
so numerische Feinheiten zum Beispiel dabei, die außerdem noch
effizient ist, ist extrem aufwendig.
Also ich könnte Ihnen jetzt eine Programmieraufgabe stellen, sagen wir
mal für dieses Softwarepraktikum, dann könnte so eine Arbeitsgruppe
von vier Leuten wahrscheinlich einen linearen Programmierer schreiben,
der ich sag mal meistens funktioniert, aber wenn Sie dem dann große
Instanzen geben, wären die kommerziellen Systeme wahrscheinlich
tausendmal schneller.
Und die funktionieren immer, oder fast immer.
Während Ihre manchmal merkwürdige Ergebnisse produzieren würden.
Das heißt, das ist tatsächlich ein Beispiel, wo man normalerweise die
Finger von eigenen Implementierungen lässt und da auf existierende
Pakete setzt, da gibt es sehr gute kommerzielle Systeme, freie
Systeme, auch die gar nicht schlecht sind und Sachen, die zum Beispiel
für kommerziellen Einsatz umsonst sind, gibt es sowieso ziemlich
viele.
So, das ist eine gute Stelle zum aufhören, beim nächsten Mal werden
wir dann ganzzahlige lineare Programmierungen machen, das Ganze aus
Rucksackproblemen anwenden und weitere Optimierungstechniken kennenlernen.