NearestNeighborTsp implements the nearest neighbor heuristic for solving symmetric TSP.
This is probably the simplest TSP heuristic. It starts with a minimum cost edge and at each step, it connects the nearest unvisited node to the current path. Finally, it connects the two end points of the path to form a tour.
This method runs in O(n2) time. It quickly finds a relatively short tour for most TSP instances, but it could also yield a really bad (or even the worst) solution in special cases.
CM | Type of the cost map. |
#include <lemon/nearest_neighbor_tsp.h>
Public Types | |
typedef CM | CostMap |
Type of the cost map. | |
typedef CM::Value | Cost |
Type of the edge costs. | |
Public Member Functions | |
NearestNeighborTsp (const FullGraph &gr, const CostMap &cost) | |
Constructor. | |
Execution Control | |
Cost | run () |
Runs the algorithm. | |
Query Functions | |
Cost | tourCost () const |
The total cost of the found tour. | |
const std::vector< Node > & | tourNodes () const |
Returns a const reference to the node sequence of the found tour. | |
template<typename Iterator > | |
void | tourNodes (Iterator out) const |
Gives back the node sequence of the found tour. | |
template<typename Path > | |
void | tour (Path &path) const |
Gives back the found tour as a path. |
NearestNeighborTsp | ( | const FullGraph & | gr, |
const CostMap & | cost | ||
) | [inline] |
Constructor.
gr | The full graph the algorithm runs on. |
cost | The cost map. |
This function returns the total cost of the found tour.
const std::vector<Node>& tourNodes | ( | ) | const [inline] |
This function returns a const reference to a vector that stores the node sequence of the found tour.
void tourNodes | ( | Iterator | out | ) | const [inline] |
This function copies the node sequence of the found tour into an STL container through the given output iterator. The value_type
of the container must be FullGraph::Node
. For example,
std::vector<FullGraph::Node> nodes(countNodes(graph)); tsp.tourNodes(nodes.begin());
or
std::list<FullGraph::Node> nodes; tsp.tourNodes(std::back_inserter(nodes));
This function copies the found tour as a list of arcs/edges into the given path structure.