Güte des Nearest Insertion Verfahrens
-
Ich schreibe gerade etwas über das Nearest Insertion Verfahren für die Annäherung einer TSP-Tour durch einen Graphen und bin in dieser pdf auf die Behauptung gestoßen, dass die maximale Tourlänge 200% der optimalen Tour sei:
http://www.phynet.de/private/snOOfy/tanler-tsp.pdf (Seite 8, oder 6 nach den Seitenzahlen)Diese Behauptung wird allerdings weder bewiesen noch irgendwie erklärt. Ich habe schon nach anderen Quellen gesucht, aber bisher nichts gefunden.
Kennt jemand einen Beweis oder eine logische Argumentation?Ich hoffe diese Frage ist nicht zu speziell für ein allgemeines Forum...
-
Falls es hier irgendwen interessiert...
Die obere Schranke ist 200%, wenn der Graph die Dreiecksungleichung erfüllt, ansonsten liefert der Algorithmus beliebig schlechte Ergebnisse.
Das habe ich in dem englischen Fachbuch "The Traveling Salesman Problem" von E.L.Lawler, J.K.Lenstra und anderen gefunden.
War wohl doch ein bisschen zu speziell
-
Hallo,
hab ich doch damals geschrieben -> nur bei metrischem TSP (das impliziert bereits, daß die Dreiecksungleichung gelten muss) :-).
Liebe Grüße und viel Erfolg noch,
Martin Tanler
-
Oha, der Autor^^
Jo, stimmt, hast du geschrieben. Ich hatte "symmetrisch" gelesen, was ja eine andere Bedeutung hat.
Schade eigentlich, ich hatte mich schon gefreut, endlich mal einen dieser angeblich so zahlreichen Fehler bei Wikipedia gefunden zu haben, von denen ich bisher noch nie etwas gemerkt hatte
Aber vielen Dank für deine Arbeit, hat mir sehr geholfen.