Use the cluster to time how long it takes to solve the travelling salesperson problem using different numbers of locations.

Cluster for 5 locations :

Cluster for 9 locations :

Using the formula [(N 1) (N 2) 3 2 1], calculate the total number of routes for both five and nine locations.

1. Time how long it takes to find the shortest and longest routes for five locations using 16 cores.

2. Using this time and your calculation of the total number of routes, estimate how long it will take the cluster to find the shortest route for nine locations using 16 cores.

3. Check your estimate by running the program on the cluster. Were you right? If you were right, what was your reasoning? If not, why do you think you mis-estimated?

Table 1 Timings for different variations of the travelling salesperson problem Starting timing on the Raspberry Pi cluster > Minimum distance is 25 > On route [13254] > Maximum distance is 49 > On route [1 2 2 4 4 3 5 > The Raspberry Pi cluster took 0.5845 seconds > Starting timing on an individual Raspberry Pi > Minimum distance is 25 > On route (1,3,2,5,4) > Maximum distance is 49 > On route (1,2,4,3,5) > An individual Raspberry Pi took 0.00674 seconds Starting timing on the Raspberry Pi cluster > Minimum distance is 33 > Maximum distance is 104 > On route [1 28793564 ] > The Raspberry Pi cluster took 9.50595 seconds > Starting timing on an individual Raspberry Pi > Minimum distance is 33 > On route (1,3,6,7,2,5,8,4,9) > Maximum distance is 104 > On route (1,2,8,7,9,3,5,6,4)