# Changeset 1202:ef200e268af2 in lemon

Ignore:
Timestamp:
01/09/11 00:56:52 (11 years ago)
Branch:
default
Phase:
public
Message:

Unifications and improvements in TSP algorithms (#386)

Files:
6 edited

Unmodified
Removed
• ## doc/groups.dox

 r1200 once (i.e. the minimum cost Hamiltonian cycle). These TSP algorithms should be used with a metric cost function. Otherwise, they could yield worse results. These TSP algorithms are intended to be used with a \e metric \e cost \e function, i.e. the edge costs should satisfy the triangle inequality. Otherwise the algorithms could yield worse results. LEMON provides five well-known heuristics for solving symmetric TSP:
• ## lemon/christofides_tsp.h

 r1201 namespace lemon { /// \ingroup tsp /// /// \brief Christofides algorithm for symmetric TSP. /// /// /// This a well-known approximation method for the TSP problem with /// \ref checkMetricCost() "metric cost function". /// metric cost function. /// It yields a tour whose total cost is at most 3/2 of the optimum, /// but it is usually much better. /// \tparam CM Type of the cost map. /// /// \warning \& CM::Value must be signed type. /// \warning CM::Value must be a signed number type. template class ChristofidesTsp /// found tour. /// /// This function returns a const reference to the internal structure /// This function returns a const reference to a vector /// that stores the node sequence of the found tour. ///
• ## lemon/greedy_tsp.h

 r1201 namespace lemon { /// \ingroup tsp /// /// \brief Greedy algorithm for symmetric TSP. /// /// /// This method runs in O(n2log(n)) time. /// It quickly finds an effectively short tour for most TSP /// instances, but in special cases, it could yield a really bad /// (or even the worst) solution. /// It quickly finds a short tour for most TSP instances, but in special /// cases, it could yield a really bad (or even the worst) solution. /// /// \tparam CM Type of the cost map. /// found tour. /// /// This function returns a const reference to the internal structure /// This function returns a const reference to a vector /// that stores the node sequence of the found tour. ///
• ## lemon/insertion_tsp.h

 r1201 namespace lemon { /// \ingroup tsp /// /// \brief Insertion algorithm for symmetric TSP. /// /// During the algorithm, nodes are selected for addition to the current /// subtour according to the applied rule. /// In general, the FARTHEST yields the best tours, thus it is the /// default option. RANDOM usually gives somewhat worse results, but /// it is much faster than the others and it is the most robust. /// In general, the FARTHEST method yields the best tours, thus it is the /// default option. The RANDOM rule usually gives somewhat worse results, /// but it is much faster than the others and it is the most robust. /// /// The desired selection rule can be specified as a parameter of the /// found tour. /// /// This function returns a const reference to the internal structure /// This function returns a const reference to a vector /// that stores the node sequence of the found tour. ///
• ## lemon/nearest_neighbor_tsp.h

 r1201 #include #include #include #include namespace lemon { /// \ingroup tsp /// /// \brief Nearest neighbor algorithm for symmetric TSP. /// /// /// This method runs in O(n2) time. /// It quickly finds an effectively short tour for most TSP /// instances, but in special cases, it could yield a really bad /// (or even the worst) solution. /// It quickly finds a short tour for most TSP instances, but in special /// cases, it could yield a really bad (or even the worst) solution. /// /// \tparam CM Type of the cost map. const CostMap &_cost; Cost _sum; std::deque _path; std::vector _path; public: Cost run() { _path.clear(); if (_gr.nodeNum() == 0) return _sum = 0; if (_gr.nodeNum() == 0) { return _sum = 0; } else if (_gr.nodeNum() == 1) { _path.push_back(_gr(0)); } std::deque path_dq; Edge min_edge1 = INVALID, min_edge2 = INVALID; Node n1 = _gr.u(min_edge1), n2 = _gr.v(min_edge1); _path.push_back(n1); _path.push_back(n2); path_dq.push_back(n1); path_dq.push_back(n2); FullGraph::NodeMap used(_gr, false); min_edge1 = INVALID; while (int(_path.size()) != _gr.nodeNum()) { while (int(path_dq.size()) != _gr.nodeNum()) { if (min_edge1 == INVALID) { for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) { if (_cost[min_edge1] < _cost[min_edge2]) { n1 = _gr.oppositeNode(n1, min_edge1); _path.push_front(n1); path_dq.push_front(n1); used[n1] = true; } else { n2 = _gr.oppositeNode(n2, min_edge2); _path.push_back(n2); path_dq.push_back(n2); used[n2] = true; } _sum = _cost[_gr.edge(_path.back(), _path.front())]; for (int i = 0; i < int(_path.size())-1; ++i) { _sum += _cost[_gr.edge(_path[i], _path[i+1])]; n1 = path_dq.back(); n2 = path_dq.front(); _path.push_back(n2); _sum = _cost[_gr.edge(n1, n2)]; for (int i = 1; i < int(path_dq.size()); ++i) { n1 = n2; n2 = path_dq[i]; _path.push_back(n2); _sum += _cost[_gr.edge(n1, n2)]; } /// found tour. /// /// This function returns a const reference to the internal structure /// 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. const std::deque& tourNodes() const { const std::vector& tourNodes() const { return _path; }
• ## lemon/opt2_tsp.h

 r1201 /// \ingroup tsp /// \file /// \brief 2-opt algorithm for symmetric TSP /// \brief 2-opt algorithm for symmetric TSP. #include namespace lemon { /// \ingroup tsp /// /// \brief 2-opt algorithm for symmetric TSP. /// } /// \brief Runs the algorithm from the given tour. /// \brief Runs the algorithm starting from the given tour. /// /// This function runs the algorithm starting from the given tour. } /// \brief Runs the algorithm from the given tour. /// /// This function runs the algorithm starting from the given tour. /// /// \param tour The tour as a node sequence. It must be a standard /// sequence container storing all Nodes in the desired order. /// \brief Runs the algorithm starting from the given tour. /// /// This function runs the algorithm starting from the given tour /// (node sequence). /// /// \param tour A vector that stores all Nodes of the graph /// in the desired order. /// /// \return The total cost of the found tour. template
Note: See TracChangeset for help on using the changeset viewer.