Die Chhristofides-Heuristik

Schritt 3

Jetzt sucht man die jeweils kürzeste Verbindung zwischen 2 Knoten im Kompletten Graphen und somit Knotenpaare(Matching) erzeugt.

Schritt 3

Danach fügt man die dabei entstehenden Kanten, die noch nicht zum MST gehören diesem hinzu.

Schritt 3b

  • Weiter
  • Zurück