prev up inhalt next


Näherungslösungen für das TSP

Sei P ein Minimierungsproblem und A ein Näherungsalgorithmus für dieses Problem. Sei I eine Instanz (z.B. Anzahl von Städten bei TSP). Sei Apr(I) die (Näherungs-) Lösung, die A für Instanz I findet, Opt(I) die optimale Lösung.

Gilt für alle I : ${\frac{Apr(I)}{Opt(I)}}$$\ge$f $\Rightarrow$ Fehlerschranke von A ist f ( f$\le$1 ).

Näherungslösungen für TSP:

1.
Nearest Neighbour (NN) Nimm jeweils billigsten Nachbarn. Für diesen Algorithmus ex. keine konstante Fehlerschranke, d.h., für jede Fehlerschranke ex. ein Graph, so daß NN diese Schranke nicht einhält.
2.
2 - opt für ungerichteten Graphen

Bestimme Rundweg. Tausche Paare aus, falls

c(x,y) + c(a,b) > c(x,b) + c(a,y)


Keine konstante Fehlerschranke.

Im folgenden sei die Dreiecksungleichung erfüllt d.h. c(x,z)$\ge$c(x,y) + c(y,z)$\forall$x,y,z $\in$ V . (Insbesondere gilt also: G ist voll besetzt.)

3.
Spannbaum umlaufen
(a)
Minimum-Spanning-Tree (MST) bestimmen
(b)
Umlaufen des MST


$\Rightarrow$ Länge = 2c(MST) , da c(MST) < c(TSP) $\Rightarrow$ Umlauf < 2c(TSP) .

(c)
Transformiere Umlauf zu einer ``TSP''-Rundreise, indem schon besuchte Knoten ausgelassen werden.


$\Rightarrow$ Fehlerschranke f = 2 .

4.
Verfahren nach Christofides
(a)
MST bestimmen.
(b)
Sei V' $\subseteq$ V . V' = { Knoten aus MST mit ungeradem (Kanten-) Grad bzgl. MST} .
(c)
Bestimme ein Minimum Cost Matching M in G' = (V',E) .

(Wegen |V'| geradzahlig, ist das Matching perfekt.)

(d)
Betrachte G'' = (V,MST $\cup$ M)

Alle Knoten haben geraden Grad (in G'' ). $\Rightarrow$ Graph G'' ist eulersch (d.h. es ex. eine Eulertour in G'' ). Bestimme Eulertour K . Es gilt: c(K) = c(MST) + c(M) ( c(MST) < c(TSP),c(M) < ${\frac{1}{2}}$ · c(TSP) )

(e)
Transformiere wie bei 3.) die Eulertour K zu einer "TSPRundreise. $\Rightarrow$ Fehlerschranke f = ${\frac{3}{2}}$ .

Zur Begründung der weiter unten folgenden Vermutung benötigen wir den Begriff der NP-Vollständigkeit:


prev up inhalt next