Diskussion:MST-Heuristik
aus Wikipedia, der freien Enzyklopädie
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.
