Added Travelling Salesman algorithm. A demo is included in STEM4U_DemoTest.
The Traveling salesman problem (TSP) of a list of points calculates the shortest possible route that visits each point and returns to the origin.
This is a NP-hard problem that for medium sets could be impractical to be solved by an exact algorithm as brute force or linear programming. Because of that, for practical reasons, its resolution using heuristics and approximations is advised.
This implementation uses a Nearest neighbor algorithm to get an initial guess, and follows with a 2-opt algorithm.
template <typename T> T TSP(const Vector<Vector<T>>& matrix, Vector<int> &order)
Returns the total distance of a traveling salesman problem defined by a matrix of distances between nodes. All the elements of the diagonal of this matrix have to be zero, and the elements above the diagonal are considered. It also returns the most optimal order between the nodes.
order may include an initial guess of the right ordering. If not, order should be empty.
template <typename T> T TSP(const Vector<Point_<T>>& points, Vector<int> &order)
Returns the total distance of a traveling salesman problem defined by a list of euclidean coordinates of the points. It also returns the most optimal order between the nodes.
order may include an initial guess of the right ordering. If not, order should be empty.
Members
Pages
Help
Register
Login
Home
