Christofides-Heuristik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Christofides-Heuristik ist ein Algorithmus, der zur Approximation von metrischen Problemen des Handlungsreisenden dient. Er war lange Zeit die beste Approximation für euklidische Graphen. (Arora und Mitchell stellten 1996 ein besseres PTAS vor.)

Formal geht man ähnlich wie bei der Minimum-Spanning-Tree-Heuristik vor:

  1. Erzeuge einen minimalen aufspannenden Baum T für den zugrunde liegenden Graphen G=\left(V,E\right) mit Kantengewichten.
  2. Suche ein (bezüglich Kantengewicht) minimales perfektes Matching M im Graphen zwischen den Knoten, die ungeraden Grad in dem gerade erzeugten Baum T besitzen.
  3. Füge diese Kanten zu T hinzu. Der entstehende Graph  T\cup M ist dann Eulersch.
  4. Konstruiere eine Eulertour in T\cup M.
  5. Konstruiere einen Hamiltonkreis in T\cup M. Wähle dazu einen beliebigen Startknoten und gehe die Eulertour ab. Ersetze dabei die bereits besuchten Knoten durch direkte Verbindungen (bzw. Abkürzungen) zum nächsten noch nicht besuchten Knoten.

Gütegarantie[Bearbeiten]

Es lässt sich zeigen, dass die Christofides-Heuristik eine 1,5-Approximation ist. Das heißt die so entstandene Rundreise ist maximal um die Hälfte länger als die optimale Tour. Der Beweis beruht dabei auf einer wiederholten Anwendung der Dreiecksungleichung.

  • Der Minimum-Spanning-Tree (MST) ist sowieso kleiner gleich der optimalen Lösung, da jede Lösung des Traveling Salesman Problem (TSP) einen Spanning Tree enthält.
  • Bezüglich des Matching gilt folgendes:
    Sei i_1, \ldots, i_n die Folge der Knoten vormals ungeraden Grades in der optimalen Lösung; dazwischen liegen irgendwelche anderen Knoten: a - i_1 - b - i_2 - c - \ldots - i_n. Betrachte die beiden Matchings \{ (i_1, i_2), (i_3, i_4), \ldots (i_{n-1}, i_n)\} sowie \{ (i_2, i_3), (i_4, i_5), \ldots (i_n, i_1)\}. Dann gilt aufgrund der Dreiecksungleichung, dass c(i_1, i_2) \leq c(i_1, b) + c(b, i_2), c(i_2, i_3) \leq c(i_2, c) + c(c, i_3), \ldots Also sind die Gesamtkosten der optimalen Lösung größer gleich derer zweier beliebiger Matchings, insbesondere also zwei Mal des minimalen Matchings. Dann ist ein minimales Matching auch nur maximal halb so groß wie die optimale Lösung.

Beispiel[Bearbeiten]

Metrischer Graph mit 5 Knoten.svg Ausgangslage: metrischer Graph G=\left(V,E\right) mit Kantengewichten
Christofides MST.svg Minimalen Spannbaum T berechnen.
V'.svg Die Menge der Knoten mit ungeradem Grad im Spannbaum bestimmen (V').
G V'.svg G auf die Knoten aus V' reduzieren (G|_{V'}).
Christofides Matching.svg Matching M mit minimalem Gewicht auf G|_{V'}bestimmen.
TuM.svg Matching und Spannbaum vereinigen (T\cup M).
Eulertour.svg Euler-Tour auf T\cup M berechnen (A-B-C-A-D-E-A).
Eulertour bereinigt.svg Wiederholt vorkommende Knoten entfernen und durch Direktverbindung ersetzen (A-B-C-D-E-A). In metrischen Graphen führt dies nicht zu einer längeren Strecke.

Diese Tour ist die Ausgabe des Algorithmus.

Weblinks[Bearbeiten]