Online-Bibliothek

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 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.

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.