Sunday October 24, 2010
The Traveling Salesperson (TSP) is a classic example of NPcompleteness. This simple problem has applications in such diverse fields as shipping, circuit design, and DNA sequencing. It is one of the most wellstudied 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.
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:
Serial_Route_Starter
—
TSP Starter Code
©19942014

Shodor

Privacy Policy

NSDL

XSEDE

Blue Waters

ACM SIGHPC





Not Logged In. Login