The simulated annealing solution to the TSP requires that we be able to generate random changes in the list of cities in a tour. In a paper by Lin, rearrangements such as invert and translate were found to be very effective. Using the code template below, add the following three functions to your existing utes.cpp file. void swap_any_two ( double A[][2], int n ) void invert ( double A[][2], int n, int start, int len ) void translate ( double A[][2], int n, int src, int len, int dst ) Check all arguments given to your function. If any are erroneous, DO NOT abort (or throw exceptions or allow array bounds exceptions. Simply return from the function without performing the operation. //--------------------------------------------------------------------------- /**(add to your existing utes.cpp file.) * pick any two (they must be different) and swap them. * * ex. before A = { {1,5}, {2,7}, {9,4}, {12,7}, {2,8}, {13,3}, {6,16}, {5,25} } * swap_any_two( A, 8 ); * after A = { {1,5}, {2,7}, {5,25}, {12,7}, {2,8}, {13,3}, {6,16}, {9,4} } * * @param A is the list of locations (x,y) of the cities in the current tour. * @param n is the number of cities in A. */ void swap_any_two ( double A[][2], int n ) {

//todo: add your code here

} //--------------------------------------------------------------------------- /**(add to your existing utes.cpp file.) * This function performs an invert (or inversion or flip). * * double A[][2] = { {0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}, {7,7} }; * call invert( A, 8, 3, 4 ): A B C D * after: { {0,0}, {1,1}, {2,2}, {6,6}, {5,5}, {4,4}, {3,3}, {7,7} } * D C B A * * for full credit, this function should be able to handle inverts that extend * beyond the end of the array and wrap around to the beginning. for example, * double X[][2] = { {0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}, {7,7} }; * C D A B * call invert( X, 8, 6, 4 ): * after: { {7,7}, {6,6}, {2,2}, {3,3}, {4,4}, {5,5}, {1,1}, {0,0} }; * B A D C * generous partial credit will be given for implementing the core/basic * functionality. * * @param A is the list of locations (x,y) of the cities in the current tour. * @param n is the number of cities in A. * @param start is the index of the beginning of the section to be inverted. * @param len is the length of the segment to invert. */ void invert ( double A[][2], int n, int start, int len ) {

//todo: add your code here

} //--------------------------------------------------------------------------- /**add to your existing utes.cpp file. * translate moves a sequence around. * * double A[][2] = { {0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}, {7,7} }; * ^dst A B C * call translate( A, 8, 5, 3, 1 ): * after: { {0,0}, {5,5}, {6,6}, {7,7}, {1,1}, {2,2}, {3,3}, {4,4} }; * A B C * * for full credit, this function should be able to handle translations that * extend beyond the end of the array and wrap around to the beginning. * generous partial credit will be given for implementing the core/basic * functionality. * * @param A is the list of locations (x,y) of the cities in the current tour. * @param n is the number of cities in A. * @param src is the index of the beginning of the section to be translated (moved). * @param len is the length of the segment to translate. * @param dst is the index of the beginning of the target of moving. */ void translate ( double A[][2], int n, int src, int len, int dst ) {

//todo: add your code here

} //---------------------------------------------------------------------------