www.wikidata.de-de.nina.az

Algorithmus von Christofides Der oder der und Serdyukov ist ein Algorithmus der zur Approximation des metrischen Problem

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.

Gütegarantie Bearbeiten

Es lässt sich zeigen, dass die Christofides-Heuristik eine -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:
    Sei die Folge der Knoten vormals ungeraden Grades in der optimalen Lösung; dazwischen liegen irgendwelche anderen Knoten: . Betrachte die beiden Matchings sowie . Dann gilt aufgrund der Dreiecksungleichung, dass
    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 (d. h. die Summe der Gewichte aller Kanten in ) 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 Bearbeiten

Ausgangslage: metrischer Graph mit Kantengewichten
Minimalen Spannbaum berechnen.
Die Menge der Knoten mit ungeradem Grad im Spannbaum bestimmen ().
auf die Knoten aus reduzieren ().
Matching mit minimalem Gewicht auf bestimmen.
Matching und Spannbaum vereinigen (). 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.
Euler-Tour auf berechnen (A-B-C-A-D-E-A).
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 Bearbeiten

  • 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 Bearbeiten

Einzelnachweise Bearbeiten

  1. 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
  2. Anatoliy I. Serdyukov: Über einige extreme Kreise in Graphen. In: Upravlyaevye Sistemy. Band 17. Novosibirsk 1978, S. 76–79 (russisch, nsc.ru [PDF] Originaltitel: О некоторых экстремальных обходах в графах.).
  3. René van Bevern, Viktoriia A. Slugina: A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. In: Historia Mathematica. Elsevier, 2020, doi:10.1016/j.hm.2020.04.003, arxiv:2004.02437.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 unabhangig von Nicos Christofides und Anatoliy I Serdyukov entdeckt 1 2 3 und war lange Zeit die beste Approximation des Problems fur euklidische Graphen 1996 stellten Arora und Mitchell fur diese jedoch einen besseren Approximationsalgorithmus vor Formal geht man ahnlich wie bei der Minimum Spanning Tree Heuristik vor Erzeuge einen minimalen aufspannenden Baum T displaystyle T fur den zugrunde liegenden Graphen G V E displaystyle G left V E right mit Kantengewichten Suche ein bezuglich Kantengewicht minimales perfektes Matching M displaystyle M im Graphen zwischen den Knoten die ungeraden Grad in dem gerade erzeugten Baum T displaystyle T besitzen Fuge diese Kanten zu T displaystyle T hinzu Dabei konnen Multikanten auftreten Der entstehende Graph T M displaystyle T cup M ist dann eulersch Konstruiere eine Eulertour in T M displaystyle T cup M Konstruiere einen Hamiltonkreis in T M displaystyle T cup M Wahle dazu einen beliebigen Startknoten und gehe die Eulertour ab Ersetze dabei die bereits besuchten Knoten durch direkte Verbindungen bzw Abkurzungen zum nachsten noch nicht besuchten Knoten Inhaltsverzeichnis 1 Gutegarantie 2 Beispiel 3 Literatur 4 Weblinks 5 EinzelnachweiseGutegarantie BearbeitenEs lasst sich zeigen dass die Christofides Heuristik eine 1 5 displaystyle 1 5 nbsp Approximation ist Das heisst die so entstandene Rundreise ist maximal um die Halfte langer 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 Losung da jede Losung des Traveling Salesman Problem TSP einen Spannbaum enthalt Bezuglich des Matchings gilt folgendes Sei i 1 i n displaystyle i 1 ldots i n nbsp die Folge der Knoten vormals ungeraden Grades in der optimalen Losung dazwischen liegen irgendwelche anderen Knoten a i 1 b i 2 c i n displaystyle a i 1 b i 2 c cdots i n nbsp Betrachte die beiden Matchings i 1 i 2 i 3 i 4 i n 1 i n displaystyle left left i 1 i 2 right left i 3 i 4 right ldots left i n 1 i n right right nbsp sowie i 2 i 3 i 4 i 5 i n i 1 displaystyle left left i 2 i 3 right left i 4 i 5 right ldots left i n i 1 right right nbsp Dann gilt aufgrund der Dreiecksungleichung dass c i 1 i 2 c i 1 b c b i 2 c i 2 i 3 c i 2 c c c i 3 displaystyle 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 nbsp Also sind die Gesamtkosten der optimalen Losung grosser gleich derer zweier beliebiger Matchings insbesondere also zwei Mal des minimalen Matchings Dann ist ein minimales Matching auch nur maximal halb so gross wie die optimale Losung So lasst sich die Summe der Kantengewichte entlang der Eulertour in T M displaystyle T cup M nbsp d h die Summe der Gewichte aller Kanten in T M displaystyle T cup M nbsp nach oben hin abschatzen Schliesslich lasst 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 abschatzen denn die Direktkanten konnen nicht langer sein als die Verbindung uber einen schon fruher besuchten Knoten also transitiv durch das 1 5 Fache der optimalen Losung Beispiel Bearbeiten nbsp Ausgangslage metrischer Graph G V E displaystyle G left V E right nbsp mit Kantengewichten nbsp Minimalen Spannbaum T displaystyle T nbsp berechnen nbsp Die Menge der Knoten mit ungeradem Grad im Spannbaum bestimmen V displaystyle V nbsp nbsp G displaystyle G nbsp auf die Knoten aus V displaystyle V nbsp reduzieren G V displaystyle G V nbsp nbsp Matching M displaystyle M nbsp mit minimalem Gewicht auf G V displaystyle G V nbsp bestimmen nbsp Matching und Spannbaum vereinigen T M displaystyle T cup M nbsp Dieser Schritt sorgt dafur dass Knoten mit vormals ungeradem Grad nun einen geraden Grad aufweisen Dies ist eine notwendige Bedingung fur die Berechnung der Euler Tour im nachsten Schritt nbsp Euler Tour auf T M displaystyle T cup M nbsp berechnen A B C A D E A nbsp Wiederholt vorkommende Knoten entfernen und durch Direktverbindung ersetzen A B C D E A In metrischen Graphen fuhrt dies nicht zu einer langeren Strecke Diese Tour ist die Ausgabe des Algorithmus Literatur BearbeitenLawler 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 algorithmWeblinks BearbeitenFoliensatz mit grafischer Visualisierung des Algorithmus PDF 154 KiB Einzelnachweise Bearbeiten 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 Anatoliy I Serdyukov Uber einige extreme Kreise in Graphen In Upravlyaevye Sistemy Band 17 Novosibirsk 1978 S 76 79 russisch nsc ru PDF Originaltitel O nekotoryh ekstremalnyh obhodah v grafah Rene van Bevern Viktoriia A Slugina A historical note on the 3 2 approximation algorithm for the metric traveling salesman problem In Historia Mathematica Elsevier 2020 doi 10 1016 j hm 2020 04 003 arxiv 2004 02437 Abgerufen von https de wikipedia org w index php title Algorithmus von Christofides amp oldid 223842971