Description
The Traveling Salesperson Problem
The input to the problem is a collection of n points in the plane. The points have int values.
The goal of the traveling salesperson problem is to find the shortest path that visits every point
exactly once and returns to the starting point. That is, we are looking for a cycle in the graph that
visits each vertex exactly once, such that the total length is as small as possible.
For example, suppose the input is the 4 points
A = (2,2), B = (2,6), C = (5,6), D = (5,9)
Then we may consider each of the following cycles through the 4 points.
– The length of the cycle on the left ABCD (and back to A) is
dist(A,B)+dist(B,C)+dist(C,D)+dist(D,A) = 4 + 3 + 3 + 3
2
+ 7
2 ≈ 17. 616
– The length of the cycle in the middle ACDB (and back to A) is
dist(A,C)+dist(C,D)+dist(D,B)+dist(B,A) = 3
2
+ 4
2
+ 3 + 3
2
+ 3
2
+ 4 ≈ 16. 243
– The length of the cycle on the right ACBD (and back to A) is
dist(A,C)+dist(C,B)+dist(B,D)+dist(D,A) = 3
2
+ 4
2
+ 3 + 3
2
+ 3
2
+ 3
2
+ 7
2 ≈ 19. 858
That is, among these three cycles, the better one is ACDB, whose length is 16.243…
In fact, this is the optimal solution for this input.
You will need to design your own classes in C++ to implement a solver for this problem.
Requirements:
The requirements for this project are the following [The exact implementation details are described
below].
Storing the points:
You will need to write a class that stores a collection of points. You may use any data structure you
want to do it (array, linked list or vector in C++)
Print the list of points:
Your solution should have a method that prints the list of all points. The format is up to you. For
example, you can use the format
A = (2,2)
B = (2,6)
C = (5,6)
D = (5,9)
Drawing the points:
Your solution should have a method that draws the points on the screen.
No need to use anything fancy for drawing. A textual representation of the board suffices.
You may assume for drawing only that all coordinates are between 0 and 20 and names of points
are single letters. For example, you can print something like this:
– – – – – – – – – – –
– – – – – – – – D – –
– – – – – – – – – – –
– – – – – – – – – – –
– – B – – – – C – –
– – – – – – – – – – –
– – – – – – – – – – –
– – – – – – – – – – –
– – A – – – – – – –
– – – – – – – – – – –
– – – – – – – – – – –
TSPSolver:
This is the main part of this project. You will need to implement a heuristic algorithm that finds a
solution to the TSP problem. For the algorithm see the part TSP solver below.
main():
You will need to write the main() function that will run several tests to check your solution.
Write a test for every part of your code. Write as many tests as you think are necessary.
At the very least, your tests should (1) provide inputs to the problem (2) print the list using the
printList method (3) draw the points (4) run the solver and output the obtained solution: you need
to print to screen both the order of the vertices in the cycle and the total length of the cycle.
TSP solver
The Traveling Salesperson Problem is NP-complete. Without saying exactly what this means, this
implies that we don’t know an efficient algorithm that finds an optimal solution for every input.
Instead of trying to find an optimal solution, your TSPsolver will need to implement the following
heuristic algorithm, which we will call “smallest increase heuristic”.
Smallest increase heuristic:
● The input is a list L[0…n-1] of n≥3 points.
● The algorithm starts with the cycle consisting of only the points L[0], L[1], L[2].
● In the first iteration the algorithm takes the point L[3], and adds it to the current cycle in the
location that minimizes the increase in the length.
● In the second iteration the algorithm takes the point L[4], and adds it to the current cycle in
the location that minimizes the increase in the length.
● And so on. When adding the point L[i], we add it to the cycle between C[j] and C[j+1] so
that dist(C[j],L[i]) + dist(L[i],C[j+1]) – dist(C[j+1],C[j]) is
minimized.
** This heuristic is not guaranteed to find an optimal solution. Instead, it chooses the position for
each point in the cycles using a greedy strategy.
Example:
Consider the example above with 4 points, and suppose that the list is [C,B,D,A].
1. We start with the cycle consisting of the points C,B,D.
2. In the first iteration, we choose where to add A to the cycle.
➢ If we add A between C and B, then the increase will be
dist(C,A) +dist(A,B) – dist(B,C) = 3
2
+ 4
2
+ 4 − 3 = 6
➢ If we add A between B and D, then the increase will be
dist(B,A) +dist(A,D) – dist(D,B) = 4 + 3
2
+ 7
2 − 3
2
+ 3
2 = 7. 3731…
➢ If we add A between D and C, then the increase will be
dist(D,A) +dist(A,C) – dist(C,D) = 3
2
+ 7
2
+ 3
2
+ 4
2 − 3 = 9. 6157…
3. Therefore, it is best to add A between C and B.
4. The resulting cycle will be CABD (and back to C)
Implementing classes:
There are no specific requirements about which classes you need to implement. However, your
solution must meet the requirements described on page 3.
Here are some suggestions you may use. They are also provided in Assignment5_supportFiles.zip
These are examples only. You may choose a completely different implementation if you want.
// the class represents a point in the grid
class Point {
private:
string name;
int x;
int y;
public:
// computes the distance between this and the other point
float getDistance(const Point &other)
// also contains getters and setters, see .hpp for details
}
// the class stores an ordered list of points
// used to store the input to the problem
// may also be used to store a partial solution to the TSP problem
class ListOfPoints {
// some data structure to store the points
public:
// adds a newPt after a point with the given name/given index in the list
void addAfter(Point& newPt, string name);
void addAfter(Point& newPt, int index); // you decide which one you prefer
// adds a new point to the end of the list
void addToBack(Point& newPt);
// gets a copy of the point from the list at index i
Point& getPointAt(unsigned int i);
// gets the size of the list
int getSize() const;
// prints the list of points
void printList() const;
// draws the points
void draw() const;
}
// stores a cycle that traverses all points in some order
class TSPCycle : public ListOfPoints {
public:
float getLength() const // returns the total length of the cycle
}
// implementation of the TSP solver
class TSPSolver {
private:
// may hold the following members:
ListOfPoints m_list;
TSPCycle m_solution; // you may remove/modify these in any way you want
public:
// an example of a constructor – gets list of points
TSPSolver(ListOfPoints &list);
// solves the problem, and stores the solution
void solve();
// returns the solution obtained by the solve() method.
TSPCycle& getSolution();
}
Other heuristics [NOT FOR SUBMISSION]:
You may try implementing several other heuristics if you want.
For example, consider the following two greedy ideas:
● Nearest last point heuristic: The algorithm starts with a path consisting of one point. In
each iteration the algorithm builds a path P by adding to it one point at a time. Specifically,
the algorithm finds a point that has not been added to P yet, which is the closest to the last
point in P (breaking ties arbitrarily). This point is added to P as the last point. In the end the
last point is connected to the first point to close the cycle.
● Nearest existing point heuristic: The algorithm starts with the path consisting of L[0]. In
each iteration take the next point L[i], and add it to the current path after the point to which
it is closest, breaking ties arbitrarily. When all points have been added, close the cycle by
connecting the last point in the path to the first point.
● Extended smallest increase heuristic: Same as what you need to do for the assignment, but
in each iteration the algorithm chooses which point is best to choose among the remaining
points, and where to add it in the cycle.