Given a set of N points in the plane, the goal of a traveling salesperson is to

Question

Given a set of N points in the plane, the goal of a traveling salesperson is to visit all of them (and arrive back home) while keeping the total distance traveled as short as possible. For this assignment you will write a program to compute an approximate solution to the traveling salesperson problem (TSP), and use it to find the shortest tour that you can, connecting a given set of points in the plane.

Your main task is to implement the nearest neighbor and smallest increase insertion heuristics for building a tour incrementally. These heuristic approaches work as follows. Start with a one-point tour (from the first point back to itself), and iterate the following process until there are no points left.

- Nearest neighbor heuristic: Read in the next point, and add it to the current tour after the point to which it is closest. (If there is more than one equivalent point to which it is closest, insert it after the first such point you discover.)
- Smallest increase heuristic: Read in the next point, and add it to the current tour after the point where it results in the least possible increase in the tour length. (If there is more than one equivalent best point, insert it after the first such point you discover.)

The input file format will look like this, with the x value on the left and the y value on the right for each point:

532.6531 247.7551
93.0612 393.6735
565.5102 590.0001
10.0201 11.8643

And so on. PLEASE USE THE JAVA STANDARD LINKEDLIST CLASS! Do not answer with an array based implementation.

Explanation / Answer

you should implement two classes Tour and Point. the API: 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 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 Try using an inner class called Node which act like a linkedlist. and the logic for insertNearest is you have to link the nodes which are nearer in our linked list. Try to implement these methods..

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.