MST-Heuristik – einfach erklärt

Zweck und Verfahren

Die MST-Heuristik ist ein Näherungsverfahren für das metrische Problem des Handlungsreisenden (TSP). Gesucht wird dabei ein möglichst kurzer Rundweg, der jeden Knoten genau einmal besucht und zum Startknoten zurückkehrt. „MST“ steht für „minimum spanning tree“, also minimaler Spannbaum: ein zusammenhängender, kreisfreier Teilgraph, der alle Knoten verbindet und unter allen solchen Spannbäumen die geringste Gesamtkantenlänge besitzt.

Das Verfahren besteht aus drei Schritten:

Zunächst wird für den zugrunde liegenden ungerichteten Graphen ein minimaler Spannbaum erzeugt.
Anschließend wird jede Kante dieses Spannbaums verdoppelt. Dadurch entsteht ein eulerscher Graph, in dem ein Eulerkreis möglich ist, also ein geschlossener Weg, der jede Kante genau einmal durchläuft.
Von einem beliebigen Startknoten aus folgt man einem solchen Eulerkreis. Bereits besuchte Knoten werden übersprungen, indem man direkt zum folgenden Knoten geht, sofern es sich nicht um den letzten Knoten des Kreises handelt. So entsteht eine Rundreise, in der jeder Knoten nur einmal vorkommt.

Gütegarantie

Für TSP-Instanzen, welche die Dreiecksungleichung erfüllen, ist die von der MST-Heuristik gefundene Rundreise höchstens doppelt so teuer beziehungsweise lang wie eine optimale Lösung. Die Dreiecksungleichung besagt hier, dass eine direkte Kante zwischen zwei Knoten niemals länger ist als ein Umweg über weitere Knoten.

Durch das Verdoppeln des minimalen Spannbaums wird jede seiner Kanten genau zweimal benutzt. Beim anschließenden Überspringen bereits besuchter Knoten werden teilweise direkte Kanten gewählt, die nicht zum Spannbaum gehören. Wegen der Dreiecksungleichung können diese Abkürzungen den Weg nicht verlängern. Der berechnete Kreis ist daher höchstens doppelt so lang wie der minimale Spannbaum.

Zur Verbindung mit der optimalen TSP-Lösung entfernt man aus deren Rundreise eine Kante. Der verbleibende Weg ist ein Spannbaum und kann nicht kürzer als der minimale Spannbaum sein. Somit ist die Länge des minimalen Spannbaums höchstens so groß wie die Kosten der optimalen Rundreise. Da die MST-Heuristik höchstens die doppelte Länge des minimalen Spannbaums erreicht, ist ihre Lösung höchstens doppelt so teuer wie die optimale Lösung.