CSCI 136 |
1,000 points optimal tour
Each Point object can return a string representation of itself, draw itself to standard draw, draw a line segment from itself to another point using standard draw, and calculate the Euclidean distance between itself and another point.public class Point (2D point data type) --------------------------------------------------------------------------------------- Point(double x, double y) // create the point (x, y) String toString() // return string representation void draw() // draw point using standard draw void drawTo(Point that) // draw line segment between the two points double distanceTo(Point that) // return Euclidean distance between the two points
Your Tour data type must implement the following API:private class Node { private Point p; private Node next; }
Each Tour object should be able to print its constituent points to standard output, draw its points to standard draw, count its number of points, compute its total distance, and insert a new point using either of the two heuristics. The first constructor creates an empty tour; the second constructor creates a 4-point tour and is intended to assist with debugging. It will not need to be used in the final program.public class Tour ---------------------------------------------------------------------------------------------- Tour() // create an empty tour Tour(Point a, Point b, Point c, Point d) // create a 4 point tour a->b->c->d->a void show() // print the tour to standard output void draw() // draw the tour to standard draw int size() // number of points on tour double distance() // return the total distance of the tour void insertNearest(Point p) // insert p using nearest neighbor heuristic void insertSmallest(Point p) // insert p using smallest increase heuristic
After implementing Tour.java, use the client program NearestInsertion.java to read in the points from standard input, run the nearest neighbor heuristic; print the resulting tour, its distance, and its number of points to standard output; and draw the resulting tour to standard draw. SmallestInsertion.java is analogous but runs the smallest insertion heuristic.% more tsp1000.txt 775 768 185.0411 457.8824 247.5023 299.4322 701.3532 369.7156 563.2718 442.3282 144.5569 576.4812 535.9311 478.4692 383.8523 458.4757 329.9402 740.9576 ... 254.9820 302.2548
% java NearestInsertion tsp1000.txt Tour distance = 27868.710634854797 Number of points = 1000 (185.0411, 457.8824) (198.3921, 464.6812) (195.8296, 456.6559) (216.8989, 455.126) (213.3513, 468.0186) (241.4387, 467.413) (259.0682, 473.7961) (221.5852, 442.8863) ... (264.57, 410.328) |
% java SmallestInsertion tsp1000.txt Tour distance = 17265.628155352584 Number of points = 1000 (185.0411, 457.8824) (195.8296, 456.6559) (193.0671, 450.2405) (200.7237, 426.3461) (200.5698, 422.6481) (217.4682, 434.3839) (223.1549, 439.8027) (221.5852, 442.8863) ... (186.8032, 449.9557) |
||
Grade Item | Points Possible | Points Earned |
---|---|---|
Program Compiles | 1 | |
Program Runs | 1 | |
javadoc Comments on All Classes and Methods | 4 | |
Implemented Tour() Correctly | 2 | |
Implemented Tour(a,b,c,d) Correctly | 2 | |
Implemented show() Correctly | 2 | |
Implemented draw() Correctly | 2 | |
Implemented size() Correctly | 2 | |
Implemented distance() Correctly | 2 | |
Implemented insertNearest(p) Correctly | 4 | |
Implemented insertSmallest(p) Correctly | 4 | |
Write Up of Results across Several Test Files | 4 | |
Total | 30 |
Page last updated: December 20, 2019