Loading...
Searching...
No Matches
GreedyTsp< CM > Class Template Reference
Algorithms » Traveling Salesman Problem

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

  CM | Type 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()

template<typename CM>

GreedyTsp | ( | const FullGraph & | gr,
|  | const CostMap & | cost )

inline

Constructor.

Parameters

  gr | The full graph the algorithm runs on.
  cost | The 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());
lemon::countNodes
int countNodes(const Graph &g)
Function to count the nodes in the graph.
Definition core.h:252

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.