09. Übung zu Algorithmen I 12. Juli 2017 - crypto.iti.kit.edu · [M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization yb a colony of cooperating agents, IEEE ransactionsT

09. Übung zu Algorithmen I12. Juli 2017

Björn Kaidel

[email protected]

mit Folien von Lukas Barth

1 / 67

[email protected]

Roadmap

I Ausblick: Was sind schwierige Probleme?

I Travelling Salesman Problem - Reprise

I ein ILPI ein Algorithmus mit Ameisen

I Vertex Cover

I ein Annäherungsversuch

2 / 67

Schwierige Probleme

Bisher:I Identi�ziere Problem...I ... und löse es mit einem e�zienten Algorithmus

Frage: Ist das immer möglich?

Antwort: Wissen wir nicht!I KomplexitätstheorieI Klassi�ziert Probleme in KlassenI Klassen machen Aussagen über benötigten Speicherplatz,

Laufzeit, Lösbarkeit durch randomisierte Algorithmen, ...

3 / 67

Schwierige Probleme

Bisher:I Identi�ziere Problem...I ... und löse es mit einem e�zienten Algorithmus

Frage: Ist das immer möglich?

Antwort: Wissen wir nicht!I KomplexitätstheorieI Klassi�ziert Probleme in KlassenI Klassen machen Aussagen über benötigten Speicherplatz,

Laufzeit, Lösbarkeit durch randomisierte Algorithmen, ...

4 / 67

Schwierige Probleme

Eine Menge ProblemeIntuitiv: NP ist die Menge aller Probleme, zu denen einegegebene Lösung e�zient überprüft werden kannAchtung: es kann schwer sein eine solche Lösung zu �nden

Schwierige ProblemeIntuitiv: Ein Problem ist NP-schwierig, wenn esgenausoschwierig wie das schwierigste Problem in NP ist

Einfache ProblemeIntuitiv: P ist die Menge aller Probleme, die in Polynomialzeitlösbar sind.

5 / 67

Schwierige Probleme

Eine Menge ProblemeIntuitiv: NP ist die Menge aller Probleme, zu denen einegegebene Lösung e�zient überprüft werden kannAchtung: es kann schwer sein eine solche Lösung zu �nden

Schwierige ProblemeIntuitiv: Ein Problem ist NP-schwierig, wenn esgenausoschwierig wie das schwierigste Problem in NP ist

Einfache ProblemeIntuitiv: P ist die Menge aller Probleme, die in Polynomialzeitlösbar sind.

6 / 67

Schwierige Probleme

Wie schwierig sind die schwierigsten Probleme? Sind siee�zient lösbar? Was bedeutet hier e�zient?

I hier: �e�zient�4= existiert ein Polynomialzeit-Algorithmus

I Das ist die berühmte P?= NP-Frage!

I groÿe ungelöste Frage der Informatik!I Dafür gibt es gute Gründe!

I viele vermuten die Antwort ist neinI jedes Jahr einige �Beweise� - für beide RichtungenI NP-schwierige Probleme nach heutigem Forschungsstand

also nicht e�zient lösbar

Wie löst man solche Probleme trotzdem möglichst e�zient?I ApproximationI Heuristiken

7 / 67

Schwierige Probleme








8 / 67

Schwierige Probleme








9 / 67

Erinnerung: Lineare Programme

Ein lineares Programm mit n Variablen und m Constraints (NB)wird durch das folgende Minimierungs-/Maximierungsproblemde�niert:

I Kostenfunktion f (x) = c · xc ist der Kostenvektor

I m Constraints der Form ai · x ./i bi mit ./i∈ {≤,≥,=},ai ∈ Rn. Wir erhalten:

L = {x ∈ Rn : ∀j ∈ 1..n : xj ≥ 0 ∧ ∀i ∈ 1..m : ai · x ./i bi} .

10 / 67

LP graphisch

x2

x1

opt

11 / 67

LP graphisch

x2

x1

opt

12 / 67

LP graphisch

x2

x1

opt

13 / 67

LP graphisch

x2

x1

opt

14 / 67

LP graphisch

x2

x1

opt

15 / 67

LP graphisch

x2

x1

opt

16 / 67

LP graphischInteger LP

x2

x1

opt

17 / 67


x2

x1

opt

18 / 67


x2

x1

opt

19 / 67

(I)LP: Komplexität

I LPs können e�zient gelöst werdenI ILPs dagegen nicht

I Das Problem ist sogar in NP-schwierig!

I Approximation: Löse ILP als LP und �runde �dasEndergebnis

20 / 67

Erinnerung: Travelling Salesman Problem

I Gegeben ungerichteter Graph G = (V ,E ), c : E → RI Gesucht kürzester Kreis, der alle Knoten besuchtI NP-schweres Problem

21 / 67

Ein ILP für TSP

I Städte: 1, 2, . . . , nI Distanzen: d{i ,j}:= c({i , j})

Variablenx{i ,j} = 1, wenn die Tour durch Kante {i , j} geht,

= 0 sonst

22 / 67

Ein ILP für TSP

Zielfunktionminimiere ∑

i ,j : i 6=j

x{i ,j} · d{i ,j}

I x{i ,j} = 1 nur für Kanten, die Teil der Tour sind

⇒ die Zielfunktion ist gerade die Länge der Tour!

23 / 67

Ein ILP für TSP

Bedingung I - TourFür alle i ∈ V gelte: ∑

j : i 6=j

x{i ,j} = 2

I jeder Knoten muss durch genau eine Kante betretenwerden und durch genau eine Kante verlassen werden

24 / 67

Ein ILP für TSP

Frage: Was fehlt noch?

Abbildung: Von User:Sdo - self-made using x�g, CC BY-SA 2.5,https://commons.wikimedia.org/w/index.php?curid=718415

Bedingung II - Zusammenhängende TourFür alle S ⊆ V gelte: ∑

i∈S ,j /∈S

x{i ,j} ≥ 2

25 / 67

Ein ILP für TSP

Frage: Was fehlt noch?

Abbildung: Von User:Sdo - self-made using x�g, CC BY-SA 2.5,https://commons.wikimedia.org/w/index.php?curid=718415

Bedingung II - Zusammenhängende TourFür alle S ⊆ V gelte: ∑

i∈S ,j /∈S

x{i ,j} ≥ 2

26 / 67

Heuristiken

HeuristikI altgr. heurísko: �ich �nde�I in begrenzter Zeit gute Lösungen zu schwierigen

Problemen berechnenI ... ohne Garantien!

MetaheuristikI eine Heuristik für alle ProblemeI ... eigentlich eher eine Familie

27 / 67

Ameisenalgorithmen

I Vorbild: AmeisenstraÿenI Ameisen versprühen

Pheromone. . .I . . . und folgen diesen dannI selbstverstärkender E�ekt!

Abbildung: Ameisenstraÿe. c©MehmetKaratay

28 / 67

Ameisenalgorithmen für das TSP

Jede Ameise. . .I . . . startet irgendwoI . . . läuft immer zu einer zufälligen (neuen) Nachbarstadt

I abhängig davon, wie viele Pheromone auf der Kante sind!

I . . . legt einen Pheromon-Pfad, wenn sie alle Städtegesehen hat

29 / 67

Ameisenalgorithmen für das TSP

I auf der schnellsten Tour wird mehr Pheromon abgelegt

30 / 67

Ameisenalgorithmen für das TSPErgebnisse

[M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization by a colony of cooperating agents,IEEE Transactions on Systems, Man, and Cybernetics�Part B , volume 26, numéro 1, pages 29-41,

1996.]

Experimentelle ResultateI sehr gute Lösungsqualität (meist ≥ 95%)I sehr schnellI anwendbar auf viele Probleme (mehrere im Paper)

31 / 67

Vertex Cover

Gegeben ungerichteter Graph G = (V ,E )

Gesucht minimale Menge S ⊆ V , sodass jede Kantemindestens einen Endpunkt in S hat:

∀{u, v} ∈ E : {u, v} ∩ S 6= ∅

⇒ NP-schwer!

32 / 67

Approximation

Erinnerung: HeuristikI e�zient gute Lösungen zu schwierigen Problemen

berechnenI ... ohne Garantien!

ApproximationI in begrenzter Zeit gute Lösungen zu schwierigen

Problemen berechnenI . . . die nicht mehr als einen (konstanten!) Faktor k

schlechter sind als die Optimallösung

⇒ Algorithmen für Steinerbaum- und TSP-Problem aus letzterÜbung waren Approximationen!

33 / 67

Eine Approximation für Vertex Cover

Function Approx-Vertex-Cover(G = (V ,E ) : Graph)C = ∅while E 6= ∅ do

e = pickRandom(E ) // e = {e1, e2}C = C ∪ e∀e ′ ∈ E , e ′ ∩ e 6= ∅ : E = E \ e ′

return C

34 / 67

Eine Approximation für Vertex CoverKorrektheit

Frage: Warum sind nachher alle Kanten abgedeckt?

I es werden nur abgedeckte Kanten entferntI es wird immer ≥ eine Kante entfernt!

I wichtig: immer zeigen, dass der Algorithmus terminiert!

⇒ alle Kanten abgedeckt

35 / 67

Eine Approximation für Vertex CoverBeweis: 2-Approximation

I sei A Menge der in der Schleife zufällig gewählten KantenI |C | = 2 · |A|I keine zwei Kanten in A haben einen Knoten gemeinsam

I sei C eine Optimallösung⇒ für jede Kante in A ist mindestens ein Knoten in C⇒ |C | ≥ |A|⇒ |C | ≤ 2 · |C |

36 / 67

Eine Approximation für Vertex CoverBeweis: 2-Approximation

I sei A Menge der in der Schleife zufällig gewählten KantenI |C | = 2 · |A|I keine zwei Kanten in A haben einen Knoten gemeinsam

I sei C eine Optimallösung⇒ für jede Kante in A ist mindestens ein Knoten in C⇒ |C | ≥ |A|⇒ |C | ≤ 2 · |C |

37 / 67

Metaheuristiken und Nachbarschaften

Wie kann man Metaheuristiken für Vertex Cover verwenden?

I Idee: de�niere eine �Nachbarschaft� auf den zulässigenLösungen

I Wie sieht das bei Vertex Cover aus?I Lösung: eine Menge von KnotenI Nachbarlösungen: jede Menge, die sich nur um einen

Knoten unterscheidetI natürlich nicht unbedingt minimal!

38 / 67

NachbarschaftsmetaheuristikenLokale Suche

Lokale SucheI gehe immer zur besten Lösung in der Nachbarschaft der

aktuellen Lösung

x

f(x)

39 / 67



aktuellen Lösung

x

f(x)

40 / 67



aktuellen Lösung

x

f(x)

⇒ lokale Optima sind ein Problem

41 / 67

NachbarschaftsmetaheuristikenTabu-Suche

Tabu-SucheI gehe immer zur besten Lösung in der Nachbarschaft der

aktuellen LösungI . . . auÿer den letzten k Lösungen

x

f(x)

I läuft aus lokalen Optima herausI wenn die Tabu-Liste gut gewählt ist

42 / 67




x

f(x)


43 / 67




x

f(x)


44 / 67

Lokale Suche für Vertex Cover

I lokales Optimum, aber nicht global optimal!

45 / 67



46 / 67



47 / 67



48 / 67



49 / 67

Tabu-Suche für Vertex Cover

I Gröÿe der Tabu-Liste: 1I derzeit tabu: ∅

I globales Optimum!I Sind gröÿere Tabu-Listen zwangsläu�g besser...?

50 / 67




51 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 2, 3, 4, 5, 6}


