10.11.2013Kapitel 11 Methoden des Algorithmenentwurfs Kapitel 1: Einführung Christian Scheideler SS...

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: scheideler@upb.de

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?