abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
GreedyTsp< CM > Class Template Reference

Greedy algorithm for symmetric TSP. More...

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

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(n2logn) time, the sort of the edges of the complete graph. 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.

Constructor & Destructor Documentation

◆ GreedyTsp()

template< typename CM >
GreedyTsp ( const FullGraph & gr,
const CostMap & cost )
inline

Constructor.

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

Member Function Documentation

◆ run()

template< typename CM >
Cost run ( )
inline

This function runs the algorithm.

Returns
The total cost of the found tour.

◆ tourCost()

template< typename CM >
Cost tourCost ( ) const
inline

This function returns the total cost of the found tour.

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

◆ tourNodes() [1/2]

template< typename CM >
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.

◆ tourNodes() [2/2]

template< typename CM >
template< typename Iterator >
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() );
int countNodes( const Graph & g )
Function to count the nodes in the graph.
Definition core.h:258

or

std::list< FullGraph::Node > nodes;
tsp.tourNodes( std::back_inserter( nodes ) );
Precondition
run() must be called before using this function.

◆ tour()

template< typename CM >
template< typename Path >
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.