ptsp - preliminary Travelling Salesman Problem

In this exercise, you will explore brute force solutions to the TSP. First, we 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 }

};

As we discussed in class, we will 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

Your program will consist of 3 modules (files): main.cpp, utilities.cpp, and brutes.cpp. Use the definitions that appear below. Your main should thoroughly test the components in utilites.cpp and brutes.cpp. Email your work to me and our wonderful TA with the required subject of DAA grad ptsp.

Here are the required files and methods you must follow:

// file : main.cpp

// author: ...

// desc. : this file defines and initializes (seeds) our random number generator.

// it also contains code that exercises/tests the following functions:

// copy, cost, fact, factRecursive, print, randomize_in_place,

// bruteForce1,

// bruteForce2

#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 void randomize_in_place(double A[][2], int n);

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

extern long bruteForce2(double A[5][2]);

extern mt19937_64 g; //random number generator

//---------------------------------------------------------------------------

int main(int argc, char* argv[]) {

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 }

};

return 0;

}

//file : utilities.cpp

//author: ...

//desc. : this file contains the following utility functions:

// copy, cost, print, and randomize_in_place.

#include

#include

#include

#include

using namespace std;

mt19937_64 g;

//---------------------------------------------------------------------------

//this function copies the tour in B (of length n) into tour A (also of length

// n. the caller must properly init and allocate the tours.

void copy( double A[][ 2 ], int n, double B[][ 2 ] ) {

}

//---------------------------------------------------------------------------

//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 ) {

}

//---------------------------------------------------------------------------

//pretty print (to cout) tour A of length n.

void print ( double A[][ 2 ], int n ) {

}

//---------------------------------------------------------------------------

//randomize tour A of length n in place

void randomize_in_place ( double A[][ 2 ], int n ) {

}

//file : brutes.cpp

//author: ...

//desc. : this file contains the functions bruteForce1, bruteForce2 (grads only),

// and bruteForce3 (optional, extra credit).

#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 randomize_in_place ( double A[][ 2 ], int n );

//---------------------------------------------------------------------------

//this function 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 bruteForce1 ( double A[][ 2 ], int n, long repeats ) {

}

//---------------------------------------------------------------------------

//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 bruteForce2 ( double A[ 5 ][ 2 ] ) {

}