Einführung: Dynamische Programmierung¶
Bisher zwei Paradigmen:
- Divide-and-conquer
- Greedy
Weiteres Paradigma: Dynamische Programmierung (dynamic programming)
Einführung am Beispiel des
Weighted-Independent-Set Problem¶
Gegeben: Ungerichteter Graph $G=(V,E)$
Eine unabhängige Menge (independent set) ist eine Untermenge $S \subseteq V$ von gegenseitig nicht angrenzenden Knoten, d.h. für jedes $v,w \in S$ gilt $(v,w)\notin E$.
Beispiel: Personen (Knoten), die sich nicht mögen (Kanten), ergeben ("harmonische") Gruppen.
Quiz¶
Wieviele Independent-Sets haben folgende Graphen:
- Fünf vollvernetzte Knoten.
- Fünf Knoten zu einem Ring vernetzt.
Problem: Weighted-Independent-Set¶
Input (Eingabe): Ein ungerichteter $G=(V ,E)$ und ein nicht-negatives Gewicht $w$ für jeden Knoten $v \in V$.
Output (Ausgabe): Eine unabhängige Menge (independent set) $S \subseteq V$ von $G$ mit der maximal-möglichen Summe $W = \sum_{v \in S} w_v$ der Knoten-Gewichte.
Die Lösung des Problems wird MWIS (maximum weighted independent set) genannt.
Als einführendes Beispiel in die dynamische Programmierung betrachten wir hier
Pfad-Graphen (Path Graphs, genaue Definition später), d.h. "lineare Ketten".
Beispiel¶
Lineare Kette mit vier Knoten mit den Gewichten: $1,4,5,4$
Greedy Algorithmus liefert falsche Lösung¶
WIS: Greedy Ansatz
$S:=\emptyset$
sort vertices of $V$ by weight
for each $v \in V$, in nonincreasing order of weights do
if $S \cup \{ v \}$ is an independent set of $G$ then
$S := S \cup \{v\} $
return $S$
Quiz¶
Welches Ergebnis liefert der Greedy Algorithmus für unser Beispiel (lineare Kette mit vier Knoten)?
Ist das Ergebnis richtig?
Divide and Conquer Ansatz¶
WIS: Divide and Conquer Approach
$G_1 :=$ first half of $G$
$G_2 :=$ second half of $G$
$S_1 :=$ recursivly solve the WIS problem on $G_1$
$S_2 :=$ recursivly solve the WIS problem on $G_2$
combine $S_1, S_2$ into a solution $S$ for $G$
return $S$
Problem: Wie soll die Kombination (Merge) ablaufen bzw. wie sollen die Unterprobleme gelöst werden, diese müssen ja zur Kombination passen.
Optimale Unterstruktur und Rekurrenz¶
$G_n =(V, E)$ sei ein Pfad-Graph
- mit Kanten $(v_1, v_2), (v_2, v_3), \dots, (v_{n-2}, v_{n-1}), (v_{n-1}, v_n)$.
- jeder Knoten $v_i \in V$ habe ein Gewicht $w_i$.
- $n \geq 2$
Für eine Lösung $S$ des MWIS-Problem gilt (Tautologie):
- $v_n \notin S$ oder
- $v_n \in S$
Fall 1: $v_n \notin S$¶
- der $(n-1)$ Pfad-Graph $G_{n-1}$ ergibt sich durch Entfernen des letzten Knotens $v_n$ und der letzten Kante $(v_{n-1}, v_n)$ von $G_n$
- für Fall 1 ist eine Lösung des MWIS-Problems von $G_{n-1}$ auch eine Lösung von $G_n$
Fall 2: $v_n \in S$¶
- hier muss gelten: $v_{n-1} \notin S$
- $S$ muss die Lösung des MWIS-Problems von $G_{n-2}$ plus $v_n$ sein.
- der $(n-2)$ Pfad-Graph $G_{n-2}$ ergibt sich durch Entfernen der beiden letzten Knoten $v_n, v_{n-1}$ und der beiden letzten Kanten $(v_{n-1}, v_n), (v_{n-2}, v_{n-1})$ von $G_n$
Lemma 16.1. (WIS Optimale Unterstruktur)¶
$S$ sei eine Lösung des MWIS eines Pfad-Graphen mit $n\geq2$-Knoten. $G_i$ notiert den Untergraphen von $G_n$ bestehend aus den ersten $i$-Knoten und ersten $i-1$ Kanten. Dann ist $S$ entweder
- ein MWIS von $G_{n-1}$ oder
- ein MWIS von $G_{n-2}$ ergänzt durch den letzten Knoten $v_n$ von $G$.
Es gibt also zwei Möglichkeiten die Lösung $S$ des MWIS aus einer Lösung eines Teilproblems zu konstruieren. Das Maximum der beiden Lösungsmöglichkeiten ist die Lösung $S$ des Gesamtproblems:
$$W_n = \text{max}\left\{W_{n-1}, W_{n-2} + w_n \right\}$$
Rekursion¶
Daher gilt im Allgemeinen (für die entsprechenden Unterprobleme):
$$W_i = \text{max}\left\{W_{i-1}, W_{i-2} + w_i \right\}$$
für alle $i = 2,3, \dots, n$ mit $G_i$ als Eingabe-Graphen
Naiver rekursiver Algorithmus¶
Rekursiver Algorithmus für WIS¶
Input: a path graph $G$ with vertex set $\left\{v_1,v_2,v_3, \dots, v_n \right\}$ and a nonnegative weight $w_i$ for each vertex $v_i$
Output: a maximum-weight independent set of $G$
if $n=0$ then
// base case #1
return the empty set
if $n=1$ then// base case #2
return $\{ v_1\}$
// recursion when$n\geq2$
$S_1 :=$ recursively compute an MWIS of $G_{n-1}$
$S_2 :=$ recursively compute an MWIS of $G_{n-2}$
return $S_1$ or $S_2 \cup \{v_n\}$, whichever has higher weight
Quiz¶
Wie ist die Laufzeit des naiven rekursiven Ansatzes?
Quiz¶
Wie viele verschiedene Unterprobleme / Subgraphen werden betrachtet?
Die Lösungen der Unterprobleme werden im naiven Algorithmus immer wieder neu berechnet, sodass sich die exponentielle Laufzeit ergibt. Eine Lösung wäre es die Lösungen in einem Cache zu speichern und bei Bedarf abzurufen, statt sie immer wieder neu zu berechnen. Dadurch ergibt sich eine lineare Laufzeit.
Iterative Bottom-Up Implementierung¶
WIS¶
Input: a path graph $G$ with vertex set $\left\{v_1,v_2,v_3, \dots, v_n \right\}$ and a nonnegative weight $w_i$ for each vertex $v_i$
Output: the total weight of a maximum-weighted independent set of $G$
$A:=$ length-$(n+1)$ array
\\ subproblem solutions
$A[0]:=0$// base case #1
$A[1]:=w_1$// base case #2
for $i:=2$ to $n$ do
$A[i]:= \text{max}\left\{A[i-1], A[i-2] + w_i \right\}$
return $A[n]$
Beispiel:
für die Gewichte
$w_1=3, w_2=2, w_3=1, w_4=6, w_5=4, w_6=5$
Ergeben sich die Array-Werte:
0 | 3 | 3 | 4 | 9 | 9| 14¶
Quiz¶
Laufzeit des Algorithmus?
Der Algorithmus berechnet die Summe der Gewichte aber nicht direkt die Lösung, d.h. die Menge der Knoten.
- Diese Lösung könnte man durch Erweiterung des obigen Algorithmus erhalten.
- Die Lösung lässt sich aber auch durch einen Rekonstruktionsalgorithmus erhalten.
WIS Reconstruction¶
Input: an array computed by the
WISalgorithm for a path graph $G$ with vertex set $\{ v_1, v_2, \dots, v_ n \}$ and a nonnegative weight $w_i$ for each vertex $v_i$
Output: a maximum-weight independent set of $G$
$S := \emptyset$
$i:= n$
while $i \geq 2$ do
if $A[i-1] \geq A[i-2] + w_i$ then
$i :=i-1$
else
$S := S \cup \{ v_i \}$
$i :=i-2$
if $i=1$ then
$S := S \cup \{ v_1 \}$
return $S$
für das Beispiel mit den Gewichten $w_1=3, w_2=2, w_3=1, w_4=6, w_5=4, w_6=5$
und den berechneten Array-Werten:
0 | 3 | 3 | 4 | 9 | 9 | 14¶
ergibt sich $S := \{1,4,6\}$
Prinzipien der Dynamischen Programmierung¶
- Identifiziere eine relative kleine Menge von Unterproblemen
- Zeige, wie man schnell und korrekt ein größeres Unterproblem aus kleineren Unterproblemen konstruieren kann.
- Zeige, wie man schnell und korrekt die Lösung des Gesamtproblems aus den Lösungen der Unterprobleme rekonstruieren kann.
Laufzeit¶
$$ f(n) \cdot g(n) + h(n) $$
- $f(n)$: Anzahl der Unterprobleme
- $g(n)$: Zeit pro Unterproblem
- $h(n)$: Rekonstruktion/Postprocessing
Beispiel WIS für Pfad-Graphen:
$$f(n) \cdot g(n) + h(n)$$
- $f(n) = O(n)$: Anzahl der Unterprobleme
- $g(n) = O(1)$ : Zeit pro Unterproblem
- $h(n) = O(n)$: Rekonstruktion/Postprocessing
$$ O(n) \cdot O(1) + O(n) = O(n) $$
Literatur¶
- T. Roughgarden, Algorithms Illuminated, Part 3: Greedy Algorithms and Dynamic Programming