​​Lab 4: Traveling Salesperson
​​Bard College – Computer Science – Data Structures
​​
​​In this lab we’ll solve the traveling salesperson problem (well, kinda). More 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:
​​
​​http://www.cs.princeton.edu/courses/archive/spr15/cos126/assignments/tsp.html

​​Modifications

​​No need for the second constructor:
​​       Tour(Point a, Point b, Point c, 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()​ .

​​Tips

​​insertFIFO()​ : before worrying about the heuristics, create a simpler version that insert points in FIFO order (i.e. standard enqueue).  You might even compare the heuristic methods with this one.
​​
​​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()

​​Extra Credit

​​Implement another heuristic

​​Lab 4 Unit Test (Checklist)

  • ​​Did I include the correct comment (name, date, collab statement)
  • ​​Did I download the correct Point class?
  • ​​Did I submit the right files (Tour.java, readme.txt) in a zip file?
  • ​​Don’t worry too much about the readme.txt given lab 5
  • ​​Did I implement the Tour API, including both the nearest neighbor and the smallest increase heuristics?
​​
​​