NearestNeighborTsp
Declared in lemon/nearest_neighbor_tsp.h, in the group Traveling Salesman Problem; the same class on the Doxygen site.
-
template< typename CM >
class NearestNeighborTsp Nearest neighbor algorithm for symmetric TSP.
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.
- Template Parameters:
CM – Type of the cost map.
Execution Control
Query Functions
-
inline Cost tourCost() const
The total cost of the found tour.
This function returns the total cost of the found tour.
- Pre:
run() must be called before using this function.
-
inline const std::vector< Node > & tourNodes() const
Returns a const reference to the node sequence of the found tour.
This function returns a const reference to a vector that stores the node sequence of the found tour.
- Pre:
run() must be called before using this function.
-
template< typename Iterator >
inline void tourNodes( Iterator out ) const Gives back the node sequence of the found tour.
This function copies the node sequence of the found tour into an STL container through the given output iterator. The
value_typeof the container must beFullGraph::Node. For example,orstd::vector< FullGraph::Node > nodes( countNodes( graph ) ); tsp.tourNodes( nodes.begin() );
std::list< FullGraph::Node > nodes; tsp.tourNodes( std::back_inserter( nodes ) );
- Pre:
run() must be called before using this function.
-
template< typename Path >
inline void tour( Path & path ) const Gives back the found tour as a path.
This function copies the found tour as a list of arcs/edges into the given path structure.
- Pre:
run() must be called before using this function.
Public Types
Public Functions
-
inline NearestNeighborTsp( const FullGraph & gr , const CostMap & cost )
Constructor.
- Parameters:
gr – The full graph the algorithm runs on.
cost – The cost map.