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: == 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 doppe...