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.
Apllications available are:
- Microsoft Windows (98 or later) running on an Intel x86-compatible CPU
- Microsoft Windows running on an AMD x86_64 or Intel EM64T CPU
- Linux running on an Intel x86-compatible CPU
- Linux running on an AMD x86_64 or Intel EM64T CPU
- Mac OS 10.4 or later running on Intel
- Linux running crunch3r's boxes EV67 and DEC