author Peter Kovacs Sun, 09 Jan 2011 00:56:52 +0100 changeset 1202 ef200e268af2 parent 1201 9a51db038228 child 1203 07682e24c4e8
Unifications and improvements in TSP algorithms (#386)
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/christofides_tsp.h file | annotate | diff | comparison | revisions lemon/greedy_tsp.h file | annotate | diff | comparison | revisions lemon/insertion_tsp.h file | annotate | diff | comparison | revisions lemon/nearest_neighbor_tsp.h file | annotate | diff | comparison | revisions lemon/opt2_tsp.h file | annotate | diff | comparison | revisions
     1.1 --- a/doc/groups.dox	Sat Jan 08 22:51:16 2011 +0100
1.2 +++ b/doc/groups.dox	Sun Jan 09 00:56:52 2011 +0100
1.3 @@ -561,8 +561,9 @@
1.4  the problem is to find a shortest possible tour that visits each node exactly
1.5  once (i.e. the minimum cost Hamiltonian cycle).
1.6
1.7 -These TSP algorithms should be used with a
1.8 -metric cost function. Otherwise, they could yield worse results.
1.9 +These TSP algorithms are intended to be used with a \e metric \e cost
1.10 +\e function, i.e. the edge costs should satisfy the triangle inequality.
1.11 +Otherwise the algorithms could yield worse results.
1.12
1.13  LEMON provides five well-known heuristics for solving symmetric TSP:
1.14   - \ref NearestNeighborTsp Neareast neighbor algorithm

     2.1 --- a/lemon/christofides_tsp.h	Sat Jan 08 22:51:16 2011 +0100
2.2 +++ b/lemon/christofides_tsp.h	Sun Jan 09 00:56:52 2011 +0100
2.3 @@ -31,13 +31,15 @@
2.4
2.5  namespace lemon {
2.6
2.7 +  /// \ingroup tsp
2.8 +  ///
2.9    /// \brief Christofides algorithm for symmetric TSP.
2.10    ///
2.11    /// ChristofidesTsp implements Christofides' heuristic for solving
2.12    /// symmetric \ref tsp "TSP".
2.13    ///
2.14    /// This a well-known approximation method for the TSP problem with
2.15 -  /// \ref checkMetricCost() "metric cost function".
2.16 +  /// metric cost function.
2.17    /// It yields a tour whose total cost is at most 3/2 of the optimum,
2.18    /// but it is usually much better.
2.19    /// This implementation runs in O(n<sup>3</sup>log(n)) time.
2.20 @@ -54,7 +56,7 @@
2.21    ///
2.22    /// \tparam CM Type of the cost map.
2.23    ///
2.24 -  /// \warning \& CM::Value must be signed type.
2.25 +  /// \warning CM::Value must be a signed number type.
2.26    template <typename CM>
2.27    class ChristofidesTsp
2.28    {
2.29 @@ -195,7 +197,7 @@
2.30        /// \brief Returns a const reference to the node sequence of the
2.31        /// found tour.
2.32        ///
2.33 -      /// This function returns a const reference to the internal structure
2.34 +      /// This function returns a const reference to a vector
2.35        /// that stores the node sequence of the found tour.
2.36        ///
2.37        /// \pre run() must be called before using this function.

     3.1 --- a/lemon/greedy_tsp.h	Sat Jan 08 22:51:16 2011 +0100
3.2 +++ b/lemon/greedy_tsp.h	Sun Jan 09 00:56:52 2011 +0100
3.3 @@ -30,6 +30,8 @@
3.4
3.5  namespace lemon {
3.6
3.7 +  /// \ingroup tsp
3.8 +  ///
3.9    /// \brief Greedy algorithm for symmetric TSP.
3.10    ///
3.11    /// GreedyTsp implements the greedy heuristic for solving
3.12 @@ -42,9 +44,8 @@
3.13    /// not increase the degree of any node above two.
3.14    ///
3.15    /// This method runs in O(n<sup>2</sup>log(n)) time.
3.16 -  /// It quickly finds an effectively short tour for most TSP
3.17 -  /// instances, but in special cases, it could yield a really bad
3.18 -  /// (or even the worst) solution.
3.19 +  /// It quickly finds a short tour for most TSP instances, but in special
3.20 +  /// cases, it could yield a really bad (or even the worst) solution.
3.21    ///
3.22    /// \tparam CM Type of the cost map.
3.23    template <typename CM>
3.24 @@ -193,7 +194,7 @@
3.25        /// \brief Returns a const reference to the node sequence of the
3.26        /// found tour.
3.27        ///
3.28 -      /// This function returns a const reference to the internal structure
3.29 +      /// This function returns a const reference to a vector
3.30        /// that stores the node sequence of the found tour.
3.31        ///
3.32        /// \pre run() must be called before using this function.

     4.1 --- a/lemon/insertion_tsp.h	Sat Jan 08 22:51:16 2011 +0100
4.2 +++ b/lemon/insertion_tsp.h	Sun Jan 09 00:56:52 2011 +0100
4.3 @@ -30,6 +30,8 @@
4.4
4.5  namespace lemon {
4.6
4.7 +  /// \ingroup tsp
4.8 +  ///
4.9    /// \brief Insertion algorithm for symmetric TSP.
4.10    ///
4.11    /// InsertionTsp implements the insertion heuristic for solving
4.12 @@ -74,9 +76,9 @@
4.13        ///
4.14        /// During the algorithm, nodes are selected for addition to the current
4.15        /// subtour according to the applied rule.
4.16 -      /// In general, the FARTHEST yields the best tours, thus it is the
4.17 -      /// default option. RANDOM usually gives somewhat worse results, but
4.18 -      /// it is much faster than the others and it is the most robust.
4.19 +      /// In general, the FARTHEST method yields the best tours, thus it is the
4.20 +      /// default option. The RANDOM rule usually gives somewhat worse results,
4.21 +      /// but it is much faster than the others and it is the most robust.
4.22        ///
4.23        /// The desired selection rule can be specified as a parameter of the
4.24        /// \ref run() function.
4.25 @@ -178,7 +180,7 @@
4.26        /// \brief Returns a const reference to the node sequence of the
4.27        /// found tour.
4.28        ///
4.29 -      /// This function returns a const reference to the internal structure
4.30 +      /// This function returns a const reference to a vector
4.31        /// that stores the node sequence of the found tour.
4.32        ///
4.33        /// \pre run() must be called before using this function.

     5.1 --- a/lemon/nearest_neighbor_tsp.h	Sat Jan 08 22:51:16 2011 +0100
5.2 +++ b/lemon/nearest_neighbor_tsp.h	Sun Jan 09 00:56:52 2011 +0100
5.3 @@ -24,12 +24,15 @@
5.4  /// \brief Nearest neighbor algorithm for symmetric TSP
5.5
5.6  #include <deque>
5.7 +#include <vector>
5.8  #include <limits>
5.9  #include <lemon/full_graph.h>
5.10  #include <lemon/maps.h>
5.11
5.12  namespace lemon {
5.13
5.14 +  /// \ingroup tsp
5.15 +  ///
5.16    /// \brief Nearest neighbor algorithm for symmetric TSP.
5.17    ///
5.18    /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
5.19 @@ -41,9 +44,8 @@
5.20    /// Finally, it connects the two end points of the path to form a tour.
5.21    ///
5.22    /// This method runs in O(n<sup>2</sup>) time.
5.23 -  /// It quickly finds an effectively short tour for most TSP
5.24 -  /// instances, but in special cases, it could yield a really bad
5.25 -  /// (or even the worst) solution.
5.26 +  /// It quickly finds a short tour for most TSP instances, but in special
5.27 +  /// cases, it could yield a really bad (or even the worst) solution.
5.28    ///
5.29    /// \tparam CM Type of the cost map.
5.30    template <typename CM>
5.31 @@ -63,7 +65,7 @@
5.32        const FullGraph &_gr;
5.33        const CostMap &_cost;
5.34        Cost _sum;
5.35 -      std::deque<Node> _path;
5.36 +      std::vector<Node> _path;
5.37
5.38      public:
5.39
5.40 @@ -85,28 +87,30 @@
5.41        /// \return The total cost of the found tour.
5.42        Cost run() {
5.43          _path.clear();
5.44 -
5.45 -        if (_gr.nodeNum() == 0) return _sum = 0;
5.46 +        if (_gr.nodeNum() == 0) {
5.47 +          return _sum = 0;
5.48 +        }
5.49          else if (_gr.nodeNum() == 1) {
5.50            _path.push_back(_gr(0));
5.51            return _sum = 0;
5.52          }
5.53
5.54 +        std::deque<Node> path_dq;
5.55          Edge min_edge1 = INVALID,
5.56               min_edge2 = INVALID;
5.57
5.58          min_edge1 = mapMin(_gr, _cost);
5.59          Node n1 = _gr.u(min_edge1),
5.60               n2 = _gr.v(min_edge1);
5.61 -        _path.push_back(n1);
5.62 -        _path.push_back(n2);
5.63 +        path_dq.push_back(n1);
5.64 +        path_dq.push_back(n2);
5.65
5.66          FullGraph::NodeMap<bool> used(_gr, false);
5.67          used[n1] = true;
5.68          used[n2] = true;
5.69
5.70          min_edge1 = INVALID;
5.71 -        while (int(_path.size()) != _gr.nodeNum()) {
5.72 +        while (int(path_dq.size()) != _gr.nodeNum()) {
5.73            if (min_edge1 == INVALID) {
5.74              for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
5.75                if (!used[_gr.runningNode(e)] &&
5.76 @@ -127,7 +131,7 @@
5.77
5.78            if (_cost[min_edge1] < _cost[min_edge2]) {
5.79              n1 = _gr.oppositeNode(n1, min_edge1);
5.80 -            _path.push_front(n1);
5.81 +            path_dq.push_front(n1);
5.82
5.83              used[n1] = true;
5.84              min_edge1 = INVALID;
5.85 @@ -136,7 +140,7 @@
5.86                min_edge2 = INVALID;
5.87            } else {
5.88              n2 = _gr.oppositeNode(n2, min_edge2);
5.89 -            _path.push_back(n2);
5.90 +            path_dq.push_back(n2);
5.91
5.92              used[n2] = true;
5.93              min_edge2 = INVALID;
5.94 @@ -146,9 +150,15 @@
5.95            }
5.96          }
5.97
5.98 -        _sum = _cost[_gr.edge(_path.back(), _path.front())];
5.99 -        for (int i = 0; i < int(_path.size())-1; ++i) {
5.100 -          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
5.101 +        n1 = path_dq.back();
5.102 +        n2 = path_dq.front();
5.103 +        _path.push_back(n2);
5.104 +        _sum = _cost[_gr.edge(n1, n2)];
5.105 +        for (int i = 1; i < int(path_dq.size()); ++i) {
5.106 +          n1 = n2;
5.107 +          n2 = path_dq[i];
5.108 +          _path.push_back(n2);
5.109 +          _sum += _cost[_gr.edge(n1, n2)];
5.110          }
5.111
5.112          return _sum;
5.113 @@ -171,11 +181,11 @@
5.114        /// \brief Returns a const reference to the node sequence of the
5.115        /// found tour.
5.116        ///
5.117 -      /// This function returns a const reference to the internal structure
5.118 +      /// This function returns a const reference to a vector
5.119        /// that stores the node sequence of the found tour.
5.120        ///
5.121        /// \pre run() must be called before using this function.
5.122 -      const std::deque<Node>& tourNodes() const {
5.123 +      const std::vector<Node>& tourNodes() const {
5.124          return _path;
5.125        }
5.126

     6.1 --- a/lemon/opt2_tsp.h	Sat Jan 08 22:51:16 2011 +0100
6.2 +++ b/lemon/opt2_tsp.h	Sun Jan 09 00:56:52 2011 +0100
6.3 @@ -21,13 +21,15 @@
6.4
6.5  /// \ingroup tsp
6.6  /// \file
6.7 -/// \brief 2-opt algorithm for symmetric TSP
6.8 +/// \brief 2-opt algorithm for symmetric TSP.
6.9
6.10  #include <vector>
6.11  #include <lemon/full_graph.h>
6.12
6.13  namespace lemon {
6.14
6.15 +  /// \ingroup tsp
6.16 +  ///
6.17    /// \brief 2-opt algorithm for symmetric TSP.
6.18    ///
6.19    /// Opt2Tsp implements the 2-opt heuristic for solving
6.20 @@ -114,7 +116,7 @@
6.21          return start();
6.22        }
6.23
6.24 -      /// \brief Runs the algorithm from the given tour.
6.25 +      /// \brief Runs the algorithm starting from the given tour.
6.26        ///
6.27        /// This function runs the algorithm starting from the given tour.
6.28        ///
6.29 @@ -156,16 +158,16 @@
6.30          return start();
6.31        }
6.32
6.33 -      /// \brief Runs the algorithm from the given tour.
6.34 +      /// \brief Runs the algorithm starting from the given tour.
6.35        ///
6.36 -      /// This function runs the algorithm starting from the given tour.
6.37 +      /// This function runs the algorithm starting from the given tour
6.38 +      /// (node sequence).
6.39        ///
6.40 -      /// \param tour The tour as a node sequence. It must be a standard
6.41 -      /// sequence container storing all <tt>Node</tt>s in the desired order.
6.42 +      /// \param tour A vector that stores all <tt>Node</tt>s of the graph
6.43 +      /// in the desired order.
6.44        ///
6.45        /// \return The total cost of the found tour.
6.46 -      template <template <typename> class Container>
6.47 -      Cost run(const Container<Node>& tour) {
6.48 +      Cost run(const std::vector<Node>& tour) {
6.49          _path.clear();
6.50
6.51          if (_gr.nodeNum() == 0) return _sum = 0;
6.52 @@ -180,7 +182,7 @@
6.53          }
6.54
6.55          _plist.resize(2*_gr.nodeNum());
6.56 -        typename Container<Node>::const_iterator it = tour.begin();
6.57 +        typename std::vector<Node>::const_iterator it = tour.begin();
6.58          int first = _gr.id(*it),
6.59              prev = first,
6.60              curr = _gr.id(*(++it)),
6.61 @@ -217,7 +219,7 @@
6.62        /// \brief Returns a const reference to the node sequence of the
6.63        /// found tour.
6.64        ///
6.65 -      /// This function returns a const reference to the internal structure
6.66 +      /// This function returns a const reference to a vector
6.67        /// that stores the node sequence of the found tour.
6.68        ///
6.69        /// \pre run() must be called before using this function.