TSP - Wir haben ein Team hier!
- Ersteller indiana_74
- Erstellt am
indiana_74
Moderator
☆☆☆☆☆☆
About TSP
The Traveling Salesman Problem (TSP) is not hard to explain. For a given set of cites, visit each city once (once and only once) and minimize the distance you travel. This deceptively simple problem is trivial given a small set of cities, however, as you add more cities the number of possible paths goes through the roof. It should come as no surprise that the TSP is classified as an NP-Hard problem, with the number of Hamiltonian paths being equal to n!/2 where n is equal to the number of cities in the problem.
An efficient general solution has not been found. Mathematicians have decided that the best case scenario is an algorithm that has a polynomial variation with respect to the number of cites. The best solutions to date vary exponentially with respect to the number of cites. This is where the bonic project TSP comes in. The TSP project is under taking the arduous task of using the brute force method to find an optimal solution to a 48 city TSP. Once the optimal path(s) is/are known evaluation of other algorithms can begin. Future algorithms include genetic algorithms, repetitive nearest neighbor, simulated annealing and ant colony optimization.
TSP is based at The American Samoa Habiscus House.
Die Projekt Url lautet: http://bob.myisland.as/tsp/
Unser Team findet ihr hier: http://bob.myisland.as/tsp/team_display.php?teamid=272
Derzeit sind wir hier irgendwo auf Platz 80 bis 100 zu finden!
Unser Freunde von SETI.USA belegen zur Zeit den zweiten Platz
Das geht ja nun mal gar nicht
The Traveling Salesman Problem (TSP) is not hard to explain. For a given set of cites, visit each city once (once and only once) and minimize the distance you travel. This deceptively simple problem is trivial given a small set of cities, however, as you add more cities the number of possible paths goes through the roof. It should come as no surprise that the TSP is classified as an NP-Hard problem, with the number of Hamiltonian paths being equal to n!/2 where n is equal to the number of cities in the problem.
An efficient general solution has not been found. Mathematicians have decided that the best case scenario is an algorithm that has a polynomial variation with respect to the number of cites. The best solutions to date vary exponentially with respect to the number of cites. This is where the bonic project TSP comes in. The TSP project is under taking the arduous task of using the brute force method to find an optimal solution to a 48 city TSP. Once the optimal path(s) is/are known evaluation of other algorithms can begin. Future algorithms include genetic algorithms, repetitive nearest neighbor, simulated annealing and ant colony optimization.
TSP is based at The American Samoa Habiscus House.
Die Projekt Url lautet: http://bob.myisland.as/tsp/
Unser Team findet ihr hier: http://bob.myisland.as/tsp/team_display.php?teamid=272
Derzeit sind wir hier irgendwo auf Platz 80 bis 100 zu finden!
Unser Freunde von SETI.USA belegen zur Zeit den zweiten Platz
Das geht ja nun mal gar nicht
Zuletzt bearbeitet:
Kleine Korrektur: Es ist offenbar kein deutsches Projekt. Ich habe mich bisher auch von der RKN-Wiki fehlleiten lassen. Nach einigen Nachforschungen kann ich sagen, dass das Projekt mit sehr hoher Wahrscheinlichkeit wirklich in Amerikanisch-Samoa beheimatet ist.
