Sunday October 24, 2010
The Traveling Salesperson (TSP) is a classic example of NP-completeness. This simple problem has applications in such diverse fields as shipping, circuit design, and DNA sequencing. It is one of the most well-studied optimization problems. Optimize and possibly parallelize a program for solving TSP.
Given a set of cities and the coordinates or distances between pairs of cities, find the shortest path through the cities which visits each city exactly once.

A very simplistic, serial, inefficient TSP solver is attached. Your task is to improve this solver any way you like. It is recommended that you investigate both parallelism and improved algorithms. The inputs will have metric, Euclidean distances.

-Some information on this problem can be found in this Wikipedia article.

-An example web application that uses data from Google can be found here.

-As with many of the previous challenges, make sure to install the Mersenne Twister random number generator to properly take advantage of the starter code.
Show solution
Challenge Resources:
©1994-2014   |   Shodor   |   Privacy Policy   |   NSDL   |   XSEDE   |   Blue Waters   |   ACM SIGHPC   |   facebook  |   facebook   |   twitter   |   rss   |   youtube Not Logged In. Login