TSP |
Introduction
The Traveling Salesman Problem (TSP) is simple enough: For a given set of cites, how do you identify the shortest route that will allow you to visit visit each city exactly once? This deceptively simple problem is trivial given a small set of cities, however, as you add more cities the number of possible routes goes through the roof. For instance, a set of 48 cities would require evaluation of a staggering number of possible routes:
129,311,620,755,584,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000
Who cares about traveling salesmen? Do we really need to know how to get a traveling salesman to our door in the shortest time? No, but generic forms of the TSP have been used in designing circuit boards, reducing waste of raw materials (i.e. lumber or sheet metal) in manufacturing, analyzing crystal structures, scheduling, and much more.
An efficient general solution has not been found. The TSP project is undertaking the arduous task of using the brute force method to find an optimal solution to a 48 city TSP (ie, trying all possible routes one at a time). Once the optimal path(s) is/are known, evaluation of other algorithms can begin. The final step for the TSP will be to determine if a combination of algorithms can produce results more quickly.
Contents | |
Videos
Science
[The Science section might (or might not) be divided into two parts: {1} general discussion of the field, and then {2} a discussion of the project's specific endeavor. For instance, in LHC@home, we might have {1} "Science of the Large Hardon Collider" and then {2} "Science of LHC@home"
The above is desirable, because in most cases, the field of research is really fascinating, and presenting this in broad terms-- outlining the big questions-- can make it easier to understand the particulars of the project and why it is important. ]
Results
[Where known, we should attempt to keep track of each project's publications. A good list to draw from is here. ]
Links of Interest
[Why recreate the wheel; there are lots of great sources out there.; a good list of sources can be really useful to the reader.]
TSP In the Classroom
[For each project, please add a "[Projectname] in the Classroom" section-- with a link to Volunteer Computing In the Classroom and an article named "[Projectname] in the Classroom". (Then please add "[Projectname] in the Classroom" to the list on the main Education page.)]
Categories: Projects