Disclaimer: Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an grafdan@ethz.ch.
Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich hier.
Nehmen Sie an, Sie haben zu Ostern Schokolade in diversen Formen und Grössen erhalten. Nun möchten Sie die Schokolade möglichst gleichmässig mit jemandem teilen.
Formal: Gegeben sind verschiedene Zahlen. Wir möchten die Zahlen in zwei Mengen aufteilen, sodass die Summen der Elemente in beiden Menge gleich gross sind.
17 145 280 92 ...
Gegeben sind
Gesucht:
Es scheint schwierig, die Gleichung zu gebrauchen, um wie letztes mal hier induktiv vorzugehen. Wir können das ganze aber umformulieren, denn wir wissen ja, wie gross die beiden Summen je sein sollten: Je genau die Hälfte. Wir setzen also und suchen stattdessen nach einer Teilmenge der Zahlen, welche summiert genau ergibt. Dies nennt man auch das Subset-Sum-Problem.
Gegeben sind die Elemente mit , sowie eine vorgegebene Summe .
Frage: s.t. ?
Wir könnten naiverweise alle möglichen Teilmengen ausprobieren. Dann müssten wir aber mögliche Teilmengen berücksichtigen.
a_i= 5 3 2 7, z = 11
0 0 0 0 -> 0
0 0 0 1 -> 7
0 0 1 0 -> 2
0 0 1 1 -> 9
...
Das -te Bit einer Zeile sagt aus, ob die -te Zahl Teil der Menge ist oder nicht.
Neue Idee: Wir merken uns welche Summen wir mit den ersten Zahlen erreichen können. Die Summe können wir beispielsweise mit jeder Eingabe erreichen; wir wählen einfach keine der Zahlen.
0 1 2 3 4 5 6 7 8 9 10 11=z
keine Zahlen Y N N N N N N N N N N N
a_1 = 5 Y N N N N Y N N N N N N
a_2 = 3 Y N N Y N Y N N Y N N N
Wir definiern falls die Summe mit den ersten Zahlen erreichbar ist. Wenn mit den ersten Zahlen erreichbar sind, haben wir entweder die -te Zahl nicht genommen und können bereits mit den ersten Zahlen erreichen, oder wir haben die -te Zahl genommen und können mit den ersten Zahlen die Summe erreichen:
Das einfach rekursiv auszurechnen hat Laufzeit
Wir können jedoch eine DP-Tabelle err der Grösse verwenden, in der der Eintrag err[i,z] der obigen Definition von entspricht.
Sobald wir die Tabelle berechnet haben, wissen wir ob die Summe erreichbar ist oder nicht, indem wir den Eintrag betrachten. Wollen wir auch eine Menge finden, die diese Summe ergibt, so müssen wir von diesem Eintrag aus zurückverfolgen, welchen vorherigen Eintrag wir verwendet haben um den aktuellen Eintrag auf True zu setzen.
Achtung: kann sehr gross sein: In linearer Eingabelänge können wir eine exponentiell grosse Zahl darstellen. Wir können also mit einer relativ kleinen Eingabe ein riesiges Tableau erzeugen. Daher ist unser Algorithmus pseudopolynomiell, was soviel heisst wie: Der Algorithmus läuft polynomiell in den Zahlen, welche in der Eingabe repräsentiert werden. Falls alle Zahlen in der Eingabe also klein sind (polynomiell in ), so läuft dieses dynamische Programm polynomiell schnell in der Eingabelänge, aber im Allgemeinen nicht.
Andere Formulierung: Wenn die Eingabezahlen nicht binär, sondern unär (quasi als Strichlisten) dargestellt werden, dann läuft der Algorithmus linear in der Eingabelänge. Aber die Eingabelänge quasi künstlich zu verlängern ist ja ein wenig geschummelt.
Jetzt haben wir zwei Algorithmen: die Laufzeit des einen ist exponentiell in und die des anderen ist pseudopolynomiell. Können wir diese beiden Algorithmen irgendwie kombinieren? Hier hat der Kollege Schöning aus Ulm einen guten Trick gefunden:
Gegeben sei ein Array mit Zahlen. Um zu wissen, ob zwei dieser Zahlen zusammen eine Zielzahl ergeben, könnten wir alle Paare von Zahlen anschauen. Geht es schneller?
Wir können das Array sortieren und dann die grösste und kleinste Zahl betrachten. Falls die Summe dieser beiden Zahlen zu gross ist, müssen wir die grösste Zahl nie wieder betrachten, da jede andere Zahl mit dieser Zahl zusammen eine grössere Summe ergibt. Analog müssen wir die kleinste Zahl nicht betrachten, wenn die Summe der kleinsten und der grössten Zahl kleiner als die Zielsumme ist. Mit dieser Idee können wir nach dem Sortieren in linearer Zeit berechnen, ob die Zielsumme mit zwei Zahlen erreichbar ist. Beispiel:
1 2 17 26 56 111
^ ^
| |
Die Summe ist zu gross, weshalb wir die zweitgrösste Zahl betrachten.
1 2 17 26 56 111
^ ^
| |
Die Summe dieser Zahl und der kleinsten Zahl ist wieder zu gross; wir betrachten also die nächstkleinere Zahl, usw.
Auf diese Weise verschieben wir den rechten Zeiger nach links oder den linken Zeiger nach rechts bis wir die Zielsumme erreicht haben oder sich die beiden Zeiger treffen.
Wie können wir diese Beobachtung nun für unser Problem nutzen? Wir teilen die gegebenen Zahlen in zwei Hälften auf und bilden für jede Hälfte alle möglichen Teilsummen (höchstens viele):
Beispiel: Wir teilen die Zahlen 5 3 2 7 auf in 5 3 und 2 7.
5 3 2 7
-------- --------
0 0 -> 0 0 0 -> 0
0 1 -> 3 0 1 -> 7
1 0 -> 5 1 0 -> 2
1 1 -> 8 1 1 -> 9 (Alle Teilmengen)
Nun sortieren wir auf beiden Seiten die Folge der berechneten Teilsummen:
(alle Summen die mit 3 und 5 erreichbar sind) und (diejenigen, die mit 2 und 7 erreichbar sind).
Wir gehen in einer Folge mit einem Zeiger von links nach rechts und gleichzeitig in der anderen mit einem zweiten Zeiger von rechts nach links durch. Falls die aktuelle Summe zu gross ist, verschieben wir wie vorher den zweiten Zeiger nach links, ist sie zu klein den ersten Zeiger nach rechts.
0 3 5 8 0 2 7 9
^ ^
| |
Der Algorithmus arbeitet also wie folgt:
Insgesamt haben wir also eine Laufzeit von .
Ist das jetzt viel besser als ? Ja! Bei exponentiellen Algorithmen ist auch die kleinste Verbesserung an der Basis wichtig. Selbst ist exponentiell viel schneller als .[1]
Diese Idee hat also die exponentielle Basis deutlich reduziert, aber wenn alle Zahlen in der Eingabe klein sind, dann ist unser dynamisches Programm (Laufzeit O()) unter Umständen deutlich schneller.
Wir betrachten nun ein weiteres bekanntes Problem: Angenommen Sie brechen in ein Juweliergeschäft ein und müssen nun ihren Rucksack möglichst optimal mit teuren Schmuckstücken füllen. Wie können Sie sich "schnell" entscheiden?
Formal: Sie haben Gegenstände. Jeder Gegenstand hat ein gewisses Gewicht und einen gewissen Wert. Wir möchten einen Rucksack packen und die Gegenstände möglichst so wählen, dass der Gesamtwert der gepackten Gegenstände möglichst gross ist. Der Rucksack kann allerdings nur ein gewisses Gesamtgewicht fassen, bevor er bricht.
Gegeben: und für , also Wert (value) und Gewicht (weight) der Gegenstände, sowie ein Gesamtgewicht , das in den Rucksack passt.
Wir wollen nun die Gegenstände, die wir in den Rucksack nehmen, so wählen, dass wir möglichst viel Wert haben und dass wir Gesamtgewicht, das in den Rucksack passt, nicht überschreiten.
Gesucht: , so dass und maximal.
Beispiel:
v 5 7 8 (values)
w 3 2 4 (weights)
Erste Idee: Greedy / gierig:
Wir sortieren die Gegenstände absteigend nach und nehmen dann fortlaufend den nächsten Gegenstand, solange dieser noch in den Rucksack passt.
Ist das gut? Gar optimal? Oder mindestens eine gute Approximation?
Es kann sehr schlecht werden. Angenommen es gibt zwei Gegenstände:
mit sehr klein
oder konkreter:
,
,
mit
Dann nehmen wir den ersten Gegenstand, weil er die höhere Wertdichte hat als der zweite Gegenstand, und haben dann für den zweiten. Damit sind wir beliebig schlechter als die optimale Lösung, die nur den zweiten Gegenstand nimmt.
Nun wollen wir ähnlich wie bei Subset-Sum vorhin einen DP-Ansatz verfolgen: Wir nehmen an, dass wir uns eine kleinere Gewichtsgrenze vorgeben und dann schauen wollen ob wir mit den ersten Gegenständen einen Mindestwert erreichen können. Also:
wenn mit den ersten Gegenständen ein Gesamtgewicht nicht überschreiten und einen Gesamtwert mindestens erreichen können, und falls nicht.
Das ist nur eine von vielen möglichen Formulierungen, aber eine, die sehr nach Induktion riecht. Denn nun gilt wiederum, dass wahr ist, wenn wir und bereits mit den ersten Gegenständen erreichen können oder wenn wir mit den ersten Gegenständen den Wert und erreichen können. Es gilt also
Initialisierung: Wenn die Gewichtsschranke negativ ist, dann ist die Antwort "Nein".
Wenn die Gewichtsschranke nicht negativ ist und der Mindestwert nicht positiv, dann ist die Antwort "Ja". Sonst bestimmen wir die Antwort mit einem Tableau.
Aufruf: Um zu prüfen, ob das gesamte Juweliergeschäft in den Rucksack passt, betrachten wir . Doch das wird im Normalfall nicht möglich sein. Wir müssen daher für alle betrachten, um den maximalen Wert zu finden, den wir ergattern können.
Dies ergibt ein dreidimensionales Tableau der Grösse .
Die Berechnung jedes Eintrags kostet jeweils konstante Zeit. Als totale Laufzeit erhalten wir also Tableau-Grösse Eintragsberechnungsdauer . Ist dies bereits eine gute Laufzeit oder geht es noch schneller?
Überlegen wir uns, wo im Tableau die Antwort zu finden ist: Wir müssen für und den maximalen Mindestwert suchen, für den die Antwort Ja ist. Für fixierte und haben wir also ein derartiges Muster von Einträgen (aufsteigend nach Mindestwert v):
Y Y Y Y Y Y Y Y N N N N N
Wir finden das grösste Y also mit binärer Suche und können es uns merken.
Wenn wir aber schon wissen, dass die Einträge für fixe und die Form haben, dann können wir das Tableau auch einfach so abändern, dass wir uns nur gerade merken, wo die Y aufhören und die N beginnen. Wir merken uns also den maximalen erreichbaren Mindestwert.
Unser neues Tableau hat also die Grösse und ein Eintrag enthält den maximalen Wert, den man mit den ersten Gegenständen und einer Gewichtsschranke erreichen kann. Ein Eintrag wird wie folgt berechnet:
Somit erhalten wir ein neues Tableau der Grösse , und die Berechnung jedes Eintrages erfolgt weiterhin aus nur zwei vorhergehenden Einträgen. Die Gesamtlaufzeit des neuen dynamischen Programs ist also .
Das ist wiederum eine pseudopolynomielle Lösung. Bei sehr grossem kann es also immer noch sehr lange dauern, die Lösung zu berechnen. Deshalb wollen wir nun noch nach Lösungen suchen, die schnell laufen und Lösungen finden, die zwar vielleicht nicht optimal sind, aber immerhin sehr sehr nahe am Optimum sind.
Wir wollen nun also versuchen, eine Näherung zu berechnen. Wir geben uns damit zufrieden, eine sehr gute, aber nicht optimale, Lösung zu finden. Wir möchten eine Garantie haben, dass die Lösung nicht wesentlich schlechter ist als die optimale Lösung. Das Ziel ist also eine Lösung , sodass
wobei die optimale Lösung bezeichnet. Wir möchten also, dass unsere Lösung garantiert nur um ein von der optimalen Lösung abweicht.
Wir versuchen dies wiederum mit einem Tableau, in welchem wir das erreichbare minimale Gewicht für einen bestimmten Wert mit den Gegenständen 1 bis notieren.
0 1 ... n*Vmax
0
1
2
.
.
.
n
Wir haben also in Zeile die ersten Gegenstände zur Verfügung und in Spalte einen bestimmten möglichen Wert. Ein Eintrag sagt, welche Gewichtsgrenze nötig ist, damit man mit den ersten Gegenständen den Wert erreichen kann.
Die Tabellengrösse ist und die Berechnung eines Eintrags erfolgt in konstanter Zeit. Insgesamt haben wir also eine Laufzeit von
Was passiert nun, wenn wir bei jedem Gegenständen die letzten drei Stellen des Wertes streichen und hoffen dass dabei nicht viel kaputt geht?
Approximation:
Ist das gut oder schlecht? Genauer: Ist das schnell? Und ist die Qualität gut?
Schauen wir uns unsere Tabelle an um die Laufzeit zu bestimmen. Da wir jeden Wert durch teilen und abrunden, wird die Summe der Werte mindestens mal kleiner. Vergleichen wir also (es gilt ) mit , dann sehen wir, dass das Tableau von Problem' Grösse hat. Damit läuft der Algorithmus mal schneller.
Wie schlecht kann die Lösung dieser Approximation werden?
Beim Abrunden verlieren wir höchstens , d.h. also
Wir bezeichnen nun mit
ist die exakte optimale Lösung des Problems und mit
ist die optimale Lösung des skalierten Problems. Dann gilt
Wir wollten höchstens von der optimalen Lösung abweichen. Das können wir erreichen, indem wir so wählen, dass gilt.
Das Optimum kennen wir zwar nicht, aber wir wissen, dass es mindestens ist (unter der Annahme, dass kein Gegenstand ein grösseres Gewicht hat als in den Rucksack überhaupt reinpassen; sonst könnten wir diesen Gegenstand sofort entfernen, da wir ihn sicher nicht einpacken). Also wählen wir stattdessen so, dass gilt, also
Also haben wir eine -Approximation in Zeit
Die Laufzeit hängt jetzt nur noch von und dieser Approximationsstellschraube ab und ist völlig unabhängig von den Gewichten.
Sowas nennt man ein Approximationsschema: Sobald wir ein gewählt haben, ist quasi eine Konstante und der Algorithmus hat dann polynomielle Laufzeit. Die Laufzeit ist also ein Polynom in und in . In diesem Fall nennt man das Approximationsschema dann voll-polynomielles Approximationsschema (engl. FPTAS – fully polynomial-time approximation scheme).
Hier haben wir ein Riesenglück, denn solche Algorithmen sind sehr selten. Häufig kommt es vor, dass z.B. nicht als multiplikativer Faktor, sondern als Exponent auftaucht, z.B eine Laufzeit wie . Für ein fixes ist dies dann zwar immer noch polynomiell, aber die Potenz hängt nun von ab.
Wir erinnern uns an das Problem des Handlungsreisenden aus der allerersten Vorlesung. Gegeben sind Städte, nummeriert von bis , mit einem Distanzmass , welches für jedes die (gerichtete!) Distanz von Stadt nach beschreibt. Gesucht ist die kürzeste Rundreise, also eine Reise, welche jede Stadt genau einmal besucht und bei derselben Stadt startet und endet.
Gesucht ist also eine Permutation der Städte. Für und die Permutation sind die Kosten für die vier Teilstrecken aufsummiert .
Warum wollen wir jede Stadt genau einmal besuchen? Könnte es nicht kürzer sein gewisse Städte mehrfach zu besuchen? Ja, das kann sein. In vielen (sinnvollen) Graphen gilt aber die Dreiecksungleichung für jedes weshalb sich dann Doppelbesuche nicht mehr lohnen. Ausserdem nehmen wir an, dass jede Stadt mit jeder anderen verbunden ist.
Naive Lösung: Die naive Lösung für dieses Problem wäre es alle Permutationen durchzutesten, was wir in Zeit erledigen könnten. Das ist aber sehr langsam.
Induktive Lösung: Wir betrachten nun einzelne Reisestücke, also keine kompletten Rundreisen, sondern einfach einige aufeinanderfolgend besuchte Städte. Wir beschreiben ein Reisestück durch seinen Startknoten , seinen Endknoten und die Menge der besuchten Knoten .
Nach dem Optimalitätsprinzip wissen wir, dass für jedes Reisestück aus einer optimalen Rundreise gilt, dass es kürzest möglich ist. Für einen Reiseabschnitt mit fixem , und benutzen wir also immer den kürzesten Weg unter allen Wegen, die von nach ebenfalls genau die Knotenmenge benutzen.
Damit bauen wir folgende Rekursion:
Wir unterscheiden also welche Stadt wir als letztes besuchen. Dies führt zu einer Induktion über , da die rekursiven Aufrufe jeweils weniger Städte besuchen.
Da wir eine Rundreise suchen, können wir den Startknoten beliebig fixieren. Sei beispielsweise immer . Dann schreiben wir:
Wir starten mit der Verankerung und wollen schliesslich berechnen.
Laufzeit: Wir haben ein Tableau der Grösse und benötigen Zeit, um einen Eintrag zu berechnen. Die Gesamtzeit von ist immer noch viel, aber drastisch weniger als .