Explore brute force solutions to the TSP. First, 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 #include #include

using namespace std;

extern void copy ( double A[][2], int n, double B[][2] ); extern double cost ( double A[][2], int n ); extern void print ( double A[][2], int n ); extern long fact ( long n ); extern long factRecursive ( long n ); extern void randomize_in_place ( double A[][2], int n );

extern void bruteForceRandom ( double A[][2], int n, long repeats ); extern long bruteForce5Loops ( double A[][2], int n );

extern mt19937_64 g; //our random number generator //--------------------------------------------------------------------------- int main ( int argc, char* argv[] ) { g.seed( time(NULL) );

//add whatever test your wish here. here are some examples. 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 } };

randomize_in_place( tour, n ); printf( "before (cost=%f) : ", cost(tour,n) ); print( tour, n ); bruteForce5Loops( tour, n ); printf( "after (cost=%f) : ", cost(tour,n) ); print( tour, n );

randomize_in_place( tour, n ); printf( "before (cost=%f) : ", cost(tour,n) ); print( tour, n ); bruteForceRandom( tour, n, 240 ); printf( "after (cost=%f) : ", cost(tour,n) ); print( tour, n );

return 0; } //---------------------------------------------------------------------------

________________________________________

//file : utes.cpp //author: ... //desc. : this file contains the following utility functions: // copy, cost, fact, factRecursive, print, and randomize_in_place. #include #include #include #include #include

using namespace std;

mt19937_64 g; //our random number generator //--------------------------------------------------------------------------- //this function copies the tour in src (of length n) into tour dst (also of // length n. the caller must properly init and allocate the tours. this is // useful for keeping a copy of the best so far. void copy ( double dst[][2], int n, double src[][2] ) { cout << "todo" << endl; } //--------------------------------------------------------------------------- //this functions returns the cost of tour A (of length n). // don't forget that the distance from the end back to the start must be // included. double cost ( double A[][2], int n ) { cout << "todo" << endl;

return 0; } //--------------------------------------------------------------------------- //non-recursive version of n factorial. n! is returned. long fact ( long n ) { cout << "todo" << endl;

return 0; } //--------------------------------------------------------------------------- //recursive version of n factorial. n! is returned. long factRecursive ( long n ) { cout << "todo" << endl;

return 0; } //--------------------------------------------------------------------------- //pretty print (to cout or stdout) tour A of length n. void print ( double A[][2], int n ) { cout << "todo" << endl; } //--------------------------------------------------------------------------- //randomize tour A of length n in place. //Do not use shuffle or any other built-in function. void randomize_in_place ( double A[][2], int n ) { cout << "todo" << endl; } //---------------------------------------------------------------------------

________________________________________

//file : brutes.cpp //author: ... //desc. : this file contains the functions bruteForceRandom, and bruteForce5Loops. #include #include

using namespace std;

extern void copy ( double A[][2], int n, double B[][2] ); extern double cost ( double A[][2], int n ); extern void print ( double A[][2], int n ); extern void randomize_in_place ( double A[][2], int n ); //--------------------------------------------------------------------------- //this function (hopefully - no guarantees) finds the optimal solution by // repeatedly calling randomize_in_place while keeping track of the best // solution. // // repeats is the number of repeats. // A is the initial tour and n is its length. // this function returns the best solution in A. // note: to dynamically allocate 2D arrays, user the following: // double (*tmp)[2] = new double[n][2]; //tmp is a ptr to pairs of doubles void bruteForceRandom ( double A[][2], int n, long repeats ) { cout << "todo" << endl; } //--------------------------------------------------------------------------- //this function generates (exactly) all permutations of the tour A. // your solution should be hard-coded to only work for an array of length 5. // the optimal tour should be returned in A. the number of permutations // tested should be returned. long bruteForce5Loops ( double A[][2], int n ) { assert( n == 5 ); //only works for n=5 cout << "todo" << endl;

return 0; } //---------------------------------------------------------------------------