Minimum-Spanning-Tree-Heuristik

Minimum-Spanning-Tree-Heuristik

Die MST-Heuristik (MST steht für minimal 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
  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.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Spanning Tree — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… …   Deutsch Wikipedia

  • Christofides-Heuristik — Die Christofides Heuristik ist ein Algorithmus, der zur Approximation von metrischen Problemen des Handlungsreisenden dient. Sie ist die zur Zeit beste Heuristik für solche Probleme mit einer festen Gütegarantie. Formal geht man ähnlich wie bei… …   Deutsch Wikipedia

  • 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: Erzeuge einen minimalen Spannbaum für den… …   Deutsch Wikipedia

  • Botenproblem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Euklidisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Handlungsreisendenproblem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Metrisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Problem des Handelsreisenden — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Rectilinieares Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Rundfahrtproblem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”