Traveling Salesman Problem (TSP)

[Messoras]

Ich bin verzweifelt :/
In Info machen wir gerade Pathfinding und ich konnte schon stolz den A* Algorythmus aus meinem Spiel vorstellen, aber Dieses TSP ist so dermaßen anstrengend...
Gegeben sind eine beliebige Anzahl von Knoten und die dazwischenliegenden Entfernungen, dabei ist die Dreiecksungleichung (AB <= AC+CB) erfüllt.
Alle Texte dazu sind ziemlich lang, ganzschön kompliziert und ohne Lösung, oder ohne erkennbare Lösung.
Das einzige, was ich dazu erarbeiten und nachvollziehen konnte war die Nearest Neighbour Methode, aber dabei wird soweit ich weiß nicht die kürzeste Route berechnet, vor allem, wenn man nicht weiß welcher Knoten als Startpunnkt gewählt werden soll. Außerdem geht der Rechenaufwand da schon in den x^n(K) Bereich...
Könnt ihr mir weiterhelfen? Was ist die gängigste und einfachste Lösung für das TSP?

Gruß Messoras

 

[stg]

TSP ist NP-vollständig. Was erwartest du nun?

 

[Messoras]

Ist das TSP nicht eigentlich NP-äquivalent? 😉
Also muss ich annehmen, dass es keine Lösung mit (wesentlich) kleinerem Aufwand gibt? :/
Ich denke im Unterricht werden wir ohnehin im Bereich unter 10 Knoten arbeiten, aber gibt es in dem Bereich keinen besseren Algorythmus?

Gruß Messoras

 

[nvidia]

Besser nicht, einfacher schon und optimal bzgl. des kürzesten Weges. Wenn die Probleminstanzen so winzig sind, dann bilde einfach systematisch alle Permutation der Städte und merk dir die Permutation mit der kleinsten Gesamtweglänge. Für 10 Städte sind das um die 3,6 Mio. Permutationen, das sollte noch relativ schnell die Lösung ausspucken. An dieser naiven Lösung kann man auch schön demonstrieren wie schnell die Laufzeit bei noch größeren Instanzen ansteigt und weshalb man heutzutage deshalb oft nur "fast optimale" dafür von der Laufzeit her noch beherrschbare Algorithmen verwendet.

 

[Thallius]

Naja, alle Permutationen muss er nicht berechnen. Wenn er es rekursiv macht (Wovon ich mal ausgehe), kann er sich immer die Länge des bisher kürzesten Weg merken und sobald der neue getestete Weg größer als das bisher kürzeste ist, dann kann er eine Ebene zurück und muss nicht bis zum Ziel durchrechnen. Das dürfte einiges sparen.

Gruß

Claus