Embed Size (px)
Citation preview
Approximationsalgorithmen auf metrischen Instanzen
Betriebswirtschaftliche Optimierung
Joachim Schauer
Institut fur Statistik und OR
Uni Graz
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
1 Approximationsalgorithmen auf metrischen Instanzen
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Minimum Spanning Tree
Definition (Spannbaum)
Ein Spannbaum in einem Graphen G = (V ,E ) ist ein kreisfreierTeilgraph T = (V ,E ′) mit n − 1 Kanten (|E ′| = |V | − 1).
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Minimum Spanning Tree
Definition (Spannbaum)
Ein Spannbaum in einem Graphen G = (V ,E ) ist ein kreisfreierTeilgraph T = (V ,E ′) mit n − 1 Kanten (|E ′| = |V | − 1).
Definition (Minimum Spanning Tree)
Ein minimaler Spannbaum in einem gewichteten GraphenG = (V ,E ) mit Kantengewichten we ist ein SpannbaumT = (V ,E ′) mit minimaler Kantengewichtssummew(T ′) :=
∑e∈E ′ we .
Anwendungen
Zentrales Problem der Netzwerkplanung: n Orte werdenmoglichst kostengunstig an einen Versorger angeschlossen.
Basis fur Klasse von Approximationsalgorithmen fur TSP
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Minimum Spanning Tree
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
MST Algorithmus
Definition (Inzident / Adjazent)
Zwei Kanten sind zueinander inzident, falls sie einen gemeinsamenKnoten als Endpunkt haben. Zwei Knoten u und v sind adjazentfalls (u, v) ∈ E . Eine Kante und ein Knoten sind zueinanderinzident, falls der Knoten Endpunkt der Kante ist.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
MST Algorithmus
Definition (Inzident / Adjazent)
Zwei Kanten sind zueinander inzident, falls sie einen gemeinsamenKnoten als Endpunkt haben. Zwei Knoten u und v sind adjazentfalls (u, v) ∈ E . Eine Kante und ein Knoten sind zueinanderinzident, falls der Knoten Endpunkt der Kante ist.
Algorithmus von Prim
Starte mit T = ∅. Wahle Kante e mit minimalem Gewicht in G .
a) T = T ∪ e
b) Wahle jene Kante e′ in G die inzident zu einer Kante aus T istund folgende Punkte erfullt:
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
MST Algorithmus
Definition (Inzident / Adjazent)
Zwei Kanten sind zueinander inzident, falls sie einen gemeinsamenKnoten als Endpunkt haben. Zwei Knoten u und v sind adjazentfalls (u, v) ∈ E . Eine Kante und ein Knoten sind zueinanderinzident, falls der Knoten Endpunkt der Kante ist.
Algorithmus von Prim
Starte mit T = ∅. Wahle Kante e mit minimalem Gewicht in G .
a) T = T ∪ e
b) Wahle jene Kante e′ in G die inzident zu einer Kante aus T istund folgende Punkte erfullt:
1) T ∪ e ′ ist kreisfrei.2) Unter allen Kanten die das erfullen, hat e ′ minimales Gewicht.
c) Iteriere Punkt a) mit e′ in der Rolle von e.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Prim Beispiel
b
b
b
b
b
b
b
b
b
b
3
8
3
214
11
12
11
11
1
7
11
5
3
1
7
11
4
5
3
6
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Algorithmus von Prim
Beweis durch Widerspruch
Sei T der Baum vom Algorithmus von Prim und T ∗ ein MST mitw(T ∗) < w(T ).
Sei Tk der Teilbaum der im k-ten Schritt von Prims Algorithmusentsteht. Wahle k ′ als minimalen Index sodass Tk′ * T ∗. Dasbedeutet, dass die Kante ek′ = (a, b), die im k-ten Schritthinzugefugt wird, nicht in T ∗ enthalten ist. O.B.D.A. sei a jenerKnoten, der in Tk′−1 enthalten ist. Da T ∗ ein Baum ist, existiertein eindeutiger Pfad P in T ∗ von a nach b und dieser enthalt eineKante f , die Tk′−1 mit dem Rest verbindet.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Beweis durch Widerspruch
Somit hatte Prim zur Iteration k ′ − 1 die Moglichkeit gehabt f zuwahlen. Daraus folgt, dass w(f ) ≥ w(ek′) ist.
Bilde einen Baum T ′ = ek′ ∪ (T ∗ \ f ).Somit ist w(T ′) minimal da:
w(T ′) = w(T ∗) + w(ek′)− w(f )
Wiederhole das Argument mit T ′. �
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Metrisches TSP
MST-Heuristik
Sei Tmin ein MST in G = (V ,E ).
Idee: Verwende Tmin um eine TSP Losung zu konstruieren, dieeiner Gutegarantie von 1
2genugt.
Sei O∗ der optimale Zielfunktionswert einer TSP-Instanz in G mitTour T . Es gilt:
O∗ ≥ w(Tmin)
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Metrisches TSP
MST-Heuristik
Sei Tmin ein MST in G = (V ,E ).
Idee: Verwende Tmin um eine TSP Losung zu konstruieren, dieeiner Gutegarantie von 1
2genugt.
Sei O∗ der optimale Zielfunktionswert einer TSP-Instanz in G mitTour T . Es gilt:
O∗ ≥ w(Tmin)
Beweis:
Fur jede Kante e in der optimalen Tour T gilt, T \ e ist einSpannbaum.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Metrisches TSP
Definition (Eulerscher Kreis und Graph)
Ein Eulerscher Kreis in G = (V ,E ) ist ein Kreis der jede Kante ausE genau einmal durchlauft. Ein Eulerscher Graph ist ein Graph mitEulerschem Kreis. Graphen sind Eulersch genau dann wenn jederKnoten eine gerade Anzahl an Nachbarn hat.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Metrisches TSP
Definition (Eulerscher Kreis und Graph)
Ein Eulerscher Kreis in G = (V ,E ) ist ein Kreis der jede Kante ausE genau einmal durchlauft. Ein Eulerscher Graph ist ein Graph mitEulerschem Kreis. Graphen sind Eulersch genau dann wenn jederKnoten eine gerade Anzahl an Nachbarn hat.
MST-Heuristik
a) Konstruiere einen MST Tmin.
b) Verdopple Kanten von Tmin und bilde Eulerschen Graphen T .
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Metrisches TSP
Definition (Eulerscher Kreis und Graph)
Ein Eulerscher Kreis in G = (V ,E ) ist ein Kreis der jede Kante ausE genau einmal durchlauft. Ein Eulerscher Graph ist ein Graph mitEulerschem Kreis. Graphen sind Eulersch genau dann wenn jederKnoten eine gerade Anzahl an Nachbarn hat.
MST-Heuristik
a) Konstruiere einen MST Tmin.
b) Verdopple Kanten von Tmin und bilde Eulerschen Graphen T .
c) Starte bei beliebigen Knoten von T und folge den Kanten imSinne eines Eulerschen Kreises konstruiere Tour TMST mitTMST = ∅ zu Beginn.
Markiere einen Knoten v , der zum ersten Mal besucht wird alsbesucht und setzte TMST = TMST ◦ v .
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Beispiel
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
12-Approximation
12-Approximation auf metrischen Instanzen
Behauptung: w(TMST ) ≤ 2 · w(Tmin)
Beweis
Sei (vi , vj) eine Kante aus TMST und P der zugehorige Pfade in T
zwischen vi und vj . Die Dreiecksungleichung liefert
d(vi , vj ) ≤∑
e∈P
d(e)
Der Algorithmus durchlauft aber jede Kante von T genau 2 malund jede Kante aus TMST ist einem eindeutigen (bezuglich derverdoppelten Kanten) Pfad aus P zugeordnet. �
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Christofides Heuristik
Definition (Knotengrad deg(v))
Der Grad eines Knotens v in G = (V ,E ) ist definiert als:
deg(v) := |NG (v)|
Definition (k-regular)
Ein Graph G = (V ,E ) heißt k-regular, falls deg(v) = k fur allev ∈ V .
Definition (Matching)
Ein Matching in G = (V ,E ) ist ein 1-regularer Subgraph G ′ von G .
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Beispiel Matching
bb
b
bb
b
b
b
b
b
b
bb
b
b
bb
b
b
b
b
b
b
b
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Christofides Heuristik
Fakten zum Matching
Minimum Weight Matching in bipartiten Graphen: UngarischeMethode O(n3) (H.W. Kuhn, D. Konig, J. Egervary[50er Jahre])
Minimum Weight Matching in allgemeinen Graphen: BlossomAlgorithmus O(n4) in Paths, Trees and Flowers by JackEdmonds [1965]
Minimum Weight Matching in allgemeinen Graphen:Schnellster Algorithmus O(m
√n) von S. Micali and V.V.
Vazirani [1980]
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Christofides Heuristik
Die 23-Approximation von Christofides
1) Finde einen MST Tmin in G = (V ,E ).
2) Bestimme ein Minimum Weight Matching M in G zwischenallen Knoten die in Tmin ungeraden Grad haben - deren Anzahlist gerade also ist M perfekt.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Christofides Heuristik
Die 23-Approximation von Christofides
1) Finde einen MST Tmin in G = (V ,E ).
2) Bestimme ein Minimum Weight Matching M in G zwischenallen Knoten die in Tmin ungeraden Grad haben - deren Anzahlist gerade also ist M perfekt.
3) Setzte T ′ = Tmin ∪M und nimm gegebenenfalls doppelteKanten (T ′ ist ein Eulerscher Graph).
4) Konstruiere eine Eulerschen Kreis ET ′ in T ′.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Christofides Heuristik
Die 23-Approximation von Christofides
1) Finde einen MST Tmin in G = (V ,E ).
2) Bestimme ein Minimum Weight Matching M in G zwischenallen Knoten die in Tmin ungeraden Grad haben - deren Anzahlist gerade also ist M perfekt.
3) Setzte T ′ = Tmin ∪M und nimm gegebenenfalls doppelteKanten (T ′ ist ein Eulerscher Graph).
4) Konstruiere eine Eulerschen Kreis ET ′ in T ′.
5) Konstruiere eine TSP Tour TC indem ausgehend von einembeliebigen Knoten ET ′ abgefahren wird. Wird ein Knoten v
zum ersten Mal besucht setzte TC = TC ◦ v .
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Beispiel Christofides
b
b
b
b
b
b
b
bb
b
b
b
b
b
b
b
b
bb
b
b
b
b
b
b
b
b
bb
b
MST Tmin Matching M in G
T ′ = Tmin ∪M
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Beispiel Christofides
b
b
b
b
b
b
b
bb
b
1
2
3
4
5
6
7
8
9
10b
b
b
b
b
b
b
bb
b
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
23-Approximation
23-Approximation auf metrischen Instanzen
Behauptung: w(TC ) ≤ 32O∗
Beweis
Wir wissen: :
w(TC ) ≤ w(Tmin) + w(M) (Dreiecksungleichung)
O∗ ≥ w(Tmin)
Es bleibt zu zeigen, dass
O∗ ≥ 2w(M)
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
23-Approximation
23-Approximation auf metrischen Instanzen
Behauptung: w(TC ) ≤ 32O∗
Beweis
Wir wissen: :
w(TC ) ≤ w(Tmin) + w(M) (Dreiecksungleichung)
O∗ ≥ w(Tmin)
Es bleibt zu zeigen, dass
O∗ ≥ 2w(M)
Sei nun TOPT eine optimale Tour in G mit w(TOPT ) = O∗ und seiU die Menge aller Knoten fur die im Christofides Algorithmusunter Punkt 2) ein Matching bestimmt wurde.
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
23-Approximation
Beweis
Sortiere die Knoten in U in der Reihenfolge wie sie von TOPT
durchlaufen werden als u1, u2 . . . u2k Betrachte nun eine Tour TU
die nur durch U lauft und wie folgt konstruiert wird: entferne ausTOPT alle Kanten, die inzident zu Knoten aus V \ U sind und fugedie Kanten zwischen den verbleibenden Pfaden in der Reihenfolgewie die Tour durchlaufen wird hinzu. Wir wissen aufgrund derDreiecksungleichung :
w(TU) ≤ w(TOPT )
Betrachte die MatchingsM1 = {(u1, u2), (u3, u4), . . . , (u2k−1, u2k)} undM2 = {(u2, u3), (u4, u5), . . . , (u2k , u1)}. Wir wissen TU = M1 ∪M2
und w(Mi ) ≥ w(M) und somit w(TU) ≥ 2w(M). �
Joachim Schauer Betriebswirtschaftliche Optimierung
Approximationsalgorithmen auf metrischen Instanzen
Beispiel
b
b
b
b
b
b
b
b
b
b
TOPT mit U
b
b
b
b
b
b
TU
b
b
b
b
b
b
M1 und M2
Joachim Schauer Betriebswirtschaftliche Optimierung
