Christofides-Heuristik

aus Wikipedia, der freien Enzyklopädie

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 minimales perfektes Matching auf den Knoten des Baumes, die ungeraden Grad besitzen, und füge diese Kanten zu B hinzu. Der entstehende Graph G ist dann Eulersch.
3. Konstruiere eine Eulertour in G.
4. Wähle einen Startknoten und gehe die Eulertour ab. Ersetze die bereits besuchten Knoten durch direkte Verbindungen zum nächsten noch nicht besuchten Knoten.

[Bearbeiten] Gütegarantie

Es lässt sich zeigen, dass die Christofides-Heuristik eine Gütegarantie von 50% besitzt, d.h. 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 kleiner gleich derer zweier beliebiger Matchings, insbesondere also des minimalen. Dann ist ein minimales Matching auch nur halb so groß wie die optimale Lösung.