MST-Heuristik

Die MST-Heuristik (MST steht für minimum spanning tree bzw. minimaler Spannbaum) dient dazu, das metrische Problem des Handlungsreisenden (TSP) zu approximieren. Dabei geht man wie folgt vor:

1. Erzeuge einen minimalen Spannbaum für den zugrundeliegenden ungerichteten Graphen
2. Verdopple jede Kante im resultierenden Spannbaum, was zu einem Eulerschen Graphen führt
3. Wähle einen beliebigen Startknoten und folge den Kanten des verdoppelten Spannbaums im Sinne eines Eulerkreises. Bereits besuchte Knoten werden dabei durch die direkte Kante zum folgenden Knoten übersprungen, sofern es sich nicht um den letzten Knoten des Kreises handelt.

Gütegarantie

Für jene Instanzen des TSP, in denen die Dreiecksungleichung erfüllt ist, liefert die MST-Heuristik eine Lösung, die höchstens doppelt so teuer wie die beste ist. Dies kann man damit begründen, dass jede Kante des minimalen Spannbaums genau zweimal benutzt wird. Da jeder Knoten allerdings nur (genau) einmal besucht werden darf (mit Ausnahme des Start- und Zielknotens), muss an manchen Stellen statt des vom Spannbaum erzeugten Wegs eine Kante zwischen zwei Knoten, die nicht im Spannbaum enthalten ist, gewählt werden. Da die Dreiecksungleichung erfüllt ist, kann dieser direkte Weg niemals länger als der durch den Spannbaum vorgegebene Weg sein.

Entfernt man in der optimalen Lösung des TSP eine Kante, erhält man ebenfalls einen Spannbaum. Dieser ist mindestens so schwer wie der minimale Spannbaum. Der von der MST-Heuristik berechnete Kreis ist nach obiger Argumentation höchstens doppelt so schwer wie der minimale Spannbaum. Es folgt die Behauptung.

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