jeudi 26 février 2015
Traveling Salesman Problem (TSP)
Posted on 09:58 by verona
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
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
Traveling Salesman Problem (TSP)
Categories: Traveling Salesman Problem (TSP)
Inscription à :
Publier les commentaires (Atom)
0 commentaires:
Enregistrer un commentaire