Quelltext der Seite Problem des Handlungsreisenden

==== Metrisches TSP ====
Ein symmetrisches TSP heißt ''metrisch'', wenn zusätzlich seine Kantenlängen die [[Dreiecksungleichung]] erfüllen. Anschaulich bedeutet dies, dass sich Umwege nicht lohnen, weil die direkte Verbindung von <math>i</math> nach <math>j</math> nie länger ist als der Weg von <math>i</math> nach <math>j</math> über einen dritten Knoten <math>k</math>:

: <math>c_{ij} \le c_{ik} + c_{kj}</math>

Solche Kantenlängen definieren eine [[Metrischer Raum#Pseudometrik|Pseudometrik]] auf der Knotenmenge, also ein Entfernungsmaß, das die intuitiv von einem Abstand erwarteten Bedingungen erfüllt. Mehrere in der Praxis häufig auftretende [[Distanzfunktion]]en sind Pseudometriken, erfüllen also die Dreiecksungleichung:

* die [[Euklidischer Abstand|euklidische Metrik]] des ''euklidischen TSP'',
* die [[Manhattan-Metrik]] (auch City-Block-Metrik) des ''rektilinearen TSP'', bei der die Distanz zwischen zwei Knoten eines gitterförmigen Graphen (wie dem Straßennetz von Manhattan) die Summe der Entfernungen in x- und y-Richtung ist,
* oder die [[Metrischer Raum|Maximums-Metrik]], bei der die Distanz zwischen zwei Knoten eines gitterförmigen Graphen das Maximum der Entfernungen in x- bzw. y-Richtung ist.

Die letzten beiden Metriken finden beispielsweise Anwendung beim Bohren von [[Leiterplatte]]n, wo ein Bohrer, der eine vorgegebene Menge von Löchern in möglichst kurzer Zeit abarbeiten muss, in beide Dimensionen unabhängig bewegt werden kann, um von einem Loch zum nächsten zu gelangen. Die Manhattan-Metrik entspricht dem Fall, dass die Bewegung in beide Richtungen nacheinander erfolgt, während bei der Maximum-Metrik beide Bewegungen gleichzeitig erfolgen und die Gesamtzeit von der jeweils längeren Strecke in x- bzw. y-Richtung bestimmt wird.

Ein nicht-metrisches TSP kann zum Beispiel vorliegen, wenn die Dauer einer Reise minimiert werden soll und auf verschiedenen Strecken verschiedene Verkehrsmittel möglich sind. Dabei kann ein Umweg mit dem Flugzeug schneller sein als die direkte Verbindung mit dem Auto.

Falls es im praktischen Planungsproblem zulässig ist, Orte mehrfach zu besuchen, lässt sich das symmetrische TSP auf das metrische TSP reduzieren. Dazu wird das Rundreiseproblem auf dem sogenannten ''Distanzgraphen'' betrachtet. Dieser hat dieselbe Knotenmenge wie der ursprüngliche Graph und ist ebenfalls [[Vollständiger Graph|vollständig]]. Die Kantenlängen <math>c_{ij}</math> zwischen zwei Knoten <math>i</math> und <math>j</math> im Distanzgraphen entsprechen der Länge eines kürzesten <math>i</math>-<math>j</math>-Weges zwischen diesen Knoten im ursprünglichen Graphen. Die so definierten Werte <math>c_{ij}</math> erfüllen immer die Dreiecksungleichung, und jede Tour im Distanzgraphen entspricht einer Tour mit möglichen Knotenwiederholungen im ursprünglichen Graphen.
<!-- Mit Bild veranschaulichen? -->

Sollte es ''nicht'' zulässig sein, Orte mehrfach zu besuchen, lässt sich ein beliebiges TSP ebenfalls auf ein metrisches TSP reduzieren, indem man jede Kantenlänge um dieselbe nichtnegative Konstante vergrößert: Es kann ja immer eine Konstante <math>q\ge0</math> gefunden werden, die groß genug ist, um <math>(c_{ij}+q) \le (c_{ik}+q) + (c_{kj}+q)</math> für alle Knotentripel zu erfüllen. Bei Heuristiken, die eine maximale Abweichung vom Optimum gewährleisten, vergrößert dieses Vorgehen natürlich den Abweichungsfaktor der ursprünglichen Aufgabe.