Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Im polynomialen Laufzeit kommt, indem man geschickt über gewisse Größen skaliert und am Anfang nur die Großen schiebt und dann die Kleineren.

Und auf die Art und Weise, wenn man das geschickt macht mit jeweils Halbierung dieser Größen, dann kriegt man am Schluss den Logarithmus dieser Größen rein.

Und damit haben wir aus unserem b n hoch 3 ein Log b m gemacht. Das m, da muss man ein bisschen beigeben, weil man von einer Skalierungsphase auf die nächste eben durchaus da gewisse Kantengewichte oder reduzierte Bogengewichte sozusagen bereinigen musste.

Und das hat uns einen zusätzlichen Aufwand gekostet, warum das aus einem n ein m gemacht hat. Und damit sind wir bei Log b mal m mal n² gelandet am Ende.

Aber immerhin haben wir damit auf jeden Fall mit dem netten Trick polynomialer Laufzeit bekommen. Dieser Trick, der funktioniert noch bei vielen anderen Problemen auch.

Das haben wir hier sozusagen exemplarisch an dieser Stelle einmal gemacht. Und dann haben wir gesagt, da haben wir ein bisschen unsere heile Welt verlassen.

Und sagen, die Probleme, für die man polynomiale Algorithmen kennt, für die man Zertifikate hat, für die man beweisbare Optimallösungen findet.

Wir werden später insbesondere in der Diskretenoptimierung dann uns nahezu nur mit Problemen beschäftigen, wo solche Zertifikate und polynomialen Algorithmen nicht bekannt sind.

Und man sich auf andere Methoden zurückziehen muss. Und eine sozusagen, eine gängige Methode, die halt in der Praxis sehr, sehr üblich ist, sind Heuristiken.

Die versuchen eine schnelle Laufzeit zu haben, können das aber nicht immer garantieren. Und versuchen eine möglichst gute Lösung zu haben,

können aber auch nicht garantieren, dass sie immer die exakte oder beweisbare Optimallösung haben.

Also wir vernachlässigen sozusagen an zwei Stellen unsere angestrebten Ziele. Einmal schnelle Laufzeit, sprich polynomiale Laufzeit und beweisbare Optimalität.

Und Heuristiken vernachlässigen in gewisser Weise beide Aspekte, versuchen aber eine Balance zwischen Laufzeit und Qualität der Lösung zu finden,

wobei sie Qualität am Schluss nie wirklich abschätzen können. Und da haben wir einen Klassiker in dem Zusammenhang gestern angefangen zu analysieren,

und das ist der Greedy Algorithmus. Und der Greedy Algorithmus ist, ich sag mal, für einfach Prioritätenoptimierung.

Wir suchen uns eine Gewichtung der Elemente, die wir sozusagen, die zur Auswahl stehen, und wir sortieren dann gemäss dieser Gewichtung

und packen Drei nach Reihen, solange es eine zulässige Lösung bleibt. Das Ganze haben wir aufgesetzt auf das sogenannte Unabhängigkeitssystem,

die definiert waren als eine Teilmenge, eine Potenzmenge, eine endlichen Grundmenge mit der Eigenschaft, dass wenn ich eine zulässige Lösung darin habe,

auch jede Teilmenge davon wieder zulässig ist. Und Beispiele solcher Unabhängigkeitssysteme waren eben aus der linearen Algebra lineare Unabhängigkeit,

das Beispiel waren Wälder in Grafen oder aber auch zulässige Lösungen vom Rucksackproblem. Und da haben wir uns die zwei Grundalgorithmen angeguckt,

der Greedy Max und der Greedy Min. Den Greedy Min haben wir schon eins zu eins so gesehen bei minimal aufspannenden Bäumen, da hat er funktioniert.

Dann haben wir versucht diesen Greedy Max anzuwenden aufs Rucksackproblem und da sind wir gestern stehen geblieben, da haben wir jeweils zwei Beispiele gefunden,

wo egal wie wir das machen, egal welche Sortierung wir wählen, der immer auf die Nase fällt und Lösungen liefert, die beliebig schlecht werden können.

Und heute wollen wir eben analysieren woran das liegt und sogar charakterisieren, wann der Greedy Algorithmus tatsächlich Optimallösungen findet.

Und im zweiten Teil heute wollen wir uns dann mit lokalen Suchverfahren beschäftigen und da die Klassiker uns anschauen, die es gibt,

die, ich nenne mal einfach die Schlagworte Taboo Search, Simulator aniligenetischer Algorithmen, das sind so die Klassiker im heuristischen Bereich,

die da gerne verwendet werden und sich großer Beliebtheit erfreuen in der Praxis sozusagen.

Gibt es bis dahin noch Fragen zu gestern? Gut, dann schauen wir uns mal an.

Also wir hatten ja gestern uns diesen Greedy Max angeguckt für das Rucksackproblem, wir hatten zwei Beispiele.

Wir haben dann nach einer Gewichtung gesucht, sodass der Greedy nach Möglichkeiten eine Optimallösung findet.

Wir haben einmal die Originalzielfunktion genommen, haben ein Beispiel gefunden, wo ein Faktor N daneben liegen kann, wenn ich N Variablen habe.

Und wir haben dann gesagt, naja, einfach nach der Zielfunktion gucken ist doof, wir machen den sogenannten Gewichtstichtenkriti,

wir schauen, wie viel gewinnt man denn pro Einheit sozusagen, also wir schauen dann den Quotienten Ci durch Ai an und sortieren den gemäß dieser Gewichtung

und auch dann findet sich leicht ein Beispiel, wo man beliebig schlecht werden kann, je nachdem, was man für einen Koeffizienten nimmt.

So, und die Frage, woran liegt das, und es gibt eine interessante Eigenschaft, woran das liegt und das hat mit diesen Basen zu tun.

Wir hatten ja noch mal gesagt, eine Basis in einem Unabhängigkeitssystem ist eine bezüglich Inklusion maximal unabhängige Menge.

So wie in der Linearen Algebra eine Basis, eine maximale Menge an linear unabhängigen Vektoren in der Linearen Algebra, das ist R hoch N, sind es N Vektoren.

Da ist egal, welche Basis es wählt, die haben immer N Vektoren. Wie ist das bei aufspannenden Bäumen?

Bei aufspannenden Bäumen, nehmen wir an, wir haben zusammenhängen Graph, wie viel Kanten enthält ein aufspannender Baum?

Immer N minus 1, also das heißt die maximal unabhängigen Mengen, also Basen,

machen wir es mal so, Kardinalität von Basen.

Also da hat man als erstes Beispiel lineare Unabhängigkeit in der Linearen Algebra, und da hat man Basen, jede Basis, wenn man so im R hoch N hat, Kardinalität N.

Dann bei Wäldern in Graphen, nehmen wir mal an zusammenhängend, das soll zusammenhängend sein, jede Basis hat Kardinalität N minus 1.

So, und wie ist beim Rucksack?

Wie ist beim Rucksack Problem? Schauen wir uns mal ein Beispiel an.

Wenn ich irgendwie maximiere x1, x2, x3, mach mal 3x1 plus 3x2 plus 5x3 kleiner gleich 6, was wären da die Basen von diesem Beispiel?

Also was sind die maximal unabhängigen Mengen?

Ich kann die 1 nehmen und die 2. Wenn ich die 2 nehme, die passen rein, 3 plus 3 macht die 6, passt rein.

Der 1 selber ist keine Basis, vorhin kann ich ja erweitern, gehe ich noch einen mit rein. Wir haben ja gesagt beim Rucksack Problem, die Menge aller unabhängigen Mengen sind zulässige Lösungen.