![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
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. | |
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.
| CM | Type of the cost map. |
Constructor.
| gr | The full graph the algorithm runs on. |
| cost | The cost map. |
|
inline |
This function runs the algorithm.
|
inline |
This function returns the total cost of the found tour.
|
inline |
This function returns a const reference to a vector that stores the node sequence of the found tour.
|
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,
or
This function copies the found tour as a list of arcs/edges into the given path structure.