imported>SchlurcherBot: Bot: http → https

2025-07-12T07:04:08Z

Bot: http → https

Neue Seite

Der '''Algorithmus von Christofides''' oder der '''Algorithmus von Christofides und Serdyukov''' ist ein [[Algorithmus]], der zur Approximation des [[Metrischer Raum|metrischen]] [[Problem des Handlungsreisenden]] dient. Er wurde 1976 unabhängig von [[Nicos Christofides]] und Anatoliy I. Serdyukov entdeckt<ref>N. Christofides, ''Worst-case analysis of a new heuristic for the travelling salesman problem'', Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (CMU), 1976</ref><ref>{{Literatur |Autor=Anatoliy I. Serdyukov |Titel=Über einige extreme Kreise in Graphen |Hrsg= |Sammelwerk=Upravlyaevye Sistemy |Band=17 |Nummer= |Auflage= |Verlag= |Ort=Novosibirsk |Datum=1978 |Sprache=ru |ISBN= |Seiten=76–79 |Online=http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf |Originaltitel=О некоторых экстремальных обходах в графах}}</ref><ref>{{Literatur |Autor=René van Bevern, Viktoriia A. Slugina |Titel=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem |Hrsg= |Sammelwerk=Historia Mathematica |Band= |Nummer= |Auflage= |Verlag=Elsevier |Ort= |Datum=2020 |ISBN= |arXiv=2004.02437 |DOI=10.1016/j.hm.2020.04.003 |Seiten=}}</ref> und war lange Zeit die beste Approximation des Problems für euklidische Graphen. 1996 stellten [[Sanjeev Arora|Arora]] und [[Joseph S. B. Mitchell|Mitchell]] für diese jedoch einen besseren [[Approximationsalgorithmus]] vor.

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

# Erzeuge einen [[Minimal spannender Baum|minimalen aufspannenden Baum]] <math>T</math> für den zugrunde liegenden [[Graph (Graphentheorie)|Graphen]] <math>G=\left(V,E\right)</math> mit Kantengewichten.
# Suche ein (bezüglich Kantengewicht) minimales [[Perfekte Paarung|perfektes Matching]] <math>M</math> im Graphen zwischen den Knoten, die ungeraden [[Grad (Graphentheorie)|Grad]] in dem gerade erzeugten Baum <math>T</math> besitzen.
# Füge diese Kanten zu <math>T</math> hinzu. Dabei können Multikanten auftreten. Der entstehende Graph  <math>T\cup M</math> ist dann [[Eulerscher Graph|eulersch]].
# Konstruiere eine [[Eulertour#Auffinden eines Eulerkreises|Eulertour]] in <math>T\cup M</math>.
# Konstruiere einen [[Hamiltonkreisproblem|Hamiltonkreis]] in <math>T\cup M</math>. 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 <math>1{,}5</math>-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]].

* Die Summe der Kantengewichte im Minimum-Spanning-Tree (MST) ist sowieso kleiner gleich der optimalen Lösung, da jede Lösung des Traveling Salesman Problem (TSP) einen [[Spannbaum]] enthält.
* Bezüglich des Matchings gilt folgendes:<br />Sei <math>i_1, \ldots, i_n</math> die Folge der Knoten vormals ungeraden Grades in der optimalen Lösung; dazwischen liegen irgendwelche anderen Knoten: <math>a - i_1 - b - i_2 - c - \cdots - i_n</math>. Betrachte die beiden Matchings <math>\left\{ \left\{i_1, i_2\right\}, \left\{i_3, i_4\right\}, \ldots \left\{i_{n-1}, i_n\right\}\right\}</math> sowie <math>\left\{ \left\{i_2, i_3\right\}, \left\{i_4, i_5\right\}, \ldots \left\{i_n, i_1\right\}\right\}</math>. Dann gilt aufgrund der Dreiecksungleichung, dass <math>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</math><br/> 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. So lässt sich die Summe der Kantengewichte entlang der Eulertour in <math>T \cup M</math> (d. h. die Summe der Gewichte aller Kanten in <math>T \cup M</math>) nach oben hin abschätzen.
* Schließlich lässt sich die Summe der Kanten in dem aus der Eulertour erzeugten Hamiltonkreis durch erneutes Anwenden der Dreiecksungleichung nach oben hin durch die Summe der Kanten in der Eulertour abschätzen (denn die Direktkanten können nicht länger sein als die Verbindung über einen schon früher besuchten Knoten), also transitiv durch das 1,5-Fache der optimalen Lösung.

== Beispiel ==
{| class="wikitable"
|-
|[[Datei:Metrischer Graph mit 5 Knoten.svg|150px]]|| Ausgangslage: metrischer Graph <math>G=\left(V,E\right)</math> mit Kantengewichten

|-
|[[Datei:Christofides MST.svg|150px]] || Minimalen Spannbaum <math>T</math> berechnen.
|-
|[[Datei:V'.svg|150px]] || Die Menge der Knoten mit ungeradem Grad im Spannbaum bestimmen (<math>V'</math>).
|-
|[[Datei:G V'.svg|150px]] || <math>G</math> auf die Knoten aus <math>V'</math> reduzieren (<math>G|_{V'}</math>).
|-
|[[Datei:Christofides Matching.svg|150px]] || Matching <math>M</math> mit minimalem Gewicht auf <math>G|_{V'}</math> bestimmen.
|-
|[[Datei:TuM.svg|150px]] || Matching und Spannbaum vereinigen (<math>T\cup M</math>). Dieser Schritt sorgt dafür, dass Knoten mit vormals ungeradem Grad nun einen geraden Grad aufweisen. Dies ist eine notwendige Bedingung für die Berechnung der Euler-Tour im nächsten Schritt.
|-
|[[Datei:Eulertour.svg|150px]] || Euler-Tour auf <math>T\cup M</math> berechnen (A-B-C-A-D-E-A).
|-
|[[Datei:Eulertour_bereinigt.svg|150px]] || 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.
|}

== Literatur ==
* Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): ''The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization''. Wiley, Chichester 1985. ISBN 0-471-90413-9, Abschnitt 5.3.4: ''Christofides' algorithm''

== Weblinks ==
* [https://www.belfrage.net/eth/da/pdf/uebung13.pdf Foliensatz mit grafischer Visualisierung des Algorithmus] (PDF, 154 KiB)

== Einzelnachweise ==
<references />

[[Kategorie:Optimierungsalgorithmus|C]]
[[Kategorie:Algorithmus (Graphentheorie)|C]]

Algorithmus von Christofides - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https