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(n²) 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.

#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.

Constructor & Destructor Documentation

NearestNeighborTsp ( const FullGraph &  gr, const CostMap &  cost  )

inline

Constructor.

Parameters

gr	The full graph the algorithm runs on.
cost	The 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.