Английская Википедия:Christofides algorithm

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality). It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy I. Serdyukov (Шаблон:Lang-ru); the latter discovered it independently in 1976 (but the publication is dated 1978).

Algorithm

Let Шаблон:Math be an instance of the travelling salesman problem. That is, Шаблон:Mvar is a complete graph on the set Шаблон:Mvar of vertices, and the function Шаблон:Mvar assigns a nonnegative real weight to every edge of Шаблон:Mvar. According to the triangle inequality, for every three vertices Шаблон:Mvar, Шаблон:Mvar, and Шаблон:Mvar, it should be the case that Шаблон:Math.

Then the algorithm can be described in pseudocode as follows.

1. Create a minimum spanning tree Шаблон:Mvar of Шаблон:Mvar.
2. Let Шаблон:Mvar be the set of vertices with odd degree in Шаблон:Mvar. By the handshaking lemma, Шаблон:Mvar has an even number of vertices.
3. Find a minimum-weight perfect matching Шаблон:Mvar in the subgraph induced in Шаблон:Mvar by Шаблон:Mvar.
4. Combine the edges of Шаблон:Mvar and Шаблон:Mvar to form a connected multigraph Шаблон:Mvar in which each vertex has even degree.
5. Form an Eulerian circuit in Шаблон:Mvar.
6. Make the circuit found in previous step into a Hamiltonian circuit by skipping repeated vertices (shortcutting).

Steps 5 and 6 do not necessarily yield only a single result; as such, the heuristic can give several different paths.

Computational complexity

The worst-case complexity of the algorithm is dominated by the perfect matching step, which has <math> O(n^3) </math> complexity. Serdyukov's paper claimed <math> O(n^3 \log n) </math> complexity, because the author was only aware of a less efficient perfect matching algorithm.

Approximation ratio

The cost of the solution produced by the algorithm is within 3/2 of the optimum. To prove this, let Шаблон:Mvar be the optimal traveling salesman tour. Removing an edge from Шаблон:Mvar produces a spanning tree, which must have weight at least that of the minimum spanning tree, implying that Шаблон:Math. Next, number the vertices of Шаблон:Mvar in cyclic order around Шаблон:Mvar, and partition Шаблон:Mvar into two sets of paths: the ones in which the first path vertex in cyclic order has an odd number and the ones in which the first path vertex has an even number. Each set of paths corresponds to a perfect matching of Шаблон:Mvar that matches the two endpoints of each path, and the weight of this matching is at most equal to the weight of the paths. Since these two sets of paths partition the edges of Шаблон:Mvar, one of the two sets has at most half of the weight of Шаблон:Mvar, and thanks to the triangle inequality its corresponding matching has weight that is also at most half the weight of Шаблон:Mvar. The minimum-weight perfect matching can have no larger weight, so Шаблон:Math. Adding the weights of Шаблон:Mvar and Шаблон:Mvar gives the weight of the Euler tour, at most Шаблон:Math. Thanks to the triangle inequality, shortcutting does not increase the weight, so the weight of the output is also at most Шаблон:Math.

Lower bounds

There exist inputs to the travelling salesman problem that cause the Christofides algorithm to find a solution whose approximation ratio is arbitrarily close to 3/2. One such class of inputs are formed by a path of Шаблон:Mvar vertices, with the path edges having weight Шаблон:Math, together with a set of edges connecting vertices two steps apart in the path with weight Шаблон:Math for a number Шаблон:Math chosen close to zero but positive. All remaining edges of the complete graph have distances given by the shortest paths in this subgraph. Then the minimum spanning tree will be given by the path, of length Шаблон:Math, and the only two odd vertices will be the path endpoints, whose perfect matching consists of a single edge with weight approximately Шаблон:Math. The union of the tree and the matching is a cycle, with no possible shortcuts, and with weight approximately Шаблон:Math. However, the optimal solution uses the edges of weight Шаблон:Math together with two weight-Шаблон:Math edges incident to the endpoints of the path, and has total weight Шаблон:Math, close to Шаблон:Mvar for small values of Шаблон:Math. Hence we obtain an approximation ratio of 3/2.

Example

Файл:Metrischer Graph mit 5 Knoten.svg	Given: complete graph whose edge weights obey the triangle inequality
Файл:Christofides MST.svg	Calculate minimum spanning tree Шаблон:Mvar
Файл:V'.svg	Calculate the set of vertices Шаблон:Mvar with odd degree in Шаблон:Mvar
Файл:G V'.svg	Form the subgraph of Шаблон:Mvar using only the vertices of Шаблон:Mvar
Файл:Christofides Matching.svg	Construct a minimum-weight perfect matching Шаблон:Mvar in this subgraph
Файл:TuM.svg	Unite matching and spanning tree Шаблон:Math to form an Eulerian multigraph
Файл:Eulertour.svg	Calculate Euler tour Here the tour goes A->B->C->A->D->E->A. Equally valid is A->B->C->A->E->D->A.
Файл:Eulertour bereinigt.svg	Remove repeated vertices, giving the algorithm's output. If the alternate tour would have been used, the shortcut would be going from C to E which results in a shorter route (A->B->C->E->D->A) if this is an euclidean graph as the route A->B->C->D->E->A has intersecting lines which is proven not to be the shortest route.

Further developments

This algorithm still stands as the best polynomial time approximation algorithm for the stated problem that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces. In July 2020 Karlin, Klein, and Gharan released a preprint in which they introduced a novel approximation algorithm and claimed that its approximation ratio is 1.5 − 10⁻³⁶. Theirs is a randomized algorithm and it follows similar principles to Christofides' algorithm, but uses a randomly chosen tree from a carefully chosen random distribution in place of the minimum spanning tree. The paper was published at STOC'21 where it received a best paper award.

In the special case of Euclidean space, for any c > 0, where d is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP in

<math>O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right)</math> time;

this is called a polynomial-time approximation scheme (PTAS). Sanjeev Arora and Joseph S. B. Mitchell were awarded the Gödel Prize in 2010 for their concurrent discovery of a PTAS for the Euclidean TSP.

External links

• NIST Christofides Algorithm Definition