Diskussion:MST-Heuristik
Letzter Kommentar: vor 8 Jahren von FerdiBf
Was ein Spannbaum sein soll wird aus dem Artikel nicht deutlich. Es ist daher auch nicht nachvollziehbar wie die MST-Heuristik funktioniert.
Einen Weg zu finden, der maximal doppelt so lang wie der optimale Weg ist, sollte eigentlich nie ein Problem sein. Als Beispiel könnten ein Qudrat betrachtet werden. Der optimale Weg durch die vier Eckpunkte hat die vierfache Kantenlänge. Der ungünstigste Rundweg würde über zwei Diagonalen und zwei kürzere Kanten führen und wäre nur etwa 20 Prozent länger.
- Der Begriff Spannbaum ist verlinkt. Warum es trivial sein sollte, einen Weg zu finden, der doppelt so lang wie der optimale Weg, kann ich nicht nachvollziehen.--FerdiBf (Diskussion) 14:13, 12. Nov. 2016 (CET)