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 next week. This week we are focused on implementing the heuristics in Tour.java; next week, we’ll move onto performance comparison.
Tips
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 calculate the distance method.
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.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 next week.
Modifications
Tips
In in = new In ("tsp1000.txt");in.readDouble()in.isEmpty()Submission
Bonus