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

Detailed Description

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

GreedyTsp implements the greedy heuristic for solving symmetric TSP.

This algorithm is quite similar to the nearest neighbor heuristic, but it maintains a set of disjoint paths. At each step, the shortest possible edge is added to these paths as long as it does not create a cycle of less than n edges and it does not increase the degree of any node above two.

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/greedy_tsp.h>

Public Types

typedef CM CostMap
 Type of the cost map.
 
typedef CM::Value Cost
 Type of the edge costs.
 

Public Member Functions

 GreedyTsp (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

GreedyTsp ( 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,

tsp.tourNodes(nodes.begin());

or

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.