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:
Tour(Point a, Point b, Pointc, Point d) // create a 4 point tour a->b->c->d->a
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 received. 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. Fully document the methods of your Fraction class(javadoc strings are preferred). Please also bring a hard-copy of your Tour.java to lab next week.
Modifications
Tour(Point a, Point b, Point c, Point d) // create a 4 point tour a->b->c->d->aTips
In in = new In ("tsp1000.txt");in.readDouble()in.isEmpty()Submission
Extra