Sehr geehrte Damen und Herren,
Traveling Salesman ist ein Problem in der Informatik, welches für den Menschen leicht lösbar, jedoch für die Maschine schwer ist. Natürlich nur bei beschränkter Größe. Bei großer Größe, ist es auch für den Menschen schwer.
Das Problem ist :
Finde den kürzesten Rundweg für gegebene Punkte, welche alle miteinander auf direktem Weg erreichbar sind.
Was kann man damit machen?
Man kann natürlich kürzeste round-trips auf 2D Ebenen bestimmen.
Es geht jedoch auch darum, alles zu sortieren, was zwei orthogonale Eigenschaften hat.
Nicht dazu gehörend ist zum Beispiel, die Dichte. Sie hat das Volumen und das Gewicht als Eigenschaften. Jedoch ist sie schon durch den Bruch dieser Komponenten definiert und daher nicht wirklich zweidimensional.
Kartesische Koordinaten lassen sich hingegen nicht einfach durch einen Bruch eindeutig zuweisen.
Das TSP passt also auf zwei Eigenschaften, welche nicht per Definition durch einen Bruch definiert sind.
Typische Beispiele
Leider waren die drei typischsten Beispiele weniger passend für eine Anwendung des TSPs. Hier die Begründungen.
Soziale Netzwerke :
Sind eher chaotisch als strukturiert und daher aussagenlos trotz Anwendung eines TSPs.
Hyperlink Rankings :
Daten sind statisch, da keine Erhebungen der Klicks auf einen Link ausgeführt werden.
Ein round-trip auf diesem Netzwerk ist weniger klar zu interpretieren.
Daher scheint es weniger sinnvoll als TSP Beispiel.
Im Prinzip reicht es aus, die Anzahl der Verlinkungen zu wählen, welche weit über das Internet verteilt seien sollten und den Ort, so wie die Zeit, dazu zu nehmen, um ein aussagekräftiges Ranking zu erhalten.
Last but not least, shortest path:
Unter kürzestem Weg wird oft schnellster Weg verstanden.
Egal welches Kriterium betrachtet wird, die Vorgehensweise ist oft eine Rasterpyramide. D.h. es werden erstmal die groben Punkte verbunden und dann im Detail die Strecken gewählt.
Alternativ ist eine rekursive Suche möglich.
Shortest path, ist kein round-trip und nicht jeder Punkt ist auf direktem Weg mit jedem anderen zu erreichen. Daher ist es nicht so komplex wie das TSP. Somit schnell genug mit den oben genannten Methoden lösbar.
Es sieht so aus, als ob ich, bis auf ein Beispiel, kein passendes weiteres Beispiel finde.
Hilfe ist willkommen, in den Kommentaren.
Das eine Beispiel, das ich habe, ist das Dreikörperproblem
Dazu mehr in einem anderen Post.
Mit freundlichen Grüßen Sebastian
