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

## Detailed Description

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

InsertionTsp implements the insertion heuristic for solving symmetric TSP.

This is a fast and effective tour construction method that has many variants. It starts with a subtour containing a few nodes of the graph and it iteratively inserts the other nodes into this subtour according to a certain node selection rule.

This method is among the fastest TSP algorithms, and it typically provides quite good solutions (usually much better than NearestNeighborTsp and GreedyTsp).

InsertionTsp implements four different node selection rules, from which the most effective one (farthest node selection) is used by default. With this choice, the algorithm runs in O(n2) time. For more information, see SelectionRule.

Template Parameters

  CM | Type of the cost map.

`#include <lemon/insertion_tsp.h>`

## Public Types

enum | SelectionRule { NEAREST , FARTHEST , CHEAPEST , RANDOM }
| Constants for specifying the node selection rule. More...
typedef CM | CostMap
| Type of the cost map.
typedef CM::Value | Cost
| Type of the edge costs.

## Public Member Functions

| InsertionTsp (const FullGraph &gr, const CostMap &cost)
| Constructor.
Execution Control
Cost | run (SelectionRule rule=FARTHEST)
| 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.

## Member Enumeration Documentation

## SelectionRule

template<typename CM>

enum SelectionRule

Enum type containing constants for specifying the node selection rule for the run() function.

During the algorithm, nodes are selected for addition to the current subtour according to the applied rule. The FARTHEST method is one of the fastest selection rules, and it is typically the most effective, thus it is the default option. The RANDOM rule usually gives slightly worse results, but it is more robust.

The desired selection rule can be specified as a parameter of the run() function.

Enumerator
NEAREST | An unvisited node having minimum distance from the current subtour is selected at each step. The algorithm runs in O(n2) time using this selection rule.
FARTHEST | An unvisited node having maximum distance from the current subtour is selected at each step. The algorithm runs in O(n2) time using this selection rule.
CHEAPEST | An unvisited node whose insertion results in the least increase of the subtour's total cost is selected at each step. The algorithm runs in O(n3) time using this selection rule, but in most cases, it is almost as fast as with other rules.
RANDOM | An unvisited node is selected randomly without any evaluation at each step. The global random number generator instance is used. You can seed it before executing the algorithm, if you would like to. The algorithm runs in O(n2) time using this selection rule.

## Constructor & Destructor Documentation

## InsertionTsp()

template<typename CM>

InsertionTsp | ( | 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 | ( | SelectionRule | rule = FARTHEST | ) |

inline

This function runs the algorithm.

Parameters

  rule | The node selection rule. For more information, see SelectionRule.

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.