Upload
heilwig-allgaier
View
107
Download
2
Embed Size (px)
Citation preview
11.04.23 Kapitel 1 1
Methoden des Algorithmenentwurfs
Kapitel 1: Einführung
Christian Scheideler
SS 2009
Organisatorisches
Leitung: Prof. Dr. Christian Scheideler• Sprechstunde: Do, 16-17 Uhr• Email: [email protected]
Modulinformation:• Modul II.2.1 Modelle und Algorithmen (MuA)• V2+Ü1• 3 ECTS Credits
Zeit und Ort:• Mi 16-18 Uhr, F0.530
Webseite:• http://www.cs.upb.de/fachgebiete/fg-ti/lehre0/ss2009/methoden.html
11.04.23 Kapitel 1 2
Organisatorisches
Übungen:• Übungsleitung: NN• Mi 14-16 Uhr, F0.530, 14-tägig ab 29. April• Übungszettel:
Ausgabe: 14-tägig auf dieser Seite zum ÜbungsterminAbgabe: eine Woche danach in der VorlesungRückgabe: eine Woche danach in der Übung
Schein:Einen Schein erhält, wer die Klausur am Ende des Semesters besteht. Bei Vorrechnen einer Aufgabe verbessert sich die Note um 0,3 Punkte.
11.04.23 Kapitel 1 3
Organisatorisches
Inhalt:
• Teil 1: Approximationsalgorithmen– 1.1 Einführung [1w]– 1.2 Approximation mit absoluter Güte [2w]– 1.3 Approximation mit relativer Güte [2w]– 1.4 Approximationsschemata [2w]– 1.5 Lineare Optimierung und
Approximationsalgorithmen [2w]
11.04.23 Kapitel 1 4
Organisatorisches
• Teil 2: Online-Algorithmen– 2.1 Deterministische Online-Algorithmen
(Scheduling, Paging, selbstorganisierende Datenstrukturen) [3w]
– 2.2 Randomisierte Online-Algorithmen(Scheduling, Paging, selbstorganisierende Datenstrukturen, Lastbalancierung) [2-3w]
11.04.23 Kapitel 1 5
Literatur• Approximationsalgorithmen:
– Rolf Wanka.Approximationsalgorithmen: Eine EinführungVieweg & Teubner Verlag, 2006.
– Klaus Jansen und Marian Margraf.Approximative Algorithmen und Nichtapproximierbarkeit.De Gruyter Verlag, 2008.
• Online-Algorithmen:– Susanne Albers.
Online- und Approximationsalgorithmen.Universität Freiburg, SS 2004.Verfügbar über WWW.
– Christian Scheideler.Universal Routing Strategies for Interconnection Networks.Springer Verlag, LNCS 1390, 2007.
11.04.23 Kapitel 1 6
11.04.23 Kapitel 1 7
Kapitel 1.1: Einführung
Inhalt:• Einführung in P vs. NP• Approximationsalgorithmen• Beispiele
– Lastbalancierung– Zentrumswahl– Rucksackproblem
P vs. NP
• Algorithmus: berechnet in endlicher Zeit aus einer Eingabe eine Ausgabe.
• zentrales Problem: möglichst effizienter Algorithmus (Zeit und Speicher)
11.04.23 Kapitel 1 8
Eingabe
Algorithmus
Ausgabe
P vs. NP
• Ein Algorithmus ist „schnell“, falls seine Laufzeit polynomiell in der Eingabegröße ist.
• Eingabegröße: Anzahl der Elemente der Eingabe (z.B. Sortierproblem, Graph) oder Anzahl Bits / Wörter, aus denen Eingabe besteht (Multiplikation großer Zahlen)
• Polynomiell: Laufzeit ist O(nk) für eine Konstante k bei Eingabegröße n.
11.04.23 Kapitel 1 9
P vs. NP
n 20 60 100 300 1000
5n 100 300 500 1500 5000
n log n 86 354 665 2469 9966
n2 400 3 600 10 000 90 000 1 000 000
n3 8000 216 000 1 000 000 27 000 000 1 000 000 000
2n 1 048 576 19 Stellen 31 Stellen 91 Stellen 302 Stellen
n! 19 Stellen 82 Stellen 161 Stellen 623 Stellen unvorstellbar
nn 27 Stellen 107 Stellen 201 Stellen 744 Stellen Unvorstellbar
11.04.23 Kapitel 1 10
Laufzeitvergleiche:
11.04.23 Kapitel 1 11
P vs. NP
P: Klasse aller Entscheidungsprobleme (Anworten sind aus {Ja, Nein}), die in polynomieller Zeit entschieden werden können.
Beispiele: Sortiertheit einer Folge, Auswer-tung eines Schaltkreises, Wortproblem für kontextfreie Sprachen, Lineare Optimierung,…
11.04.23 Kapitel 1 12
P vs. NP
NP: Klasse aller Entscheidungsprobleme (Anworten sind aus {Ja, Nein}), für die es für Eingaben mit Antwort Ja ein Zertifikat gibt, so dass die Antwort in polynomieller Zeit (in der Eingabegröße) verifiziert werden kann.
Beispiele: Erfüllbarkeit einer Booleschen Formel, 3-Färbung von Graphen, Rucksackproblem,…
P vs. NP
1.1 Beispiele für Probleme in NP:• Clique = {(G,k) | G=(V,E) ist ein Graph, der einen
vollständigen Teilgraphen aus mindestens k Knoten besitzt}
• IS = {(G,k) | G=(V,E) ist ein Graph, in dem es eine Knotenmenge U aus k Knoten gibt, so dass keine zwei Knoten in U durch eine Kante in G verbunden sind}
• Hamilton = {G | G=(V,E) ist ein Graph, der einen Hamilton-Kreis besitzt}(Ein Hamilton-Kreis ist ein Kreis in G, in dem jeder Knoten genau einmal besucht wird.)
11.04.23 Kapitel 1 13
11.04.23 Kapitel 1 14
P vs. NP
Offensichtlich ist P eine Teilmenge von NP.Die 1-Million-Dollar-Frage: Ist P=NP oder nicht?
• Antwort auf diese Frage scheint sehr schwer zu sein.
• Bisher nur Ergebnisse des Typs:“Das kann nicht in polynomieller Zeit gelöst werden, es sei denn, P=NP.”
• Klasse der NP-harten Probleme: sind nicht in P, es sei denn, P=NP.
P vs. NP
Zu Entscheidungsproblemen gibt es häufig entsprechende Optimierungsprobleme.
Beispiele:• Optimierungsvariante zu Clique: finde
vollständigen Teilgraphen maximaler Größe.• Optimierungsvariante zu IS: finde Knotenmenge
maximaler Größe, in der kein Knotenpaar verbunden ist.
Einsicht: Ist das Entscheidungsproblem nicht in P, dann ist auch die Optimierungsvariante nicht in polynomieller Zeit lösbar (und umgekehrt).
11.04.23 Kapitel 1 15
P vs. NP
1.2 Definition:Ein kombinatorisches Optimierungs-problem ist charakterisiert durch vier Komponenten:– D: Menge der Eingaben– S(I) für ein ID: Menge der zur Eingabe I
zulässigen Lösungen– Die Bewertungsfunktion f:S(I) IN– ziel{min, max}
11.04.23 Kapitel 1 16
P vs. NP
• Gesucht: eine zu ID zulässige Lösung opt S(I), so dass
f(opt) = ziel{ f() | S(I)}
• f() ist der Wert der zulässigen Lösung .
• Wir schreiben OPT(I) = f(opt).
Für viele komb. Optimierungsprobleme ist es schwer, OPT(I) exakt zu bestimmen.
11.04.23 Kapitel 1 17
P vs. NP
1.3 Beispiel:(a) Das Traveling Salesperson Problem
(TSP) ist charakterisiert durch:– D={(Kn,c) | Kn ist der vollständige Graph auf n
Knoten, c:E IN sind die Kantengewichte}
– S((Kn,c)) = { C | C=(vi1,vi2
,...,vin,vi1
) ist ein Hamilton-Kreis}
– f(C) = c(vin, vi1
) + j=1n-1 c(vij
, vij+1)
– min
11.04.23 Kapitel 1 18
P vs. NP
1.3 Beispiel:(b) Das Rucksackproblem ist charakterisiert
durch:– D={ (W,vol,p,B) | W={1,...,n}, vol:W IN, B IN,
p:W IN und für alle w W gilt vol(w) ≤ B}W ist das Warenangebot, vol die Zuordnung von Volumina zu den Waren, p die Zuordnung von Werten und B die Kapazität des Rucksacks
– S((W,vol,p,B)) = {A W | wA vol(w) ≤ B}– f(A) = wA pw
– max
11.04.23 Kapitel 1 19
11.04.23 Kapitel 1 20
Übersicht
• P vs. NP• Approximationsalgorithmen• Lastbalancierung• Zentrumswahl• Rucksackproblem
Approximationsalgorithmen
Die NP-Härte eines Entscheidungsproblems legt nahe, dass die Optimierungsvariante keinen effizienten Algorithmus besitzt. Man muss sich also mit Näherungslösungen zufrieden geben.
1.4 Definition: Sei ein kombinatorisches Optimierungsproblem. Ein t(n)-Zeit-Approxi-mationsalgorithmus A berechnet zu Eingabe ID in Zeit t(|I|) eine Ausgabe I
A S(I). Wir schreiben A(I) = f(I
A).
11.04.23 Kapitel 1 21
Approximationsalgorithmen
• Wir wollen natürlich nach t(n)-Zeit-Approxi-mationsalgorithmen suchen, für die – t(n) polynomiell in n ist und– f(I
A) möglichst nah an OPT(I) ist.
Ziele:• Bestimme untere und obere Schranken für
Approximationsgüte des Algorithmus• Bestimme untere Schranken für die erreichbare
Approximationsgüte des Problems• Bestimme Heuristiken, die in der Praxis gut
funktionieren ( Benchmarks)
11.04.23 Kapitel 1 22
11.04.23 Kapitel 1 23
Übersicht
• P vs. NP• Approximationsalgorithmen• Lastbalancierung• Zentrumswahl• Rucksackproblem
11.04.23 Kapitel 1 24
Lastbalancierung
Eingabe: m identische Maschinen, n Jobs. Job i hat Laufzeit ti.
Einschränkungen:• Ein einmal ausgeführter Job muss bis zum Ende auf derselben
Maschine ausgeführt werden.• Jede Maschine kann höchstens einen Job gleichzeitig bearbeiten.
1.5 Definition: Sei J(i) die Teilmenge der Jobs, die Maschine i zugewiesen werden. Dann ist Li = jJ(i) tj die Last der Maschine i.
1.6 Definition: Der Makespan L ist die maximale Last einer Maschine, d.h. L = maxi Li
Lastbalancierung: finde Zuweisung, die Makespan minimiert
11.04.23 Kapitel 1 25
Lastbalancierung: List Scheduling
List-Scheduling Algorithmus:• Betrachte n Jobs in einer festen Reihenfolge• Weise Job j der Maschine mit z.Zt. geringster Last zu
List-Scheduling(m, n, (t1,…,tn)):for i:=1 to m do Li := 0; J(i):=;for j:=1 to n do i:=argmink Lk // wähle Maschine mit kleinster Last J(i):=J(i) {j} // weise dieser Job i zu Li:=Li + tjreturn (J(1),…,J(m))
Laufzeit: O(n log m) mit Priority Queue
11.04.23 Kapitel 1 26
Lastbalancierung: List Scheduling
1.7 Satz (Graham): List Scheduling ist 2-approximativ (d.h. für alle Eingaben I ist List-Scheduling(I) 2OPT(I) ).
vergleiche Güte des Algorithmus mit optimalem Makespan L*
1.8 Lemma: L* ≥ maxj tj
Beweis: Eine Maschine muss den zeitintensivsten Job bearbeiten.
1.9 Lemma: L* ≥ (1/m) j tj
Beweis:• Die Gesamtlast ist j tj
• Eine der m Maschinen muss mindestens 1/m der Gesamtlast bekommen.
11.04.23 Kapitel 1 27
Lastbalancierung: List Scheduling
1.10 Satz: List Scheduling ist 2-approximativ.Beweis: • Betrache Maschine i mit höchster Last Li.• Sei j der letzte Job in Maschine i.• Da Job j Maschine i zugeordnet wurde, hatte i vorher die
kleinste Last. Es gilt also Li – tj ≤ Lk für alle k.
vor j
j
nach j
Li - tj Li
11.04.23 Kapitel 1 28
Lastbalancierung: List Scheduling
Beweis (Forsetzung):
• Es gilt: Li-tj ≤ Lk für alle k{1,…,m}
• Daraus folgt: Li – tj ≤ (1/m) 1km Lk
= (1/m) 1kn tk
≤ L* (Lemma 1.9)
• Also gilt wegen Lemma 1.8: Li = (Li-tj) + tj ≤ 2L*
11.04.23 Kapitel 1 29
Lastbalancierung: List Scheduling
Ist die Analyse scharf? Ja!
Beispiel: m Maschinen, m(m-1) Jobs der Länge 1, ein Job der Länge m
m=10
Makespan = 19
11.04.23 Kapitel 1 30
Lastbalancierung: List Scheduling
Ist die Analyse scharf? Ja!
Beispiel: m Maschinen, m(m-1) Jobs der Länge 1, ein Job der Länge m
m=10
Optimaler Makespan = 10
11.04.23 Kapitel 1 31
Lastbalancierung: LPT Regel
Longest Processing Time (LPT): Sortiere die n Jobs in absteigender Reihenfolge und führe dann den List Scheduling Algorithmus aus.
LPT-List-Scheduling(m, n, (t1,…,tn)):sortiere Jobs, so dass t1≥t2≥…≥tn
for i:=1 to m do Li := 0; J(i):=;for j:=1 to n do i:=argmink Lk
J(i):=J(i) {j} Li:=Li + tj
return (J(1),…,J(m))
11.04.23 Kapitel 1 32
Lastbalancierung: LPT Regel
Beobachtung: Wenn es höchstens m Jobs gibt, dann ist List Scheduling optimal.
Beweis: Weise jedem Job eigene Maschine zu.
1.11 Lemma: Falls es mehr als m Jobs gibt, dann ist L*≥2tm+1.
Beweis:• Betrachte die ersten m+1 Jobs t1,…,tm+1
• Da die ti’s absteigend sortiert sind, benötigt jeder dieser Jobs mindestens tm+1 Zeit.
• Bei m+1 Jobs muss eine Maschine mindestens zwei Jobs erhalten.
11.04.23 Kapitel 1 33
Lastbalancierung: LPT Regel
1.12 Satz: Die LPT Regel liefert eine 3/2-Approximation.Beweis:Falls die Maschine i mit größter Last nur einen Job hat, ist LPT offensichtlich optimal. Sonst gilt für den letzten Job j auf Maschine i, dass j m+1 und damit nach Lemma 1.11:
Li = (Li – tj) + tj
L* + (1/2)L* (3/2)L*
Ist 3/2 scharf? Nein!
11.04.23 Kapitel 1 34
Lastbalancierung: LPT Regel
1.13 Satz: (Graham): Die LPT Regel ist eine 4/3-Approximation.
Beweis: aufwändig
Satz 1.13 ist im Wesentlichen scharf.Beispiel: m Maschinen, n=2m+1 Jobs: jeweils 2
Jobs der Länge m+1,m+2,…,2m und ein Job der Länge m
Vergleich zu OPT: Übung.
11.04.23 Kapitel 1 35
Übersicht
• P vs. NP• Approximationsalgorithmen• Lastbalancierung• Zentrumswahl• Rucksackproblem
11.04.23 Kapitel 1 36
Zentrumswahl-Problem
Eingabe: Menge von n Orten s1,…,sn und eine Zahl kIN.
Zentrumswahl-Problem: Wähle k Zentren C, so dass die maximale Distanz eines Ortes zum nächsten Zentrum minimal ist.
k=4
: Zentrum
11.04.23 Kapitel 1 37
Zentrumswahl-Problem
Eingabe: Menge von n Orten s1,…,sn und eine Zahl kIN.
Zentrumswahl-Problem: Wähle k Zentren C, so dass die maximale Distanz eines Ortes zum nächsten Zentrum minimal ist.
Notation:• dist(x,y) = Distanz zwischen x und y• dist(si, C) = mincC dist(si,c) = Distanz von si zum nächsten Zentrum• r(C) = maxi dist(si, C) = kleinster Überdeckungsradius
Wir nehmen an, dist ist eine Metrik, d.h.• dist(x,x) = 0 (Identität)• dist(x,y) = dist(y,x) (Symmetrie)• dist(x,y) dist(x,z) + dist(z,y) (Dreiecksungleichung)
11.04.23 Kapitel 1 38
Zentrumswahl-Problem
Beispiel: jeder Ort ist ein Punkt im 2-dimensiona-len Euklidischen Raum, dist(x,y) = Euklidische Distanz
k=4
: Zentrum
11.04.23 Kapitel 1 39
Zentrumswahl: Greedy Algorithmus
Greedy Algorithmus: Setze das erste Zentrum an der bestmöglichen Stelle für ein einzelnes Zentrum, füge dann Zentren hinzu, um den Überdeckungsradius möglichst stark zu verkleinern.
Kann beliebig schlecht werden!!
Beispiel: k=2
erstes Zentrum
11.04.23 Kapitel 1 40
Zentrumswahl: Greedy Algorithmus
Greedy Algorithmus: wähle wiederholt als näch-stes Zentrum den Ort si mit maximaler Distanz zu allen bisherigen Zentren
Greedy-Center-Selection(k, n, (s1,s2,…,sn)):C:=;wiederhole k-mal wähle Ort si mit maximalem dist(si,C) C:=C {si}return C
Bemerkung: erstes Zentrum ist beliebiger Ort si
11.04.23 Kapitel 1 41
Zentrumswahl: Greedy Algorithmus
Bemerkung: Zentren in C sind mindestens r(C) entfernt voneinanderBeweis: r(C) sinkt monoton, jeweils minimale paarweise Entfernung
1.14 Satz: Sei C* die optimale Wahl der Zentren. Dann ist r(C) ≤ 2r(C*).Beweis (durch Widerspruch):• Angenommen, r(C*) < r(C)/2.• Betrachte die Kreise mit Radius r(C)/2 um jedes ci C.• Es muss genau ein cC* im Kreis von jedem ci geben (siehe
Bemerkung und Annahme); wir nennen dieses Zentrum c*i
• Betrachte einen beliebigen Ort s und sei c*i sein nächstes Zentrum in C*. Es gilt:
dist(s,C) dist(s,ci) dist(s,c*i) + dist(c*i,ci) 2r(C*)• Also ist r(C) 2r(C*), ein Widerspruch zur Annahme
11.04.23 Kapitel 1 42
Zentrumswahl
Wir wissen: Der Greedy Algorithmus ergibt eine 2-Approximation.
Gibt es auch Polynomialzeitalgorithmen mit Approximationsgüte 3/2? Oder 4/3?
1.15 Satz: Sofern nicht P=NP ist, gibt es keinen Polynomialzeitalgorithmus mit Approximationsgüte < 2 für die Zentrums-wahl (für k>2).
11.04.23 Kapitel 1 43
Übersicht
• P vs. NP• Approximationsalgorithmen• Lastbalancierung• Zentrumswahl• Rucksackproblem
11.04.23 Kapitel 1 44
Rucksack-Problem
Rucksack-Problem:• Gegeben sind n Objekte und ein Rucksack• Objekt i hat Wert pi>0 und wiegt voli>0• Der Rucksack kann max. Gesamtgewicht B tragen.Ziel: fülle Rucksack mit Objekten mit max. Gesamtwert
Beispiel: B=11
{3,4} hat Wert 40
Objekt Wert Gewicht
1 1 1
2 6 2
3 18 5
4 22 6
5 28 7
11.04.23 Kapitel 1 45
RP: Greedy Verfahren
Greedy Strategie:
• Berechne Profitdichten d1=p1/vol1,.., dn=pn/voln• Sortiere Objekte nach Profitdichten• Angefangen von dem Objekt mit höchster
Profitdichte, füge Objekte zu Rucksack hinzu, bis kein Platz mehr da
Problem: Greedy Strategie kann weit vom Optimum entfernt liegen
11.04.23 Kapitel 1 46
RP: Greedy Verfahren
Beispiel: zwei Objekte mit p1=1 und p2=B-1 und vol1=1 und vol2=B, Rucksackkapazität ist B
Greedy-Methode: berechnet d1=1 und d2 = 1-1/B und wird nur Objekt 1 in Rucksack packen, da Objekt 2 nicht mehr passt
Optimale Lösung: packe Objekt 2 in Ruck-sack (viel besser da Wert B-1 statt 1)
11.04.23 Kapitel 1 47
RP: Greedy Verfahren
Verbesserte Greedy-Methode:
• Seien die Objekte 1 bis n absteigend nach Profitdichte sortiert
• Bestimme maximale Objektmenge {1,…,i} wie bisher mit ji volj B
• Gib entweder {1,…,i} oder {i+1} aus, je nachdem, welche Menge den maximalen Wert hat
11.04.23 Kapitel 1 48
RP: Greedy Verfahren
1.16 Satz: Die Lösung der verbesserten Greedy-Methode ist höchstens einen Faktor 2 von der optimalen Lösung entfernt.
Beweis:• Wenn beliebige Bruchteile der Objekte gewählt
werden könnten, wäre die optimale Lösung {1,…,i+1}, wobei von Objekt i+1 nur der Bruchteil genommen wird, der noch in den Rucksack passt.
• Für den optimalen Wert OPT gilt demnach:OPT ji+1 volj.
• Also ist max{ji volj, voli+1} OPT/2
11.04.23 Kapitel 1 49
Fragen?