The Solution


Calculating the distance between points is easy. Assuming you can only follow roads, tracks or open terrain, there are only a finite number of ways to get from A to B. There are simple algorithms which quickly calulate the best roads to use. The one I have used is called Dijkstra's algorithm

Returning to the 30 points, many of the point connections would lead to crossing from one side of the map to the other. It is therefore reasonable to eliminate many of these options hopefully leaving us with what is known as a 'sparse matrix' of possible connections (so there are less conneections than points). It's then just a matter of checking all the possible options.

I have written a program in Python which enables me to draw the streets from the maps, add elevation to each point, compute the Jijkstra's algorithm, connect sensible points then use Parallel computing to process a 'brute force' solution to our TSP.




Email Alerts

Sign up for email notification of new solutions
Here