MST heuristic

The minimum spanning tree (MST stands for minimum spanning tree or minimum spanning tree ) is used, the metric Traveling Salesman Problem to approximate (TSP). Proceed as follows:

1. Generate a minimal spanning tree for the underlying undirected graph
2. Will double every edge in the resulting spanning tree, resulting in an Eulerian graph leads
3. Choose any starting node and follow the edges of the doubled spanning tree in the sense of an Euler circle . Nodes that have already been visited are skipped by the direct edge to the following node, provided it is not the last node of the circle.

Quality guarantee

For those instances of the TSP in which the triangle inequality is satisfied, the MST heuristic provides a solution that is at most twice as expensive as the best. This can be justified by the fact that each edge of the minimal spanning tree is used exactly twice. However, since each node can only be visited (exactly) once (with the exception of the start and destination nodes), an edge between two nodes that is not contained in the spanning tree must be selected at some points instead of the path created by the spanning tree. Since the triangle inequality is fulfilled, this direct path can never be longer than the path given by the spanning tree.

If you remove an edge in the optimal solution of the TSP, you also get a spanning tree. This is at least as heavy as the minimal spanning tree. According to the above argument, the circle calculated by the MST heuristic is at most twice as heavy as the minimum spanning tree. The assertion follows.

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.2: Minimum spanning trees and traveling salesman tours