Bard College – Computer Science – Data Structures
In this lab we’ll solve the traveling salesperson problem(well, kinda). Specifically, we’ll develop linked-list implementations of a graph tour. Finding an optimal tour of a graph is a big deal.
Again this week, we will follow our textbook authors’ project pretty closely:
You will need to import edu.princeton.cs.algs4.* at the top of your java files.
No need for the second constructor: Tour(Point a, Point b, Point c, Point d)
NearestInsertion.java and SmallestInsertion.java calls Tour’s length() method, this is a bug, they should instead call distance() .
We’ll save the Analysis section for later. In this lab we are focused on implementing the heuristics in Tour.java; later, we’ll move onto performance comparison.
Tips
First compile and run Point to make sure your data files are in the right place.
insert(): before worrying about the heuristics, create a simpler version of Tour that simply inserts points into the tour in the order they are inputted(FIFO or LIFO). Then complete the show and distance methods.
Queue is a good place to look for inspiration for Tour; SmallestInsertion is a good test client.
StdIn Woes with IntelliJ
IntelliJ users can manually read in the file rather than using file redirection(< tsp1000.txt ):
In in = new In ("tsp1000.txt");
in.isEmpty()
in.readDouble()
in.isEmpty()
Submission
Submit your Tour.java file in a zipped folder named cmsc201-lab4-lastname-firstname . Be sure to include your name, date, email, lab description and collaboration statement. Please also bring a hard-copy of your Tour.java to lab(in two weeks).
Modifications
Tips
In in = new In ("tsp1000.txt");in.isEmpty()in.readDouble()in.isEmpty()Submission
Bonus