Try   HackMD

11 Dynamische Programmierung 2

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.

Einführung

Beispiel: Partitionierungsproblem

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

n 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

a1,a2,...,an

Gesucht:

halbierbar(a1,a2,,an)={truefalls I{1,,n} sodass ΣiIai=ΣiIai,falsesonst.

Es scheint schwierig, die Gleichung

ΣiIai=ΣiIai 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
s=Σi=1nai2
und suchen stattdessen nach einer Teilmenge der Zahlen, welche summiert genau
s
ergibt. Dies nennt man auch das Subset-Sum-Problem.

Subset-Sum-Problem

Gegeben sind die Elemente

aiN mit
i=1,,n
, sowie eine vorgegebene Summe
sN
.
Frage:
I{1,,n}
s.t.
ΣiIai=s
?

erreichbar(a1,a2,,an,s)={truefalls I{1,,n} sodass ΣiIai=s,falsesonst.

Wir könnten naiverweise alle möglichen Teilmengen

I ausprobieren. Dann müssten wir aber
2n
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

i-te Bit einer Zeile sagt aus, ob die
i
-te Zahl Teil der Menge
I
ist oder nicht.

Neue Idee: Wir merken uns welche Summen wir mit den ersten

i Zahlen erreichen können. Die Summe
0
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

err(i,z)=1 falls die Summe
z
mit den ersten
i
Zahlen erreichbar ist. Wenn
z
mit den ersten
i
Zahlen erreichbar sind, haben wir entweder die
i
-te Zahl nicht genommen und können
z
bereits mit den ersten
i1
Zahlen erreichen, oder wir haben die
i
-te Zahl genommen und können mit den ersten
i1
Zahlen die Summe
zai
erreichen:
err(i,z)=err(i1,z)err(i1,zai)

Rekursiv

Das einfach rekursiv auszurechnen hat Laufzeit

2n

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Bottom up

Wir können jedoch eine DP-Tabelle err der Grösse

ns verwenden, in der der Eintrag err[i,z] der obigen Definition von
err(i,z)
entspricht.

for i,j = 0 to n err[i,j] = False err[0,0] = True for i=1 to n for z = 0 to s if ( err[i-1,z] ) then err[i,z] = True else if ( (z-a_i) >= 0 and err[i-1,z-a_i] ) then err[i,z] = True end if end for end for

Sobald wir die Tabelle berechnet haben, wissen wir ob die Summe erreichbar ist oder nicht, indem wir den Eintrag

err[n,s] 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:

s 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
n
), 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

n 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

s 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

2n2 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:

0,3,5,8 (alle Summen die mit 3 und 5 erreichbar sind) und
0,2,7,9
(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:

  • Teile in 2 Mengen der Grösse
    n2
  • Berechne die Summen aller Teilmengen der beiden Mengen. Die Laufzeit ist
    2n/22n/2
    , weil es für beide Hälften
    2n/2
    Teilmengen gibt.
  • Sortiere diese Summen in Laufzeit
    O(2n/2log(2n/2))=O(2n/2n/2)
    .
  • Suche nach einem Summenpaar, das genau
    S
    ergibt. Dafür benötigen wir einen linearen Durchgang. Dieser hat Laufzeit
    O(2n/2)
    .

Insgesamt haben wir also eine Laufzeit von

O(n/22n/2)=O(n/22n).
Ist das jetzt viel besser als
2n
? Ja! Bei exponentiellen Algorithmen ist auch die kleinste Verbesserung an der Basis wichtig. Selbst
1.99n
ist exponentiell viel schneller als
2n
.[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(

ns)) unter Umständen deutlich schneller.

Beispiel: Rucksack-Problem (Knapsack).

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

n 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:

vi und
wi
für
i=1,,n
, also Wert (value) und Gewicht (weight) der
n
Gegenstände, sowie ein Gesamtgewicht
W
, 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:

I{1,..,n}, so dass
iIwiW
und
iIvi
maximal.

Beispiel:

​v 5 7 8 (values)
​w 3 2 4 (weights)

Erste Idee: Greedy / gierig:
Wir sortieren die Gegenstände absteigend nach

v/w 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:

v1=w1(1+ϵ) mit
w1
sehr klein
v2=w2=W

oder konkreter:

v1=3,
w1=2

v2=999999
,
w2=999999

mit
W=1000000

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.

Erster DP-Ansatz

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

i Gegenständen einen Mindestwert erreichen können. Also:

machbar(i,v,w)=1 wenn mit den ersten
i
Gegenständen ein Gesamtgewicht
w
nicht überschreiten und einen Gesamtwert
v
mindestens erreichen können, und
machbar(i,v,w)=0
falls nicht.

Das ist nur eine von vielen möglichen Formulierungen, aber eine, die sehr nach Induktion riecht. Denn nun gilt wiederum, dass

machbar(i,v,w) wahr ist, wenn wir
v
und
w
bereits mit den ersten
i1
Gegenständen erreichen können oder wenn wir mit den ersten
i1
Gegenständen den Wert
vvi
und
wwi
erreichen können. Es gilt also

machbar(i,v,w)=machbar(i1,v,w)machbar(i1,vvi,wwi).

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

machbar(n,i=1nvi,W). Doch das wird im Normalfall nicht möglich sein. Wir müssen daher
machbar(n,V,W)
für alle
Vi=1nvi
betrachten, um den maximalen Wert zu finden, den wir ergattern können.

Dies ergibt ein dreidimensionales Tableau der Grösse

niviW.

Die Berechnung jedes Eintrags kostet jeweils konstante Zeit. Als totale Laufzeit erhalten wir also Tableau-Grösse

Eintragsberechnungsdauer
=O(nWivi)
. Ist dies bereits eine gute Laufzeit oder geht es noch schneller?

Zweiter DP-Ansatz

Überlegen wir uns, wo im Tableau die Antwort zu finden ist: Wir müssen für

i=n und
w=W
den maximalen Mindestwert suchen, für den die Antwort Ja ist. Für fixierte
i
und
w
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

i und
w
die Form
(Y)(N)
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

nW und ein Eintrag
[i,j]
enthält den maximalen Wert, den man mit den ersten
i
Gegenständen und einer Gewichtsschranke
j
erreichen kann. Ein Eintrag wird wie folgt berechnet:

erreichbarerWert(i,w)=max{erreichbarerWert(i1,w)erreichbarerWert(i1,wwi)+vi)

Somit erhalten wir ein neues Tableau der Grösse

nW, und die Berechnung jedes Eintrages erfolgt weiterhin aus nur zwei vorhergehenden Einträgen. Die Gesamtlaufzeit des neuen dynamischen Programs ist also
O(nW)
.

Das ist wiederum eine pseudopolynomielle Lösung. Bei sehr grossem

W 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.

Approximationsansatz

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

I, sodass
iIvi(1ε)iOPTvi,

wobei
OPT
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

i notieren.

​	0	1	...	n*Vmax
​0
​1
​2
​.
​.
​.
​n

Wir haben also in Zeile

i die ersten
i
Gegenstände zur Verfügung und in Spalte
v
einen bestimmten möglichen Wert. Ein Eintrag
[i,v]
sagt, welche Gewichtsgrenze nötig ist, damit man mit den ersten
i
Gegenständen den Wert
v
erreichen kann.

errGewicht(i,v)=min{errGewicht(i1,v)errGewicht(i1,vvi)+wi)

Die Tabellengrösse ist

O(nivi) und die Berechnung eines Eintrags erfolgt in konstanter Zeit. Insgesamt haben wir also eine Laufzeit von
O(nivi)=O(nnvmax)

Was passiert nun, wenn wir bei jedem Gegenständen die letzten drei Stellen des Wertes

vi streichen und hoffen dass dabei nicht viel kaputt geht?

Approximation:

  • Bilde
    vi=viK
    für alle
    i
    . Wir bezeichnen mit Problem' das Rucksackproblem für die neue Eingabe
    vi,wi,W
    .
  • Löse Problem' mit DP (Die Tabelle hat Grösse
    nivi
    )
  • Nimm die Lösung für Problem' als Lösung für das ursprüngliche Problem.

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

K teilen und abrunden, wird die Summe der Werte mindestens
K
mal kleiner. Vergleichen wir also
vmax=maxi(vi)
(es gilt
ivinvmax
) mit
vmax=maxi(vi)
, dann sehen wir, dass das Tableau von Problem' Grösse
O(nnvmaxK)
hat. Damit läuft der Algorithmus
K
mal schneller.

Wie schlecht kann die Lösung dieser Approximation werden?
Beim Abrunden verlieren wir höchstens

K, d.h. also

viKKviKvi

Wir bezeichnen nun mit

OPT ist die exakte optimale Lösung des Problems und mit
OPT
ist die optimale Lösung des skalierten Problems. Dann gilt

iOPTvinKiOPTviiOPTKiOPT(viK)iOPTKvi/K=KiOPTvi/KKiOPTviK=iOPTKvi/KiOPTviK

Wir wollten höchstens

ε von der optimalen Lösung abweichen. Das können wir erreichen, indem wir
K
so wählen, dass
nK=εiOPTvi
gilt.

Das Optimum kennen wir zwar nicht, aber wir wissen, dass es mindestens

vmax 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
K
stattdessen so, dass
nK=εvmax
gilt, also
K=εvmaxn.

Also haben wir eine

(1ε)-Approximation in Zeit
O(n2vmaxK)=O(n3ε)

Die Laufzeit hängt jetzt nur noch von
n
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
n
und in
1ε
. 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.

1ε nicht als multiplikativer Faktor, sondern als Exponent auftaucht, z.B eine Laufzeit wie
O(n1ε)
. Für ein fixes
ε
ist dies dann zwar immer noch polynomiell, aber die Potenz hängt nun von
ε
ab.

Rundreiseproblem (ergänzt HS 2017)

Wir erinnern uns an das Problem des Handlungsreisenden aus der allerersten Vorlesung. Gegeben sind

n Städte, nummeriert von
1
bis
n
, mit einem Distanzmass
di,j
, welches für jedes
ij
die (gerichtete!) Distanz von Stadt
i
nach
j
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

n=4 und die Permutation
π=(2,3,1,4)
sind die Kosten für die vier Teilstrecken aufsummiert
dπ(1),π(2)+dπ(2),π(3)+dπ(3),π(4)+dπ(4),π(1)=d2,3+d3,1+d1,4+d4,2
.

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

di,jdi,k+dk,j für jedes
i,j,k
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

n! Permutationen durchzutesten, was wir in Zeit
O(nn!)
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

i, seinen Endknoten
j
und die Menge der besuchten Knoten
S
.

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

i,
j
und
S
benutzen wir also immer den kürzesten Weg unter allen Wegen, die von
i
nach
j
ebenfalls genau die Knotenmenge
S
benutzen.

Damit bauen wir folgende Rekursion:

D(S,i,j)=minkS,kj(D(S{j},i,k)+dk,j)
Wir unterscheiden also welche Stadt wir als letztes besuchen. Dies führt zu einer Induktion über
|S|
, da die rekursiven Aufrufe jeweils weniger Städte besuchen.

Da wir eine Rundreise suchen, können wir den Startknoten beliebig fixieren. Sei beispielsweise immer

1S. Dann schreiben wir:
D(S,j)=minkS,kj(D(S{j},k)+dk,j)

Wir starten mit der Verankerung

D({1},1)=0 und wollen schliesslich
D([n],1)
berechnen.

D({1},1)=0 for z = 2 to n do for each S \subseteq {1,...,n} mit |S|=z und 1 in S: D(S,1) = inf for each j in S, j ≠ 1 do D(S,j) := min_{k in S, k ≠ j}(D(S\{j},k)+d_{k,j}) return min_j(D([n],j)+d_{j,1})

Laufzeit: Wir haben ein Tableau der Grösse

n2n und benötigen
O(n)
Zeit, um einen Eintrag zu berechnen. Die Gesamtzeit von
O(n22n)
ist immer noch viel, aber drastisch weniger als
O(n!)
.