Opt2Tsp

Declared in lemon/opt2_tsp.h, in the group Traveling Salesman Problem; the same class on the Doxygen site.

template< typename CM >
class Opt2Tsp

2-opt algorithm for symmetric TSP.

Opt2Tsp implements the 2-opt heuristic for solving symmetric TSP.

This algorithm starts with an initial tour and iteratively improves it. At each step, it removes two edges and the reconnects the created two paths in the other way if the resulting tour is shorter. The algorithm finishes when no such 2-opt move can be applied, and so the tour is 2-optimal.

If no starting tour is given to the run() function, then the algorithm uses the node sequence determined by the node IDs. Oherwise, it starts with the given tour.

This is a rather slow but effective method. Its typical usage is the improvement of the result of a fast tour construction heuristic (e.g. the InsertionTsp algorithm).

Template Parameters:

CM – Type of the cost map.

Execution Control

inline Cost run()

Runs the algorithm from scratch.

This function runs the algorithm starting from the tour that is determined by the node ID sequence.

Returns:

The total cost of the found tour.

template< typename Path >
inline Cost run( const Path & tour )

Runs the algorithm starting from the given tour.

This function runs the algorithm starting from the given tour.

Parameters:

tour – The tour as a path structure. It must be a valid path containing excactly n arcs.

Returns:

The total cost of the found tour.

inline Cost run( const std::vector< Node > & tour )

Runs the algorithm starting from the given tour.

This function runs the algorithm starting from the given tour (node sequence).

Parameters:

tour – A vector that stores all Nodes of the graph in the desired order.

Returns:

The total cost of the found tour.

Query Functions

inline Cost tourCost() const

The total cost of the found tour.

This function returns the total cost of the found tour.

Pre:

run() must be called before using this function.

inline const std::vector< Node > & tourNodes() const

Returns a const reference to the node sequence of the found tour.

This function returns a const reference to a vector that stores the node sequence of the found tour.

Pre:

run() must be called before using this function.

template< typename Iterator >
inline void tourNodes( Iterator out ) const

Gives back the node sequence of the found tour.

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 ) );

Pre:

run() must be called before using this function.

template< typename Path >
inline void tour( Path & path ) const

Gives back the found tour as a path.

This function copies the found tour as a list of arcs/edges into the given path structure.

Pre:

run() must be called before using this function.

Public Types

typedef CM CostMap

Type of the cost map.

typedef CM::Value Cost

Type of the edge costs.

Public Functions

inline Opt2Tsp( const FullGraph & gr , const CostMap & cost )

Constructor.

Parameters:
  • gr – The full graph the algorithm runs on.

  • cost – The cost map.