Starter code for CSE 101 implementation project in Winter 2015. Students will implement MST, Eulerian tour and minimum-weight matching of the MST for Euclidean Traveling Salesman Problem. This project should be done alone and all code MUST be written in C/C++.
Project Specification
• Point generation code must accept parameters H, W, N, and generate N points from a uniform distribution in the rectangle with lower-left and upper-right corners (0, 0) and (W, H), respectively. W, H, N will be positive integers. W ∗ H ≥ N and N can be as large as 1.0e4.
• MST calculation code will accept a planar pointset (in a prescribed file format). The cost of edge is calculated by Euclidean distance. You can use any algorithm for constructing MST.
• TSP2 calculation code will shortcut the Eulerian tour generated by DFS of the MST of the pointset, and return the resulting heuristic TSP cost, CT SP 2.
• TSP1p5 calculation code will perform minimum-weight matching of the odd-degree vertices of the MST of the pointset, shortcut a Eulerian tour of the union of the edges of the matching and the MST of the pointset, and return the resulting heuristic TSP cost, CT SP 1p5. Please refer to the 1.5-approximation overview at this link[click]
• Write code for the 2OPT-E local improvement heuristic, which iteratively finds a pair of edges to remove from the current TSP tour, such that reconnecting the remaining paths back into a cycle (i.e., a new TSP tour of the same N points) has reduced cost. The 2OPT-E heuristic terminates when no pair of edges can be found to further reduce the TSP cost.
• Write code for the 2OPT-P local improvement heuristic, which iteratively finds a pair of points whose positions in the current TSP tour can be swapped, such that the new tour (i.e., a new TSP tour of the same N points) has reduced cost. The 2OPT-P heuristic terminates when no pair of points can be found to further reduce the TSP cost.
How to execute:
./make
./TSP