Assignment 4
Type: Group Assignment
Due: by 9:30 PM on Tuesday, October 2, 2018
Goals
The goal of this assignment is to learn about and get some practice with the Linked List data structure, and traversing sequences of nodes. You will also get to learn a bit about a very famous problem in computer science!
Note: There is a lot of information below! Most of it is explaining the context of the assignment, how to check your code, and files that you will be using but won’t need to implement. All you will need to do for this assignment is implement the Tour.java
class. The other files are scaffolding to make the rest of the assignment work.
This is a partner assignment. You should work with the partners that I assigned to you in class.
Pair Programming Guidelines
You should always be working with your partner. You may NOT divide up the work and complete the parts independently. All work you submit must be fully authored by both you and your partner. I also suggest that you work on one computer and take turns using the keyboard.
Please adhere to the guidelines in the code of conduct we wrote as a class. Here are a few especially encouraged guidelines:
- Set a timer for 10-15 minutes and switch who is using the keyboard.
- If you are currently the driver (i.e. the one using the keyboard), practice talking out loud what you are thinking as you are typing.
- If you are currently the navigator (i.e. the one not using the keyboard), pay close attention to what the driver is doing, offer feedback, and stay involved throughout that time.
- Ask each other questions. If you’re confused about something your partner is doing, let them know and ask them if they could explain or clarify their idea.
Background
Traveling Salesman Problem
In this assignment we’ll be exploring some approximate solutions to a well known problem in computer science called the traveling salesperson problem (TSP). The idea behind this problem is as follows: you are given N
points on a map (so each point has an x-coordinate and a y-coordinate) and you want to find a route to visit all of the points on the map (and arrive back where you started) while keeping the total distance traveled as small as possible.
There are many places in the real world where the TSP comes up: How does UPS decide the routes that it’s trucks take? What is the most efficient way for a machine to drill a set a holes in a circuit board? Some important problems in bioinformatics (genome assembly) can be transformed into instances of the TSP. You’ll probably see the TSP in future CS classes.
Greedy Heuristics
The traveling salesperson problem is a notoriously difficult combinatorial optimization problem, In principle, one can enumerate all possible tours, but, in practice, the number of tours is so staggeringly large (roughly N
factorial where N
is the number of stops on the tour) that this approach is useless. For large N
, no one knows an efficient method that can find the shortest possible tour for any given set of points. However, many methods have been studied that seem to work well in practice, even though they are not guaranteed to produce the best possible tour. Such methods are called heuristics.
Your main task is to implement the nearest neighbor and smallest increase insertion heuristics for building a tour incrementally.
Nearest Neighbor Heuristic
- Initialize your route as a one-point tour (from the first point back to itself).
- For each remaining point, add it to the current tour immediately after the point to which it is closest. (If there is more than one point to which it is closest, insert it after the first such point you discover.)
This means that for each point you add, you will search through the points that are already in the tour, looking for the closest one to the one you will be adding.
Smallest Increase Heuristic
- Start with an empty tour.
- Add the first point (so that the tour now goes from the first point back to itself).
- For each remaining point, add it to the position where it results in the least possible increase in total tour length. (If there is more than one such position, add it to the first such place you discover.)
This means that for each point you add, you will search through each possible place it can go, checking how much adding the point to that position increases the total length of the tour.
Your Assignment
We have provided you with several auxiliary classes that will make your job easier in the hw4.zip file we provide you with. The only place that you will have to add code is in the file Tour.java
. Inside this file we have already defined the nested class Node
for you to use. Also take a look at the code in the main()
method which you might find useful for testing out your code. Feel free to take a look at the other files if you would like, but you don’t need to understand them. You should not modify any of the files except for Tour.java
.
Point Class
You will use the Point
object extensively in the code you write. You may look at the code in Point.java
, but all you really need to know to be a USER of this class is the Point
ADT:
Method and Parameters | Return Type | Description |
---|---|---|
Point(double x, double y) | Point | Creates a Point object with (x,y) coordinates. |
toString() | String | Returns a string representation of a Point object. |
draw() | void | Draws a point using standard draw |
drawTo(Point b) | void | Draws a line segment from the Point calling the method to Point b. |
distanceTo(Point b) | double | Returns Euclidean distance between the Point calling the method and Point b. |
Tour Class
The Tour.java
class that you will implement will have the following methods (think of this at the Tour ADT). See a later section of this document for additional notes and comments on all methods.
Method and Parameters | Return Type | Description |
---|---|---|
Tour() | Tour | Creates an empty tour (has no stops). |
toString() | String | Returns a description of the tour as a nicely formatted string. |
draw() | void | Draws the tour |
size() | int | Returns the number of points, or stops in the tour. |
distance() | double | Returns the total distance in the tour. |
insertNearest(Point p) | void | Inserts p into the tour using the “nearest neighbor” heuristic. |
insertSmallest(Point p) | void | Inserts p into the tour using the “smallest insertion” heuristic. |
You will implement the Tour
class as a single linked list underneath the hood. You will start with the code that I have provided you in Tour.java
. Just to be clear, you MUST implement your own single linked list to receive credit for this assignment; you may not use any similar class provided by Java.
Hints and Additional Method Details
Here is some additional information about the methods we are asking you to implement.
-
Tour()
: Initialize head node of a linked list and any other variables you think will be useful. We’ve implemented a version of this constructor for you. Feel free to modify if you decide to add additional instance variables. -
String toString()
: Create an empty String, loop through all nodes of the linked list and add a description of each underlyingPoint
(as aString
) to the overallString
. This will be useful for debugging, as well as outputting final solutions to the tour. Note: You may want to make use of the toString() method from the Point class. -
void draw()
: Loop through all of the nodes in the tour’s linked list and draw eachPoint
object, followed by a line from thatPoint
to the nextPoint
. Do this for all nodes except for the last node in the list, for that node draw a line from the lastPoint
to the first (or head)Point
. Make sure to use thedraw()
anddrawTo()
methods in thePoint
class. Note: You DO NOT need to implement any graphics code! All you need to do is call thedraw()
anddrawTo
methods that are already implemented for thePoint
class. -
int size()
: Return the size of the linked list (in terms of nodes). In order to be more efficient, make sure to keep track of this value rather than re-computing this value whenever this method is called. -
double distance()
: Start with a distance of 0. Loop through all nodes of your linked list and compute the distance from eachPoint
to the nextPoint
, add this distance to your total distance. When you get to the last Node in your list, add the distance from thisPoint
to the firstPoint
. Make sure to use thedistanceTo(Point b)
method from thePoint
class. -
void insertNearest(Point p)
: Note: It may be helpful, from a debugging perspective, to create an initial version of this method that just adds p to the end of the Tour, so you can test the above methods before starting to implement this one. Once you’re ready to implement the true heuristic, start with some local variableminDist = Double.MAX_VALUE
that keeps track of the minimum distance found thus far betweenPoint p
and the nodes in the linked list. Loop through all Nodes of the linked list and compute the distance from the underlyingPoint
object top
. If the distance is less thanminDist
make that distance the newminDist
and save a reference to the current node. After your loop finishes, insert a new node forPoint p
after the saved node that had the minimum distance top
. -
void insertSmallest(Point p)
: This is the most difficult of all the the methods to implement. Make sure you implement and test all other methods first, before starting on this one. The idea with this method is that we will search through all the potential “slots” in which we could insertPoint p
, looking for the slot in which insertingp
would have the smallest increase in the overall distance of the tour. Thankfully, we do not need to loop through the entire list to check the effect of inserting into each slot. If, for instance, we want to know the effect of addingPoint p
between twoPoint
s calleda
andb
, we just need to compute the difference betweena.distanceTo(b)
(i.e., the distance withoutp
inserted here) anda.distanceTo(p) + p.distanceTo(b)
(i.e., the distance withp
inserted here). After looping through the current tour to see which slot would have the smallest increase in distance ifp
were inserted, putp
into that slot. -
main()
: We also include some code in this method to help you with debugging of your code. In particular, we suggest you test each function as you write it and that you implementtoString()
first as it will be useful for debugging other methods. You may certainly add and modify code in thismain()
method as you see fit.
Running Code on Input Files
The input file format will begin with two integers w
and h
, followed by pairs of real-valued x and y coordinates. All x coordinates will be real numbers between 0 and w
; all y coordinates will be real valued numbers between 0 and h
. As an example, the file tsp3.txt
could contain the following data:
600 400
532.6531 247.7551
93.0612 393.6735
565.5102 290.0000
10.0000 10.0000
The zip file hw4.zip includes several example input files, or you can define your own. Below you will find some information about the expected output for these input files to help you with debugging your own code.
Insert Nearest Solution to tsp10.txt
$ java NearestInsertion tsp10.txt
Tour distance = 1566.1363051360363
Number of points = 10
(110.0, 225.0)
(161.0, 280.0)
(157.0, 443.0)
(283.0, 379.0)
(306.0, 360.0)
(325.0, 554.0)
(397.0, 566.0)
(490.0, 285.0)
(552.0, 199.0)
(343.0, 110.0)
Insert Smallest Solution to tsp10.txt
$ java SmallestInsertion tsp10.txt
Tour distance = 1655.7461857661865
Number of points = 10
(110.0, 225.0)
(283.0, 379.0)
(306.0, 360.0)
(343.0, 110.0)
(552.0, 199.0)
(490.0, 285.0)
(397.0, 566.0)
(325.0, 554.0)
(157.0, 443.0)
(161.0, 280.0)
Insert Nearest Solution to usa13509.txt
$ java NearestInsertion usa13509.txt
Tour distance = 77449.97941714071
Number of points = 13509
...
See figure below for a visual representation of the solution.
Insert Smallest Solution to usa13509.txt
$ java SmallestInsertion usa13509.txt
Tour distance = 45074.77692017051
Number of points = 13509
...
See figure below for a visual representation of the solution.
Note: It should take less than a minute (probably even faster than that) to run through the example with 13,509 points (unless you are animating the results). If your code is taking much longer, try to narrow down what part of the code is taking the longest. Turning in an efficient solution will be part of what we consider when grading your code.
Submission and Grading
You’ll submit all your files to your Hand-in
directory under a folder named assignment4
. Only one partner from each pair needs to submit the assignment.
This assignment is worth 20 points. Below is a partial list of the things that we’ll look for when evaluating your work.
- Do you implement all of the requested methods as they are described? We’ll test this out by running your various methods on different test cases. We suggest you focus on
insertNearest
before attemptinginsertSmallest
, which is significantly more difficult. You can still get up to 17 out of 20 points on this assignment if you do everything except forinsertSmallest
. - How efficient is your code? Are you looping extra times through the list of Nodes?
- Do your classes exhibit good organization and commenting? Make sure to take a look at the Java Style Guidelines.
Start early, ask lots of questions, and have fun! Eric, the lab assistants, and the prefect are all here to help you succeed - don’t hesitate to ask for help if you’re struggling!
Starter Code
Below is the starter code zip described above.
- Acknowledgments
- This assignment modified from a similar one that has been used at Princeton and modified in turn by Sherri Goings, Layla Oesper, Eric Alexander, and Titus Klinge.