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 #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) : \n", cost(tour,n) );    print( tour, n );    bruteForce5Loops( tour, n );    printf( "after (cost=%f) : \n", cost(tour,n) );    print( tour, n );    randomize_in_place( tour, n );    printf( "before (cost=%f) : \n", cost(tour,n) );    print( tour, n );    bruteForceRandom( tour, n, 240 );    printf( "after (cost=%f) : \n", 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 placevoid 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 doublesvoid 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;}//---------------------------------------------------------------------------

Try to create a version of bruteForce5Loops that works n = anything (not fixed at 5)!