ASSIGNMENT 4
In this assignment, you will get more experience reading from a file and using arrays.
You will also learn how to design a greedy algorithmic solution to a problem that would be tedious and error-prone for a human to calculate.
GreedyPath
Given a file containing a list of two-dimensional points, you need to develop a program that does the following:
-
Computes the bounding box of the set of points.
That is, find the lower-left coordinate (x1, y1) and upper-right coordinate (x2, y2) of a rectangle that contains all points in the file.
-
Construct a path visiting each point exactly once.
The path always starts from the first point in the file.
You construct the path in a greedy fashion, always going next to the closest unvisited point.
-
Compute the total distance of the greedy path you found through the points.
The file GreedyPath.zip contains some example input files as well as a program you can use to graphically display your answer.
You can copy the files in the zip into your Eclipse project directory, then right-click on the project and select Refresh.
Here is one of the provided input files, points7.txt:
7
0.0 1.0
1.0 1.0
-1.0 1.0
2.0 0.0
-2.0 -2.0
1.0 -2.0
2.0 -2.0
Your first task will be to read the point data and put it into appropriate array variables.
For an example of a program that uses such parallel arrays, check out ClassifyProducts or SnowKey.
You can assume the input file will be well-formed and contain at least one point.
The first two lines of output of your program will be the lower-left and upper-right coordinates of the bounding box containing the points.
After this should come a blank line and then a line containing the integer number of points you read in.
You may want to get this working before working on the harder part of computing the path.
Here are sample runs of just this part of the program:
% java GreedyPath points7.txt
-2.0 -2.0
2.0 1.0
7
% java GreedyPath points5.txt
0.0 0.0
1.9 1.65
5
% java GreedyPath points3.txt
-1.0 0.0
1.0 1.0
3
We assume paths always start at the first point in the file.
From there, the path always goes to the next closest point that has not already been visited.
So for example in points7.txt, starting at (0.0, 1.0), the next closest point is (1.0, 1.0).
From (1.0, 1.0), the next closest point would be (0.0, 1.0), but since we already visited this one, the next best one is (2.0, 0.0), and so on.
You will need to use your arrays of the x- and y-coordinates to figure out which point is closest given your current location.
In the event of a tie, you should use the point that occurs first in the file.
You will also need to keep track of whether each point has been visited or not.
Hint: keeping track of something that has a yes or no answer is a perfect time for the boolean data type.
Everytime you decide on the next point (including the very first one), output the point's coordinate on a single line with the x- and y-coordinate separated by a space.
Also as you go, you should keep track of the total distance accrued by your path (i.e. compute the Euclidean distance between the last point and the point being added to the path, adding this to a sum variable).
After outputting all the points on the path, output a blank line followed by this distance.
Here is the complete output for some of the provided files:
% java GreedyPath points7.txt
-2.0 -2.0
2.0 1.0
7
0.0 1.0
1.0 1.0
2.0 0.0
2.0 -2.0
1.0 -2.0
-2.0 -2.0
-1.0 1.0
11.576491222541476
% java GreedyPath points5.txt
0.0 0.0
1.9 1.65
5
0.0 0.0
0.5 0.0
0.5 0.5
1.0 1.65
1.9 0.5
3.714301807049468
% java GreedyPath points3.txt
-1.0 0.0
1.0 1.0
3
0.0 0.0
1.0 1.0
-1.0 1.0
3.414213562373095
% java GreedyPath points3b.txt
-1.0 0.0
1.0 1.0
3
0.0 0.0
-1.0 1.0
1.0 1.0
3.414213562373095
If you would like to visualize how your path is constructed, you can use our provided program DrawPath.java.
This program reads in from standard input, the output of your GreedyPath program.
Using the StdDraw.java library, it graphically draws each line segment in your solution.
The line segments change from red to blue as the path progresses.
It also displays the path length computed by your GreedyPath program.
Here are some examples of how to use it along with the output:
% java GreedyPath points7.txt | java DrawPath 1000
|
 |
|
% java GreedyPath mona-20k.txt | java DrawPath
|
 |
|
% java GreedyPath usa13509.txt | java DrawPath
|
 |
Um. How do I get DrawPath to draw my points?
We haven't talked about using a command (or shell) window yet, but look at the slides posted on the schedule for today's lab.
How do I compute the Euclidean distance between two points?
You need to use the formula: 
In this formula p1 and p2 are the coordinates of one point and q1 and q2 are the coordinates of another.
You can take a square root in Java using Math.sqrt().
While there is a math method for taking powers, if you are just squaring a value, it is much more efficient just to use the normal multiplication operator.
Does my program find the shortest path visiting all the points?
Probably not. You might be surprised to learn this problem has been intensly studied for a very long time.
Currently we can find pretty good, but not necessarily optimal solutions.
Extra credit. Come up with an algorithm that provides a shorter path than the simple greedy heuristic.
Submission.
Submit your program GreedyPath.java via Moodle.
Be sure each submitted source file has the required header with your name, username, and a description of the program.
If you did the extra-credit, submit a single zip file containing all the files required to run your creation to the extra-credit dropbox.
Page last updated: October 06, 2016
