Algorithmus von Christofides

Der Algorithmus von Christofides oder der Algorithmus von Christofides und Serdyukov ist ein Algorithmus, der zur Approximation des metrischen Problem des Handlungsreisenden dient. Er wurde 1976 unabhängig von Nicos Christofides und Anatoliy I. Serdyukov entdeckt und war lange Zeit die beste Approximation des Problems für euklidische Graphen. 1996 stellten Arora und Mitchell für diese jedoch einen besseren Approximationsalgorithmus vor. Formal geht man ähnlich wie bei der Minimum-Spanning-Tree-Heuristik vor: 1. * Erzeuge einen minimalen aufspannenden Baum für den zugrunde liegenden Graphen mit Kantengewichten. 2. * Suche ein (bezüglich Kantengewicht) minimales perfektes Matching im Graphen zwischen den Knoten, die ungeraden Grad in dem gerade erzeugten Baum besitzen. 3. * Füge diese Kanten zu hinzu. Dabei können Multikanten auftreten. Der entstehende Graph ist dann eulersch. 4. * Konstruiere eine Eulertour in . 5. * Konstruiere einen Hamiltonkreis in . 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.