Explore brute force solutions to the TSP. First, this will represent TSP tours using a 2D array
Question:
Explore brute force solutions to the TSP. First, this will represent TSP tours using a 2D array of points (x and y values) such as the following:
const int n = 5; double tour[ n ][ 2 ] = { { 0.631980, 0.7925150 }, { 0.489609, 0.2541210 }, { 0.975682, 0.0843492 }, { 0.414236, 0.6135660 }, { 0.338385, 0.0315477 } };
Use the sum of the distances between the points in the tour as the cost function. This sum also includes the distance from the last point back to the first point. For the above tour, the cost is 3.2459. Note the a particular problem may have more than one solution, and even if there is only one solution, the representation may not be unique.
The following illustrates the latter.
0: (0.414236, 0.6135660) 1: (0.489609, 0.2541210) 2: (0.338385, 0.0315477) 3: (0.975682, 0.0843492) 4: (0.631980, 0.7925150) best cost = 2.34484 0: (0.489609, 0.2541210) 1: (0.414236, 0.6135660) 2: (0.631980, 0.7925150) 3: (0.975682, 0.0843492) 4: (0.338385, 0.0315477) another best cost = 2.34484
The program will consist of 3 modules (files): main.cpp, utes.cpp (for utilities), and brutes.cpp. Use the definitions that appear below. The main should thoroughly test the components in utes.cpp and brutes.cpp.
// file : main.cpp// author: ...// desc. : this file initializes (seeds) our random number generator.// it also contains code that exercises/tests the following // functions:// copy, cost, print, randomize_in_place,// bruteForceRandom, bruteForce5Loops#include
Try to create a version of bruteForce5Loops that works n = anything (not fixed at 5)!