52 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 3, 4, 5, 6}


53 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 3, 4, 6}


54 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 2, 3, 4, 6}


55 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 2, 3, 4}


56 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 2, 3, 4}I globales Optimum!

I Sind gröÿere Tabu-Listen zwangsläu�g besser...?

57 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 2, 3, 4}I globales Optimum!I Sind gröÿere Tabu-Listen zwangsläu�g besser...?

58 / 67


I Gröÿe der Tabu-Liste: 1I derzeit tabu: {1, 2, 3, 4}I globales Optimum!I Sind gröÿere Tabu-Listen zwangsläu�g besser...? Nein!

59 / 67



I Können nicht weitermachen!I Geben daher sehr schlechte Lösung aus!

60 / 67




61 / 67


I Gröÿe der Tabu-Liste: 3I derzeit tabu: {1, 2, 3, 4, 5, 6}


62 / 67


I Gröÿe der Tabu-Liste: 3I derzeit tabu: {1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 6}


63 / 67


I Gröÿe der Tabu-Liste: 3I derzeit tabu: {1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 6}, {1, 3, 4, 6}I Können nicht weitermachen!I Geben daher sehr schlechte Lösung aus!

64 / 67

NachbarschaftsmetaheuristikenSimulated Annealing

Stahl Anlassen (engl. Annealing)I stark erhitzen

I in erhitztem Stahl: Verbindungen ändern sich rapide

I langsam, kontrolliert abkühlenI es bilden sich starke Kristallverbindungen

Simulated AnnealingI Idee: Verschlechterungen zulassenI Aber: mit der Zeit (sinkender Temperatur. . . ) weniger

wahrscheinlich

65 / 67

NachbarschaftsmetaheuristikenSimulated Annealing

?P = e−

f(x′)−f(x)T

x

f(x)

I Idee: erst recht global suchen, dann immer lokalerI viele einzustellende ParameterI Nachbarschaft ein bisschen komplizierter. . .

66 / 67

Zusammenfassung

ProblemeI es gibt �besonders schwierige� ProblemeI Travelling Salesman ProblemI Vertex Cover

I Approximation

OptimierungstechnikenI (I)LPsI AmeisenalgorithmenI Lokale Suhe, Tabu-Suche, Simulated Annealing

67 / 67

Documents

09. Übung zu Algorithmen I 12. Juli 2017 - crypto.iti.kit.edu · [M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization yb a colony of cooperating agents, IEEE ransactionsT