COIN-OR::LEMON - Graph Library

Changeset 1202:ef200e268af2 in lemon


Ignore:
Timestamp:
01/09/11 00:56:52 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Unifications and improvements in TSP algorithms (#386)

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

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

    r1201 r1202  
    3232namespace lemon {
    3333 
     34  /// \ingroup tsp
     35  ///
    3436  /// \brief Christofides algorithm for symmetric TSP.
    3537  ///
     
    3840  ///
    3941  /// This a well-known approximation method for the TSP problem with
    40   /// \ref checkMetricCost() "metric cost function".
     42  /// metric cost function.
    4143  /// It yields a tour whose total cost is at most 3/2 of the optimum,
    4244  /// but it is usually much better.
     
    5557  /// \tparam CM Type of the cost map.
    5658  ///
    57   /// \warning \& CM::Value must be signed type.
     59  /// \warning CM::Value must be a signed number type.
    5860  template <typename CM>
    5961  class ChristofidesTsp
     
    196198      /// found tour.
    197199      ///
    198       /// This function returns a const reference to the internal structure
     200      /// This function returns a const reference to a vector
    199201      /// that stores the node sequence of the found tour.
    200202      ///
  • lemon/greedy_tsp.h

    r1201 r1202  
    3131namespace lemon {
    3232
     33  /// \ingroup tsp
     34  ///
    3335  /// \brief Greedy algorithm for symmetric TSP.
    3436  ///
     
    4345  ///
    4446  /// This method runs in O(n<sup>2</sup>log(n)) time.
    45   /// It quickly finds an effectively short tour for most TSP
    46   /// instances, but in special cases, it could yield a really bad
    47   /// (or even the worst) solution.
     47  /// It quickly finds a short tour for most TSP instances, but in special
     48  /// cases, it could yield a really bad (or even the worst) solution.
    4849  ///
    4950  /// \tparam CM Type of the cost map.
     
    194195      /// found tour.
    195196      ///
    196       /// This function returns a const reference to the internal structure
     197      /// This function returns a const reference to a vector
    197198      /// that stores the node sequence of the found tour.
    198199      ///
  • lemon/insertion_tsp.h

    r1201 r1202  
    3131namespace lemon {
    3232
     33  /// \ingroup tsp
     34  ///
    3335  /// \brief Insertion algorithm for symmetric TSP.
    3436  ///
     
    7577      /// During the algorithm, nodes are selected for addition to the current
    7678      /// subtour according to the applied rule.
    77       /// In general, the FARTHEST yields the best tours, thus it is the
    78       /// default option. RANDOM usually gives somewhat worse results, but
    79       /// it is much faster than the others and it is the most robust.
     79      /// In general, the FARTHEST method yields the best tours, thus it is the
     80      /// default option. The RANDOM rule usually gives somewhat worse results,
     81      /// but it is much faster than the others and it is the most robust.
    8082      ///
    8183      /// The desired selection rule can be specified as a parameter of the
     
    179181      /// found tour.
    180182      ///
    181       /// This function returns a const reference to the internal structure
     183      /// This function returns a const reference to a vector
    182184      /// that stores the node sequence of the found tour.
    183185      ///
  • lemon/nearest_neighbor_tsp.h

    r1201 r1202  
    2525
    2626#include <deque>
     27#include <vector>
    2728#include <limits>
    2829#include <lemon/full_graph.h>
     
    3132namespace lemon {
    3233
     34  /// \ingroup tsp
     35  ///
    3336  /// \brief Nearest neighbor algorithm for symmetric TSP.
    3437  ///
     
    4245  ///
    4346  /// This method runs in O(n<sup>2</sup>) time.
    44   /// It quickly finds an effectively short tour for most TSP
    45   /// instances, but in special cases, it could yield a really bad
    46   /// (or even the worst) solution.
     47  /// It quickly finds a short tour for most TSP instances, but in special
     48  /// cases, it could yield a really bad (or even the worst) solution.
    4749  ///
    4850  /// \tparam CM Type of the cost map.
     
    6466      const CostMap &_cost;
    6567      Cost _sum;
    66       std::deque<Node> _path;
     68      std::vector<Node> _path;
    6769
    6870    public:
     
    8688      Cost run() {
    8789        _path.clear();
    88 
    89         if (_gr.nodeNum() == 0) return _sum = 0;
     90        if (_gr.nodeNum() == 0) {
     91          return _sum = 0;
     92        }
    9093        else if (_gr.nodeNum() == 1) {
    9194          _path.push_back(_gr(0));
     
    9396        }
    9497
     98        std::deque<Node> path_dq;
    9599        Edge min_edge1 = INVALID,
    96100             min_edge2 = INVALID;
     
    99103        Node n1 = _gr.u(min_edge1),
    100104             n2 = _gr.v(min_edge1);
    101         _path.push_back(n1);
    102         _path.push_back(n2);
     105        path_dq.push_back(n1);
     106        path_dq.push_back(n2);
    103107
    104108        FullGraph::NodeMap<bool> used(_gr, false);
     
    107111
    108112        min_edge1 = INVALID;
    109         while (int(_path.size()) != _gr.nodeNum()) {
     113        while (int(path_dq.size()) != _gr.nodeNum()) {
    110114          if (min_edge1 == INVALID) {
    111115            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
     
    128132          if (_cost[min_edge1] < _cost[min_edge2]) {
    129133            n1 = _gr.oppositeNode(n1, min_edge1);
    130             _path.push_front(n1);
     134            path_dq.push_front(n1);
    131135
    132136            used[n1] = true;
     
    137141          } else {
    138142            n2 = _gr.oppositeNode(n2, min_edge2);
    139             _path.push_back(n2);
     143            path_dq.push_back(n2);
    140144
    141145            used[n2] = true;
     
    147151        }
    148152
    149         _sum = _cost[_gr.edge(_path.back(), _path.front())];
    150         for (int i = 0; i < int(_path.size())-1; ++i) {
    151           _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     153        n1 = path_dq.back();
     154        n2 = path_dq.front();
     155        _path.push_back(n2);
     156        _sum = _cost[_gr.edge(n1, n2)];
     157        for (int i = 1; i < int(path_dq.size()); ++i) {
     158          n1 = n2;
     159          n2 = path_dq[i];
     160          _path.push_back(n2);
     161          _sum += _cost[_gr.edge(n1, n2)];
    152162        }
    153163
     
    172182      /// found tour.
    173183      ///
    174       /// This function returns a const reference to the internal structure
     184      /// This function returns a const reference to a vector
    175185      /// that stores the node sequence of the found tour.
    176186      ///
    177187      /// \pre run() must be called before using this function.
    178       const std::deque<Node>& tourNodes() const {
     188      const std::vector<Node>& tourNodes() const {
    179189        return _path;
    180190      }
  • lemon/opt2_tsp.h

    r1201 r1202  
    2222/// \ingroup tsp
    2323/// \file
    24 /// \brief 2-opt algorithm for symmetric TSP
     24/// \brief 2-opt algorithm for symmetric TSP.
    2525
    2626#include <vector>
     
    2929namespace lemon {
    3030
     31  /// \ingroup tsp
     32  ///
    3133  /// \brief 2-opt algorithm for symmetric TSP.
    3234  ///
     
    115117      }
    116118
    117       /// \brief Runs the algorithm from the given tour.
     119      /// \brief Runs the algorithm starting from the given tour.
    118120      ///
    119121      /// This function runs the algorithm starting from the given tour.
     
    157159      }
    158160
    159       /// \brief Runs the algorithm from the given tour.
    160       ///
    161       /// This function runs the algorithm starting from the given tour.
    162       ///
    163       /// \param tour The tour as a node sequence. It must be a standard
    164       /// sequence container storing all <tt>Node</tt>s in the desired order.
     161      /// \brief Runs the algorithm starting from the given tour.
     162      ///
     163      /// This function runs the algorithm starting from the given tour
     164      /// (node sequence).
     165      ///
     166      /// \param tour A vector that stores all <tt>Node</tt>s of the graph
     167      /// in the desired order.
    165168      ///
    166169      /// \return The total cost of the found tour.
    167       template <template <typename> class Container>
    168       Cost run(const Container<Node>& tour) {
     170      Cost run(const std::vector<Node>& tour) {
    169171        _path.clear();
    170172
     
    181183
    182184        _plist.resize(2*_gr.nodeNum());
    183         typename Container<Node>::const_iterator it = tour.begin();
     185        typename std::vector<Node>::const_iterator it = tour.begin();
    184186        int first = _gr.id(*it),
    185187            prev = first,
     
    218220      /// found tour.
    219221      ///
    220       /// This function returns a const reference to the internal structure
     222      /// This function returns a const reference to a vector
    221223      /// that stores the node sequence of the found tour.
    222224      ///
Note: See TracChangeset for help on using the changeset viewer.