All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator 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. 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

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,

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