Traveling salesman problem (TSP)
|
|
The symmetric Traveling salesman problem (TSP) of a list of points calculates the shortest possible route that visits each point and returns to the origin, considering that it does not matter the direction (sense) of the movement.
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 can use a consecutive, random, or a Nearest neighbor algorithm to get an initial guess, and follows with a 2-opt algorithm. Since it uses templates, the input data can be either integer or floating point.
template <typename T> T TSP(const Vector<Point_<T>>& points, Vector<int> &order, TSP_Init init)
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.
init defines the initial conditions, as:
TSP_CONSECUTIVE: The actual order of supplied points. order is neglected.
TSP_RANDOM: A random order of supplied points. order is neglected.
TSP_USER: order has to include an initial guess of the right ordering.
template <typename T> T TSP(const Vector<Vector<T>>& matrix, Vector<int> &order, TSP_Init init)
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, as the problem is symmetric, only the elements above the diagonal are considered. It also returns the most optimal order between the nodes.
init defines the initial conditions, as:
TSP_CONSECUTIVE: The actual order of supplied points. order is neglected.
TSP_RANDOM: A random order of supplied points. order is neglected.
TSP_USER: order has to include an initial guess of the right ordering.
|
