Metrisches TSP
-
Kurze Frage: Ist die optimale Lösung eines metrischen TSP immer überschneidungsfrei? Habe leider im Wikipedia-Artikel nichts dazu gefunden.
MfG
-
Ja. Wenn du eine Kreuzung hast, dann spannen die endpunkte der strecken, die sich kreuzen ein konvexes viereck auf. Je zwei seiten eines solchen Vierecks sind immer kürzer als die beiden Diagonalen. (Einfach mal aufmalen!)
-
Jester: Die Argumentation stimmt nur im euklidischen Raum, weil man da den Cosinus-Satz hat. Als Gegenbeispiel für metrisches TSP kann man die Punkte (0,0), (0,1), (1,0), (1,1) zusammen mit der Maximumsnorm nehmen. Dann hat jede beliebige Tour die Länge 4.
-
Was ist mit überschneidungsfrei gemeint?
edit: Aus Jesters Antwort entnehme ich mal, dass die Kanten sich nicht überkreuzen sollen? Was soll das heißen, das ist keine Eigenschaft eines Graphen, sondern einer bestimmten Darstellung eines Graphen, die mit der Lösung eines TSP überhaupt nichts zu tun hat. Was sind die genauen Voraussetzungen?
-
Ich war jetzt im euklidischen Fall. Es stimmt natürlich, dass metrisch allgemein erstmal nur sagt, dass man einen gerichteten Graph hat in dem die Dreiecksungleichung gilt. -- Da machen Kreuzungen nicht so viel Sinn.
@Michael E.: Auch bei einer beliebigen anderen Metrik im R^2 gilt doch die Dreiecksungleichung, und die allein sollte genügen um das <= zu bekommen (du gehst von einer Ecke zum Schnittpunkt der Diagonalen zur anderen Ecke und ersetzt das durch eine Direktverbindung). Und auch wenn einem das nicht sagt, dass jede optimale Tour überschneidungsfrei ist, so sagt es zumindest das für die Praxis vermutlich genauso interessante: es gibt eine optimale Tour, die überschneidungsfrei ist. Bzw., noch etwas praktischer: Überschneidungen entfernen verlängert die Tour nicht.
-
Bashar: Wie beim euklidischen TSP üblich, habe ich das interpretiert als "Punkte im mehrdimensionalen Raum, die als vollständiger Graph mit den jeweiligen Abständen als Kantengewichte interpretiert werden".
Jester: Diese Spitzfindigkeit hätte ich bei meinem Einwand wohl erwähnen sollen. Ich hab mich wörtlich an der Frage orientiert, ob jede optimale Tour überschneidungsfrei ist.
-
Michael E. schrieb:
Bashar: Wie beim euklidischen TSP üblich
OK, aber es ist nur von metrischem TSP die Rede. Das "euklidisch" wäre z.B. eine der unerwähnten Voraussetzungen, nach denen ich gefragt hatte.
-
Michael E. schrieb:
Jester: Diese Spitzfindigkeit hätte ich bei meinem Einwand wohl erwähnen sollen. Ich hab mich wörtlich an der Frage orientiert, ob jede optimale Tour überschneidungsfrei ist.
Dann hättest Du das parsen eigentlich schon bei "*die* optimale Lösung" abbrechen müssen. :p