Bisher zwei Paradigmen:
Jetzt kommt Dynamische Programmierung (dynamic programming) hinzu.
Warnung: Dieses Konzept ist etwas schwieriger zu verstehen.
Einführung am Beispiel des
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.
Wieviele Independent-Sets haben folgende Graphen:
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 nur
Pfad-Graphen (Path Graphs, genaue Definition später), d.h. "lineare Ketten".
Lineare Kette mit vier Knoten mit den Gewichten: $1,4,5,4$
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$
Welches Ergebnis liefert der Greed Algorithmus für unser Beispiel (lineare Kette mit vier Knoten)?
Ist das Ergebnis richtig?
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.
$G_n =(V, E)$ sei ein Pfad-Graph
Für eine Lösung $S$ des MWIS-Problem gilt (Tautologie):
$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 erste $i$-Knoten und ersten $i-1$ Kanten. Dann ist $S$ entweder
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\}$$Daher gilt im Allgemeinen (für kleinere 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
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
Wie ist die Laufzeit des naiven rekursiven Ansatzes?
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.
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-weight 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:
Laufzeit des Algorithmus?
Der Algorithmus berechnet die Summe der Gewichte aber nicht direkt die Lösung, d.h. die Menge der Knoten.
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:
ergibt sich $S := \{1,4,6\}$
- 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öungen der Unterprobleme rekonstruieren kann.
Beispiel WIS für Pfad-Graphen:
$$f(n) \cdot g(n) + h(n)$$