4 Greedy-Algorithmen (gierige Algorithmen)

Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
4 Greedy-Algorithmen (gierige Algorithmen)
I
Greedy-Algorithmen werden oft für die exakte oder approximative
Lösung von Optimierungsproblemen verwendet.
I
Typischerweise konstruiert ein Greedy-Algorithmus eine Lösung
Komponente für Komponente, wobei der Wert einer einmal
gesetzten Komponente nie zurückgenommen wird.
I
Beispiele: die Algorithmus von Kruskal, die Konstruktion eines
Huffman-Codes und der Approximationsalgorithmus für das
Binpacking Problem Best-Fit.
24
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Philosophie von Greedy-Verfahren
I
Iterative Konstruktion einer Lösung unter Verwendung lokaler
Optimalitätskriterien.
I
Hoffnung: Lokale Optimalität führt auch zur globalen Optimalität —
oder zumindest zu einer guten Approximation.
I
Verschiedene lokale Kriterien führen zu verschiedenen Algorithmen.
Analysemethoden für Greedy-Verfahren
Um zu zeigen, dass ein Greedy-Verfahren eine optimale Lösung findet,
werden im wesentlichen zwei Analysemethoden eingesetzt:
1. the greedy algorithm stays ahead: In jedem Schritt ist die gefundene
partielle Lösung des Greedy-Verfahrens mindestens so gut wie jede
andere partielle Lösung.
2. exchange argument: Jede Lösung kann Schrittweise in die Lösung
des Greedy-Verfahrens transformiert werden, ohne dass hierbei die
Güte der Lösung abnimmt.
25
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
4.1 Minimale Spannbäume
I
Gegeben ist ein ungerichteter, zusammenhängender, gewichteter
Graph G = (V , E ) mit einer positiven Kostenfunktion f : E → R+ .
I
Wir nehmen an, dass für alle Kanten e ∈ E f (e) > 0 ist.
I
Wir nennen T = (V 0 , E 0 ) einen Spannbaum von G , wenn V = V 0
und T ein Baum ist.
P
Gesucht ist ein Baum T = (V , E 0 ) mit E 0 ⊆ E , so dass, e∈E 0 f (e)
minimal unter allen Spannbäumen von G ist.
I
I
I
Ist f (e) konstant 1, so können wir dieses Problem wieder mit Hilfe
der Breiten- oder Tiefensuche lösen.
Wir werden im Folgenden das Verfahren von Kruskal vorstellen.
26
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
I
Zur effizienten Implementation benutzen wir die Datenstruktur der
Priorityqueue und der Partition. Die letztere Datenstruktur ist auch
unter dem Namen UNION/FIND-Datenstruktur bekannt.
I
Wir starten mit |V | einelementigen Mengen, von denen jede einen
anderen Knoten des Graphen enthält.
I
Diese Mengen werden als Bäume mit jeweils einem Knoten
interpretiert.
Sukzessive verschmelzen wir diese Mengen durch Hinzunahme einer
Kante mit minimalen Kosten: Finde die minimale Kante, die zwei
Knoten aus unterschiedlichen Mengen verbindet und vereinige die
beiden Mengen.
I
27
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Was ist eine Priorityqueue?
I
Wir betrachten eine Teilmenge M eines Universums U, wobei jedem
Element m ∈ M eine Priorität p(m) (oder kurz p) zugeordnet wird.
I
insert(m, p): fügt m ∈ U mit Priorität p in M ein.
I
deletemin: gibt das Element aus M mit minimaler Priorität zurück
und entfernt dieses aus M.
I
readmin: gibt das Element aus M mit minimaler Priorität zurück
ohne es zu entfernen.
I
decpriority(m, d): die Priorität von m in M wird um d reduziert.
Eine Priorityqueue kann mit Hilfe eines Heaps (Heapsort) so
implementiert werden, dass die Laufzeiten der Initialisierung in O(|M|),
von readmin in O(1) und der drei verbleibenden Operationen in
O(log |M|) liegen.
28
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
Was ist eine UNION/FIND-Datenstruktur bzw. eine Partition?
I
I
Partitionen stellen eine eingeschränkte Form von Mengen dar.
Der abstrakten Datentyp ist wie folgt definiert:
I
I
I
I
U = {1, . . . , n} sei ein Universum.
P = {P1 , . . . , Pk } sei eine Menge
von disjunkten, nicht leeren
S
Teilmengen von U mit U = ni=1 Pi . Wir nennen diese Teilmengen
Partitionsblöcke oder kurz Blöcke.
Jedem Partitionsblock Pi wird ein Element ni ∈ Pi als Repräsentant
(bzw. als Name) zugeordnet.
Auf P sind die folgenden zwei Prozeduren definiert: Sei x ∈ U und
ni , nj Repräsentanten zweier Partitionsblöcke Pi und Pj .
I
I
find(x) liefert den Repräsentanten ni der Menge Pi mit x ∈ Pi .
union(ni , nj ) vereinigt die Blöcke mit den Repräsentanten ni und nj .
Diese Operation verändert die Menge P, d.h.
P = (P \ {Pi , Pj }) ∪ {Pi ∪ Pj }. Der Repräsentant der neuen Menge
ist entweder ni oder nj .
29
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Die UNION/FIND-Datenstruktur kann recht einfach so implementiert
werden, dass
I
die Initialisierung in Zeit O(|U|),
I
jede union-Operation in konstanter Zeit und
jede find-Operation in Zeit O(log2 |U|)
I
ausgeführt werden kann. Einige aufwendigere Implementierungen
erlauben es die Laufzeit der find-Operation erheblich zu reduzieren.
30
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Algorithmus MST-Kruskal()
Eingabe: global gegebener Graph G
Ergebnis: minimaler Spannbaum T = (V , E 0 )
1: Bilde die Priorityqueue Q aller e ∈ E mit Prioritäten f (e).
2: Initialisiere die Partitionen {v } für alle v ∈ V .
3: E 0 := ∅, k = |V |
4: while k > 1 do
5:
{v , w } := deletemin(Q); v0 := find(v ); w0 := find(w );
6:
if v0 6= w0 then
7:
union(v0 , w0 ); E 0 := E 0 ∪ {{v , w }}; k := k − 1;
8:
end if
9: end while
10: Return(T = (V , E 0 ))
31
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
Beispiel
3
1
5
6
2
4
5
6
2
16
13
4
1
7
9
3
0. Initialisierung
1
1. deletemin= {3, 6}
find(3) 6= find(6)
1
5
2. deletemin= {1, 2}
find(1) 6= find(2)
1
5
5
2
6
6
2
4
3
2
6
1
3
4
2
1
4
3
32
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
3. deletemin= {5, 1}
find(5) 6= find(1)
4. deletemin= {5, 6}
find(5) 6= find(6)
3
3
1
5
3
1
2
5
2
4
2
4
6
4
1
2
6. deletemin= {1, 6}
find(1) = find(6)
3
7. deletemin= {2, 3}
find(2) = find(3)
3
8. deletemin= {3, 4}
find(3) 6= find(4)
3
1
5
2
3
1
5
2
4
6
1
4
2
5
2
4
6
1
4
1
3
3
5
2
6
1
2
1
4
6
2
5. deletemin= {2, 6}
find(2) = find(6)
4
6
1
4
2
4
1
9
3
3
3
33
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Korrektheit
Lemma 1 Sei
I
G = (V , E ) ein ungerichteter Graph,
I
T = (V , ET ) ein minimaler Spannbaum für G ,
I
W = (V , EW ) ein Wald der in T enthalten ist, d.h. EW ⊆ ET und
I
S ⊆ V eine Knotenmenge, so dass keine Kante aus EW zwischen
den Mengen S und V \ S verläuft.
Wir nennen eine Kante aus E kreuzend, wenn sie einen Knoten aus S
mit einem Knoten aus V \ S verbindet. Ist e ∈ E eine kreuzende Kante,
die minimale Kosten unter allen kreuzenden Kanten besitzt, dann ist
auch W 0 := (V , EW ∪ {e}) in einem minimalen Spannbaum enthalten.
34
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
Beweis von Lemma 1:
Angenommen, T enthält W aber nicht W 0 .
V \S
S
I
Dann gilt e 6∈ ET .
I
T ist ein Spannbaum, somit gibt es von
jedem Knoten in V einen Weg zu jedem
anderen Knoten in V .
I
Addieren wir e zu T , so schließen wir
einen Kreis C .
C besitzt neben e noch eine kreuzende
Kante e 0 .
e
I
I
Sei T 0 := (V , (ET ∪ {e}) \ {e 0 }).
I
T 0 ist ein Spannbaum von G , da T 0 wieder zyklenfrei ist und |V | − 1
Kanten hat.
I
Da f (e) minimal unter allen kreuzenden Kanten ist, gilt
f (e) ≤ f (e 0 ).
35
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Beweis von Lemma 1 (Teil 2)
P
P
I Ist f (e) < f (e 0 ), so gilt
w ∈ET0 f (w ) <
w ∈ET f (w ) für
ET0 = (ET ∪ {e}) \ {e 0 }. Dieses widerspricht der Annahme, dass T
ein minimaler Spannbaum ist. Wir können somit ausschließen, dass
f (e) < f (e 0 ) ist.
I
Ist f (e) = f (e 0 ), so haben T und T 0 die gleichen Kosten. Da T ein
minimaler Spannbaum ist, muss auch T 0 ein minimaler Spannbaum
sein. Wir haben somit gezeigt, dass W 0 in einem minimalen
Spannbaum enthalten ist.
36
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
Korrektheit vom Kruskals Algorithmus
I
Der MST-Algorithmus nimmt immer eine minimale kreuzende Kante
in den bereits konstruierten Wald W auf.
I
I
Sei e = {u, v } = deletemin(Q).
Über die Abfrage find(u) = find(v ) wird überprüft, ob u und v
bereits in einer Komponente von W liegen. Beachte: Mit jeder
eingefügten Kante {u 0 , v 0 } vereinigen wir die entsprechenden
Mengen find(u 0 ) und find(v 0 ). Somit repräsentiert jede Menge der
Partition einen Baum des konstruierten Walds.
I
I
I
Ist find(u) = find(v ), so verwerfen wir die Kante.
Ist find(u) 6= find(v ), so stellt S die Knotenmenge des Teilbaums dar,
in dem u liegt. Somit ist e eine minimale kreuzende Kante.
Aus Lemma 1 können wir nun schließen, dass W 0 = (V , EW ∪ {e})
in einem minimalen Spannbaum enthalten ist, wenn auch
W = (V , EW ) in einem minimalen Spannbaum enthalten ist.
37
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Laufzeit von Kruskals Algorithmus
I
Die Initialisierung der Priorityqueue gelingt in Zeit O(|E |).
I
Die Initialisierung der Partitionen gelingt in Zeit O(|V |).
I
Die While-Schleife muss im Worst-Case |E | mal durchlaufen werden.
Bei jedem Durchlauf werden einmal die Operationen deletemin und
zweimal die Operation find aufgerufen. Nach unseren Annahmen
über die Priorityqueue und der UNION/FIND-Datenstruktur können
wir diese Operationen in Zeit O(|E | · log |E |) ausführen.
I
In |V | − 1 Durchläufen der While-Schleife wird jeweils einmal eine
union-Operation aufgerufen.
I
Zusammen erhalten wir eine Laufzeit von O(|E | · log |E |).
38
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
Satz 1 Sei G = (V , E ) ein zusammenhängender, ungerichteter,
gewichteter Graph. Dann berechnet Kruskals Algorithmus einen
minimalen Spannbaum für G in Zeit
O(|E | · log |E |) .
Beobachtung 1 Betrachten wir die Aussage von Lemma 1 und den
Korrektheitsbeweis von Kruskals Algorithmus, so erkennen wir, dass wir
hierbei ein exchange argument angewendet haben.
39
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
2. Vorlesung, 31.10.2007
4.2 Intervall-Scheduling
Definition 3 [Intervall-Scheduling Problem] Gegeben sei
I
I
eine Menge R = {1, . . . , n} von n Jobs und
zwei Funktionen s, f : R → N.
Hierbei gilt für alle Jobs i
s(i) ≤ f (i)
I
s(i) nennen wir die Startzeit von Job i und
I
f (i) nennen wir die Endzeit von Job i.
Job i steht im Konflikt mit Job j, wenn
I
i 6= j und
I
die Intervalle [s(i), f (i)[ und [s(j), f (j)[ sich überlappen.
Mit [s(i), f (i)[ bezeichnen wir das nach rechts offene reelle Intervall.
40
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Definition 3 (Teil 2)
I
Eine Teilmenge S ⊆ R ist eine zulässige Schedule, wenn S
konfliktfrei ist, d.h. für alle i, j ∈ S steht i nicht im Konflikt zu j.
I
Eine Teilmenge S ⊆ R ist eine optimale Schedule, wenn S eine
zulässige Schedule maximaler Kardinalität ist, d.h. |S| ist maximal.
Aufgabe: Bestimme eine optimale Schedule!
41
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Wir starten mit einem Grundgerüst für einen Greedy-Algorithmus für das
Intervall-Scheduling Problem:
Algorithmus Greedy-Intervall-Schedule(R)
Eingabe: Menge R
Ergebnis: optimale Schedule S
1: S := ∅
2: while R 6= ∅ do
3:
wähle ein eine Job i ∈ R
4:
S := S ∪ {i};
5:
entferne alle Jobs aus R, die zu i im Konflikt stehen
6:
R := R \ {i}
7: end while
8: Return(S)
Unsere Aufgabe besteht jetzt darin, den Auswahlmechanismus in Zeile 3
näher zu beschreiben.
42
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Wir starten mit einer einfachen Beobachtung:
Beobachtung 2 Für alle Auswahlmechanismen ist das Ergebnis S eine
zulässige Schedule.
Diese Beobachtung folgt unmittelbar daraus, dass wir in Zeile 5 alle Jobs
löschen, die zu einem einmal in die Schedule aufgenommenen Job im
Konflikt stehen.
43
Andreas Jakoby
Universität zu Lübeck
Algorithmik WS 07/08
2. Vorlesung, 31.10.2007
Einfache Auswahlmechanismen:
1. wähle i mit s(i) = minj∈R s(j)
2. wähle i mit f (i) − s(i) = minj∈R f (j) − s(j)
3. wähle das i, welches mit den wenigsten Jobs in R im Konflikt steht
4. wähle i mit f (i) = minj∈R f (j)
44
Algorithmik WS 07/08
Andreas Jakoby
Universität zu Lübeck
I
2. Vorlesung, 31.10.2007
Anhand der nachfolgenden Graphik können wir leicht erkennen, dass
die ersten drei Auswahlmechanismen auf Folie 44 keine optimale
Schedule liefern.
1.
2.
3.
I
Behauptung Benutzen wir jedoch den vierten Mechanismus in Zeile
3 von Algorithmus Greedy-Intervall-Schedule, so erhalten wir eine
optimale Schedule. Dieses muss aber noch bewiesen werden!
45