Christofides-Heuristik

Die Christofides-Heuristik ist ein Algorithmus, der zur Approximation von metrischen Problemen des Handlungsreisenden dient. Sie ist die zur Zeit beste Heuristik für solche Probleme mit einer festen Gütegarantie.

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

1. Erzeuge einen minimalen aufspannenden Baum B für den zugrunde liegenden Graphen.
2. Suche ein (bezüglich Kantengewicht) minimales perfektes Matching im Graphen zwischen den Knoten, die ungeraden Grad in dem gerade erzeugten Baum B besitzen.
3. Füge diese Kanten zu B hinzu. Der entstehende Graph G ist dann Eulersch.
4. Konstruiere eine Eulertour in G. 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

Es lässt sich zeigen, dass die Christofides-Heuristik eine Gütegarantie von 50 % besitzt, 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 MST ist sowieso kleiner gleich der optimalen Lösung, da jede Lösung des TSP einen Spanning Tree enthält.
• Bezüglich des Matching gilt folgendes:
  Sei i₁ … i_n die Folge der Knoten vormals ungeraden Grades in der optimalen Lösung; dazwischen liegen irgendwelche anderen Knoten {}: {a}−i₁−{b}−i₂−{c}−i₃ … −i_n.   Betrachte die beiden Matchings   i₁−i₂, i₃−i₄ … sowie i₂−i₃, i₄−i₅ …   Dann gilt aufgrund der Dreiecksungleichung, dass   i₁−i₂ ≤ b; i₂−i₃ ≤ c; i₃−i₄ ≤ d … Also sind die Gesamtkosten der optimalen Lösung größer gleich derer zweier beliebiger Matchings, insbesondere also des minimalen. Dann ist ein minimales Matching auch nur maximal halb so groß wie die optimale Lösung.

Weblinks

• Foliensatz mit grafischer Visualisierung des Algorithmus (PDF, 154 KiB)