All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Public Types | Public Member Functions
NearestNeighborTsp< CM > Class Template Reference

Detailed Description

template<typename CM>
class lemon::NearestNeighborTsp< CM >

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
CMType 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. More...
 
Execution Control
Cost run ()
 Runs the algorithm. More...
 
Query Functions
Cost tourCost () const
 The total cost of the found tour. More...
 
const std::vector< Node > & tourNodes () const
 Returns a const reference to the node sequence of the found tour. More...
 
template<typename Iterator >
void tourNodes (Iterator out) const
 Gives back the node sequence of the found tour. More...
 
template<typename Path >
void tour (Path &path) const
 Gives back the found tour as a path. More...
 

Constructor & Destructor Documentation

NearestNeighborTsp ( const FullGraph gr,
const CostMap cost 
)
inline

Constructor.

Parameters
grThe full graph the algorithm runs on.
costThe cost map.

Member Function Documentation

Cost run ( )
inline

This function runs the algorithm.

Returns
The total cost of the found tour.
Cost tourCost ( ) const
inline

This function returns the total cost of the found tour.

Precondition
run() must be called before using this function.
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.

Precondition
run() must be called before using this function.
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));
*
Precondition
run() must be called before using this function.
void tour ( Path path) const
inline

This function copies the found tour as a list of arcs/edges into the given path structure.

Precondition
run() must be called before using this function.