Die Christofides-Heuristik

Schritt 1

Die Christofides-Heuristik wendet auch die MST-Heuristik an. Der entscheidende Unterschied ist, dass dem MST vorher über ein sogenanntes Matching berechnete Kanten hinzugefügt werden.

Das Matching funktioniert folgendermaßen:

Zunächst wird ein Minimum Spanning Tree erzeugt und die Knoten mit geradem Grad markiert(rot).

Schritt 1

  • Weiter