Christofides' algorithm
The algorithm of Christofides or the algorithm of Christofides and Serdyukov is an algorithm that for the approximation of the metric of the traveling salesman problem is used. It was discovered in 1976 independently by Nicos Christofides and Anatoliy I. Serdyukov and has long been the best approximation of the problem for Euclidean graphs. In 1996, however, Arora and Mitchell presented a better PTAS for these .
The formal approach is similar to that of the minimum spanning tree heuristic :
- Generate a minimal spanning tree for the underlying graph with edge weights.
- Find a minimal perfect match (in terms of edge weight) in the graph between the nodes that have odd degrees in the tree just created .
- Add these edges to . Multi-edges can occur. The resulting graph is then Eulerian .
- Construct an Euler tour in .
- Construct a Hamilton cycle in . To do this, choose any starting node and take the Euler tour. Replace the already visited nodes with direct connections (or abbreviations) to the next not yet visited node.
Quality guarantee
It can be shown that the Christofides heuristic is a 1.5 approximation. This means that the resulting round trip is a maximum of half longer than the optimal tour. The proof is based on repeated application of the triangle inequality .
- The sum of the edge weights in the Minimum Spanning Tree (MST) is anyway less than or equal to the optimal solution, since every solution of the Traveling Salesman Problem (TSP) contains a spanning tree .
- Regarding the matching, the following applies:
Let the sequence of nodes previously of odd degree in the optimal solution; therebetween are any other nodes: . Consider the two matchings as well . Then, due to the triangle inequality, the following applies that the total costs of the optimal solution are greater than or equal to those of any two matchings, in particular two times the minimum matching. Then a minimal matching is only a maximum of half the size of the optimal solution. In this way the sum of the edge weights along the Euler tour in (i.e. the sum of the weights of all edges in ) can be estimated upwards. - Finally, the sum of the edges in the Hamilton circle generated from the Euler tour can be estimated by applying the triangle inequality upwards again using the sum of the edges in the Euler tour (because the direct edges cannot be longer than the connection via a previously visited node), i.e. transitively by 1.5 times the optimal solution.
example
literature
- Lawler, Lenstra, Rinnooy Kan, Shmoys (Eds.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization . Wiley, Chichester 1985. ISBN 0-471-90413-9 , Section 5.3.4: Christofides' algorithm
Web links
- Set of slides with graphic visualization of the algorithm (PDF, 154 KiB)
Individual evidence
- ^ N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem , Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (CMU), 1976
- ↑ Anatoliy I. Serdyukov: About some extreme circles in graphs . In: Upravlyaevye Sistemy . tape 17 . Novosibirsk 1978, p. 76–79 (Russian, nsc.ru [PDF] Original title: О некоторых экстремальных обходах в графах .).
- ^ 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 .