Make InsertionTsp much faster and improve docs (#386)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 09 Jan 2011 15:06:55 +0100
changeset 1036dff32ce3db71
parent 1035 07682e24c4e8
child 1037 d3dcc49e6403
Make InsertionTsp much faster and improve docs (#386)
doc/groups.dox
lemon/christofides_tsp.h
lemon/greedy_tsp.h
lemon/insertion_tsp.h
lemon/nearest_neighbor_tsp.h
lemon/opt2_tsp.h
     1.1 --- a/doc/groups.dox	Sun Jan 09 00:57:12 2011 +0100
     1.2 +++ b/doc/groups.dox	Sun Jan 09 15:06:55 2011 +0100
     1.3 @@ -572,6 +572,16 @@
     1.4   - \ref ChristofidesTsp Christofides algorithm
     1.5   - \ref Opt2Tsp 2-opt algorithm
     1.6  
     1.7 +\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     1.8 +solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     1.9 +
    1.10 +\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
    1.11 +approximation factor: 3/2.
    1.12 +
    1.13 +\ref Opt2Tsp usually provides the best results in practice, but
    1.14 +it is the slowest method. It can also be used to improve given tours,
    1.15 +for example, the results of other algorithms.
    1.16 +
    1.17  \image html tsp.png
    1.18  \image latex tsp.eps "Traveling salesman problem" width=\textwidth
    1.19  */
     2.1 --- a/lemon/christofides_tsp.h	Sun Jan 09 00:57:12 2011 +0100
     2.2 +++ b/lemon/christofides_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     2.3 @@ -40,8 +40,9 @@
     2.4    ///
     2.5    /// This a well-known approximation method for the TSP problem with
     2.6    /// metric cost function.
     2.7 -  /// It yields a tour whose total cost is at most 3/2 of the optimum,
     2.8 -  /// but it is usually much better.
     2.9 +  /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour
    2.10 +  /// whose total cost is at most 3/2 of the optimum), but it usually
    2.11 +  /// provides better solutions in practice.
    2.12    /// This implementation runs in O(n<sup>3</sup>log(n)) time.
    2.13    ///
    2.14    /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
     3.1 --- a/lemon/greedy_tsp.h	Sun Jan 09 00:57:12 2011 +0100
     3.2 +++ b/lemon/greedy_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     3.3 @@ -43,9 +43,10 @@
     3.4    /// as long as it does not create a cycle of less than n edges and it does
     3.5    /// not increase the degree of any node above two.
     3.6    ///
     3.7 -  /// This method runs in O(n<sup>2</sup>log(n)) time.
     3.8 -  /// It quickly finds a short tour for most TSP instances, but in special
     3.9 -  /// cases, it could yield a really bad (or even the worst) solution.
    3.10 +  /// This method runs in O(n<sup>2</sup>) time.
    3.11 +  /// It quickly finds a relatively short tour for most TSP instances,
    3.12 +  /// but it could also yield a really bad (or even the worst) solution
    3.13 +  /// in special cases.
    3.14    ///
    3.15    /// \tparam CM Type of the cost map.
    3.16    template <typename CM>
     4.1 --- a/lemon/insertion_tsp.h	Sun Jan 09 00:57:12 2011 +0100
     4.2 +++ b/lemon/insertion_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     4.3 @@ -24,6 +24,7 @@
     4.4  /// \brief Insertion algorithm for symmetric TSP
     4.5  
     4.6  #include <vector>
     4.7 +#include <functional>
     4.8  #include <lemon/full_graph.h>
     4.9  #include <lemon/maps.h>
    4.10  #include <lemon/random.h>
    4.11 @@ -37,13 +38,20 @@
    4.12    /// InsertionTsp implements the insertion heuristic for solving
    4.13    /// symmetric \ref tsp "TSP".
    4.14    ///
    4.15 -  /// This is a basic TSP heuristic that has many variants.
    4.16 +  /// This is a fast and effective tour construction method that has
    4.17 +  /// many variants.
    4.18    /// It starts with a subtour containing a few nodes of the graph and it
    4.19    /// iteratively inserts the other nodes into this subtour according to a
    4.20    /// certain node selection rule.
    4.21    ///
    4.22 -  /// This implementation provides four different node selection rules,
    4.23 -  /// from which the most powerful one is used by default.
    4.24 +  /// This method is among the fastest TSP algorithms, and it typically
    4.25 +  /// provides quite good solutions (usually much better than
    4.26 +  /// \ref NearestNeighborTsp and \ref GreedyTsp).
    4.27 +  ///
    4.28 +  /// InsertionTsp implements four different node selection rules,
    4.29 +  /// from which the most effective one (\e farthest \e node \e selection)
    4.30 +  /// is used by default.
    4.31 +  /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
    4.32    /// For more information, see \ref SelectionRule.
    4.33    ///
    4.34    /// \tparam CM Type of the cost map.
    4.35 @@ -64,7 +72,7 @@
    4.36        const FullGraph &_gr;
    4.37        const CostMap &_cost;
    4.38        std::vector<Node> _notused;
    4.39 -      std::vector<Node> _path;
    4.40 +      std::vector<Node> _tour;
    4.41        Cost _sum;
    4.42  
    4.43      public:
    4.44 @@ -76,9 +84,10 @@
    4.45        ///
    4.46        /// During the algorithm, nodes are selected for addition to the current
    4.47        /// subtour according to the applied rule.
    4.48 -      /// In general, the FARTHEST method yields the best tours, thus it is the
    4.49 -      /// default option. The RANDOM rule usually gives somewhat worse results,
    4.50 -      /// but it is much faster than the others and it is the most robust.
    4.51 +      /// The FARTHEST method is one of the fastest selection rules, and
    4.52 +      /// it is typically the most effective, thus it is the default
    4.53 +      /// option. The RANDOM rule usually gives slightly worse results,
    4.54 +      /// but it is more robust.
    4.55        ///
    4.56        /// The desired selection rule can be specified as a parameter of the
    4.57        /// \ref run() function.
    4.58 @@ -86,20 +95,21 @@
    4.59  
    4.60          /// An unvisited node having minimum distance from the current
    4.61          /// subtour is selected at each step.
    4.62 -        /// The algorithm runs in O(n<sup>3</sup>) time using this
    4.63 +        /// The algorithm runs in O(n<sup>2</sup>) time using this
    4.64          /// selection rule.
    4.65          NEAREST,
    4.66  
    4.67          /// An unvisited node having maximum distance from the current
    4.68          /// subtour is selected at each step.
    4.69 -        /// The algorithm runs in O(n<sup>3</sup>) time using this
    4.70 +        /// The algorithm runs in O(n<sup>2</sup>) time using this
    4.71          /// selection rule.
    4.72          FARTHEST,
    4.73  
    4.74          /// An unvisited node whose insertion results in the least
    4.75          /// increase of the subtour's total cost is selected at each step.
    4.76          /// The algorithm runs in O(n<sup>3</sup>) time using this
    4.77 -        /// selection rule.
    4.78 +        /// selection rule, but in most cases, it is almost as fast as
    4.79 +        /// with other rules.
    4.80          CHEAPEST,
    4.81  
    4.82          /// An unvisited node is selected randomly without any evaluation
    4.83 @@ -134,22 +144,24 @@
    4.84        ///
    4.85        /// \return The total cost of the found tour.
    4.86        Cost run(SelectionRule rule = FARTHEST) {
    4.87 -        _path.clear();
    4.88 +        _tour.clear();
    4.89  
    4.90          if (_gr.nodeNum() == 0) return _sum = 0;
    4.91          else if (_gr.nodeNum() == 1) {
    4.92 -          _path.push_back(_gr(0));
    4.93 +          _tour.push_back(_gr(0));
    4.94            return _sum = 0;
    4.95          }
    4.96  
    4.97          switch (rule) {
    4.98            case NEAREST:
    4.99              init(true);
   4.100 -            start<NearestSelection, DefaultInsertion>();
   4.101 +            start<ComparingSelection<std::less<Cost> >,
   4.102 +                  DefaultInsertion>();
   4.103              break;
   4.104            case FARTHEST:
   4.105              init(false);
   4.106 -            start<FarthestSelection, DefaultInsertion>();
   4.107 +            start<ComparingSelection<std::greater<Cost> >,
   4.108 +                  DefaultInsertion>();
   4.109              break;
   4.110            case CHEAPEST:
   4.111              init(true);
   4.112 @@ -185,7 +197,7 @@
   4.113        ///
   4.114        /// \pre run() must be called before using this function.
   4.115        const std::vector<Node>& tourNodes() const {
   4.116 -        return _path;
   4.117 +        return _tour;
   4.118        }
   4.119  
   4.120        /// \brief Gives back the node sequence of the found tour.
   4.121 @@ -196,7 +208,7 @@
   4.122        /// \pre run() must be called before using this function.
   4.123        template <typename Container>
   4.124        void tourNodes(Container &container) const {
   4.125 -        container.assign(_path.begin(), _path.end());
   4.126 +        container.assign(_tour.begin(), _tour.end());
   4.127        }
   4.128  
   4.129        /// \brief Gives back the found tour as a path.
   4.130 @@ -208,11 +220,11 @@
   4.131        template <typename Path>
   4.132        void tour(Path &path) const {
   4.133          path.clear();
   4.134 -        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   4.135 -          path.addBack(_gr.arc(_path[i], _path[i+1]));
   4.136 +        for (int i = 0; i < int(_tour.size()) - 1; ++i) {
   4.137 +          path.addBack(_gr.arc(_tour[i], _tour[i+1]));
   4.138          }
   4.139 -        if (int(_path.size()) >= 2) {
   4.140 -          path.addBack(_gr.arc(_path.back(), _path.front()));
   4.141 +        if (int(_tour.size()) >= 2) {
   4.142 +          path.addBack(_gr.arc(_tour.back(), _tour.front()));
   4.143          }
   4.144        }
   4.145  
   4.146 @@ -224,9 +236,9 @@
   4.147        void init(bool min) {
   4.148          Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
   4.149  
   4.150 -        _path.clear();
   4.151 -        _path.push_back(_gr.u(min_edge));
   4.152 -        _path.push_back(_gr.v(min_edge));
   4.153 +        _tour.clear();
   4.154 +        _tour.push_back(_gr.u(min_edge));
   4.155 +        _tour.push_back(_gr.v(min_edge));
   4.156  
   4.157          _notused.clear();
   4.158          for (NodeIt n(_gr); n!=INVALID; ++n) {
   4.159 @@ -241,106 +253,82 @@
   4.160        // Executes the algorithm
   4.161        template <class SelectionFunctor, class InsertionFunctor>
   4.162        void start() {
   4.163 -        SelectionFunctor selectNode(_gr, _cost, _path, _notused);
   4.164 -        InsertionFunctor insertNode(_gr, _cost, _path, _sum);
   4.165 +        SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
   4.166 +        InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
   4.167  
   4.168          for (int i=0; i<_gr.nodeNum()-2; ++i) {
   4.169            insertNode.insert(selectNode.select());
   4.170          }
   4.171  
   4.172 -        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   4.173 -        for (int i = 0; i < int(_path.size())-1; ++i) {
   4.174 -          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   4.175 +        _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
   4.176 +        for (int i = 0; i < int(_tour.size())-1; ++i) {
   4.177 +          _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
   4.178          }
   4.179        }
   4.180  
   4.181  
   4.182 -      // Implementation of the nearest selection rule
   4.183 -      class NearestSelection {
   4.184 +      // Implementation of the nearest and farthest selection rule
   4.185 +      template <typename Comparator>
   4.186 +      class ComparingSelection {
   4.187          public:
   4.188 -          NearestSelection(const FullGraph &gr, const CostMap &cost,
   4.189 -                           std::vector<Node> &path, std::vector<Node> &notused)
   4.190 -            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
   4.191 -
   4.192 -          Node select() const {
   4.193 -            Cost insert_val = 0;
   4.194 -            int insert_node = -1;
   4.195 -
   4.196 +          ComparingSelection(const FullGraph &gr, const CostMap &cost,
   4.197 +                  std::vector<Node> &tour, std::vector<Node> &notused)
   4.198 +            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
   4.199 +              _dist(gr, 0), _compare()
   4.200 +          {
   4.201 +            // Compute initial distances for the unused nodes
   4.202              for (unsigned int i=0; i<_notused.size(); ++i) {
   4.203 -              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
   4.204 -              int min_node = 0;
   4.205 -
   4.206 -              for (unsigned int j=1; j<_path.size(); ++j) {
   4.207 -                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
   4.208 -                if (min_val > curr) {
   4.209 -                    min_val = curr;
   4.210 -                    min_node = j;
   4.211 +              Node u = _notused[i];
   4.212 +              Cost min_dist = _cost[_gr.edge(u, _tour[0])];
   4.213 +              for (unsigned int j=1; j<_tour.size(); ++j) {
   4.214 +                Cost curr = _cost[_gr.edge(u, _tour[j])];
   4.215 +                if (curr < min_dist) {
   4.216 +                  min_dist = curr;
   4.217                  }
   4.218                }
   4.219 +              _dist[u] = min_dist;
   4.220 +            }
   4.221 +          }
   4.222  
   4.223 -              if (insert_val > min_val || insert_node == -1) {
   4.224 -                insert_val = min_val;
   4.225 -                insert_node = i;
   4.226 +          Node select() {
   4.227 +
   4.228 +            // Select an used node with minimum distance
   4.229 +            Cost ins_dist = 0;
   4.230 +            int ins_node = -1;
   4.231 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   4.232 +              Cost curr = _dist[_notused[i]];
   4.233 +              if (_compare(curr, ins_dist) || ins_node == -1) {
   4.234 +                ins_dist = curr;
   4.235 +                ins_node = i;
   4.236                }
   4.237              }
   4.238  
   4.239 -            Node n = _notused[insert_node];
   4.240 -            _notused.erase(_notused.begin()+insert_node);
   4.241 +            // Remove the selected node from the unused vector
   4.242 +            Node sn = _notused[ins_node];
   4.243 +            _notused[ins_node] = _notused.back();
   4.244 +            _notused.pop_back();
   4.245  
   4.246 -            return n;
   4.247 +            // Update the distances of the remaining nodes
   4.248 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   4.249 +              Node u = _notused[i];
   4.250 +              Cost nc = _cost[_gr.edge(sn, u)];
   4.251 +              if (nc < _dist[u]) {
   4.252 +                _dist[u] = nc;
   4.253 +              }
   4.254 +            }
   4.255 +
   4.256 +            return sn;
   4.257            }
   4.258  
   4.259          private:
   4.260            const FullGraph &_gr;
   4.261            const CostMap &_cost;
   4.262 -          std::vector<Node> &_path;
   4.263 +          std::vector<Node> &_tour;
   4.264            std::vector<Node> &_notused;
   4.265 +          FullGraph::NodeMap<Cost> _dist;
   4.266 +          Comparator _compare;
   4.267        };
   4.268  
   4.269 -
   4.270 -      // Implementation of the farthest selection rule
   4.271 -      class FarthestSelection {
   4.272 -        public:
   4.273 -          FarthestSelection(const FullGraph &gr, const CostMap &cost,
   4.274 -                            std::vector<Node> &path, std::vector<Node> &notused)
   4.275 -            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
   4.276 -
   4.277 -          Node select() const {
   4.278 -            Cost insert_val = 0;
   4.279 -            int insert_node = -1;
   4.280 -
   4.281 -            for (unsigned int i=0; i<_notused.size(); ++i) {
   4.282 -              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
   4.283 -              int min_node = 0;
   4.284 -
   4.285 -              for (unsigned int j=1; j<_path.size(); ++j) {
   4.286 -                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
   4.287 -                if (min_val > curr) {
   4.288 -                  min_val = curr;
   4.289 -                  min_node = j;
   4.290 -                }
   4.291 -              }
   4.292 -
   4.293 -              if (insert_val < min_val || insert_node == -1) {
   4.294 -                insert_val = min_val;
   4.295 -                insert_node = i;
   4.296 -              }
   4.297 -            }
   4.298 -
   4.299 -            Node n = _notused[insert_node];
   4.300 -            _notused.erase(_notused.begin()+insert_node);
   4.301 -
   4.302 -            return n;
   4.303 -          }
   4.304 -
   4.305 -        private:
   4.306 -          const FullGraph &_gr;
   4.307 -          const CostMap &_cost;
   4.308 -          std::vector<Node> &_path;
   4.309 -          std::vector<Node> &_notused;
   4.310 -      };
   4.311 -
   4.312 -
   4.313        // Implementation of the cheapest selection rule
   4.314        class CheapestSelection {
   4.315          private:
   4.316 @@ -353,50 +341,102 @@
   4.317  
   4.318          public:
   4.319            CheapestSelection(const FullGraph &gr, const CostMap &cost,
   4.320 -                            std::vector<Node> &path, std::vector<Node> &notused)
   4.321 -            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
   4.322 -
   4.323 -          Cost select() const {
   4.324 -            int insert_notused = -1;
   4.325 -            int best_insert_index = -1;
   4.326 -            Cost insert_val = 0;
   4.327 -
   4.328 +                            std::vector<Node> &tour, std::vector<Node> &notused)
   4.329 +            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
   4.330 +              _ins_cost(gr, 0), _ins_pos(gr, -1)
   4.331 +          {
   4.332 +            // Compute insertion cost and position for the unused nodes
   4.333              for (unsigned int i=0; i<_notused.size(); ++i) {
   4.334 -              int min = i;
   4.335 -              int best_insert_tmp = 0;
   4.336 -              Cost min_val =
   4.337 -                costDiff(_path.front(), _path.back(), _notused[i]);
   4.338 -
   4.339 -              for (unsigned int j=1; j<_path.size(); ++j) {
   4.340 -                Cost tmp =
   4.341 -                  costDiff(_path[j-1], _path[j], _notused[i]);
   4.342 -
   4.343 -                if (min_val > tmp) {
   4.344 -                  min = i;
   4.345 -                  min_val = tmp;
   4.346 -                  best_insert_tmp = j;
   4.347 +              Node u = _notused[i];
   4.348 +              Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
   4.349 +              int min_pos = 0;              
   4.350 +              for (unsigned int j=1; j<_tour.size(); ++j) {
   4.351 +                Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
   4.352 +                if (curr_cost < min_cost) {
   4.353 +                  min_cost = curr_cost;
   4.354 +                  min_pos = j;
   4.355                  }
   4.356                }
   4.357 +              _ins_cost[u] = min_cost;
   4.358 +              _ins_pos[u] = min_pos;
   4.359 +            }
   4.360 +          }
   4.361  
   4.362 -              if (insert_val > min_val || insert_notused == -1) {
   4.363 -                insert_notused = min;
   4.364 -                insert_val = min_val;
   4.365 -                best_insert_index = best_insert_tmp;
   4.366 +          Cost select() {
   4.367 +
   4.368 +            // Select an used node with minimum insertion cost
   4.369 +            Cost min_cost = 0;
   4.370 +            int min_node = -1;
   4.371 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   4.372 +              Cost curr_cost = _ins_cost[_notused[i]];
   4.373 +              if (curr_cost < min_cost || min_node == -1) {
   4.374 +                min_cost = curr_cost;
   4.375 +                min_node = i;
   4.376                }
   4.377              }
   4.378  
   4.379 -            _path.insert(_path.begin()+best_insert_index,
   4.380 -                         _notused[insert_notused]);
   4.381 -            _notused.erase(_notused.begin()+insert_notused);
   4.382 +            // Remove the selected node from the unused vector
   4.383 +            Node sn = _notused[min_node];
   4.384 +            _notused[min_node] = _notused.back();
   4.385 +            _notused.pop_back();
   4.386 +            
   4.387 +            // Insert the selected node into the tour
   4.388 +            const int ipos = _ins_pos[sn];
   4.389 +            _tour.insert(_tour.begin() + ipos, sn);
   4.390  
   4.391 -            return insert_val;
   4.392 +            // Update the insertion cost and position of the remaining nodes
   4.393 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   4.394 +              Node u = _notused[i];
   4.395 +              Cost curr_cost = _ins_cost[u];
   4.396 +              int curr_pos = _ins_pos[u];
   4.397 +
   4.398 +              int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
   4.399 +              int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
   4.400 +              Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
   4.401 +              Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
   4.402 +              
   4.403 +              if (nc1 <= curr_cost || nc2 <= curr_cost) {
   4.404 +                // A new position is better than the old one
   4.405 +                if (nc1 <= nc2) {
   4.406 +                  curr_cost = nc1;
   4.407 +                  curr_pos = ipos;
   4.408 +                } else {
   4.409 +                  curr_cost = nc2;
   4.410 +                  curr_pos = ipos_next;
   4.411 +                }
   4.412 +              }
   4.413 +              else {
   4.414 +                if (curr_pos == ipos) {
   4.415 +                  // The minimum should be found again
   4.416 +                  curr_cost = costDiff(_tour.back(), _tour.front(), u);
   4.417 +                  curr_pos = 0;              
   4.418 +                  for (unsigned int j=1; j<_tour.size(); ++j) {
   4.419 +                    Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
   4.420 +                    if (tmp_cost < curr_cost) {
   4.421 +                      curr_cost = tmp_cost;
   4.422 +                      curr_pos = j;
   4.423 +                    }
   4.424 +                  }
   4.425 +                }
   4.426 +                else if (curr_pos > ipos) {
   4.427 +                  ++curr_pos;
   4.428 +                }
   4.429 +              }
   4.430 +              
   4.431 +              _ins_cost[u] = curr_cost;
   4.432 +              _ins_pos[u] = curr_pos;
   4.433 +            }
   4.434 +
   4.435 +            return min_cost;
   4.436            }
   4.437  
   4.438          private:
   4.439            const FullGraph &_gr;
   4.440            const CostMap &_cost;
   4.441 -          std::vector<Node> &_path;
   4.442 +          std::vector<Node> &_tour;
   4.443            std::vector<Node> &_notused;
   4.444 +          FullGraph::NodeMap<Cost> _ins_cost;
   4.445 +          FullGraph::NodeMap<int> _ins_pos;
   4.446        };
   4.447  
   4.448        // Implementation of the random selection rule
   4.449 @@ -409,9 +449,11 @@
   4.450            Node select() const {
   4.451              const int index = rnd[_notused.size()];
   4.452              Node n = _notused[index];
   4.453 -            _notused.erase(_notused.begin()+index);
   4.454 +            _notused[index] = _notused.back();
   4.455 +            _notused.pop_back();
   4.456              return n;
   4.457            }
   4.458 +
   4.459          private:
   4.460            std::vector<Node> &_notused;
   4.461        };
   4.462 @@ -429,30 +471,30 @@
   4.463  
   4.464          public:
   4.465            DefaultInsertion(const FullGraph &gr, const CostMap &cost,
   4.466 -                           std::vector<Node> &path, Cost &total_cost) :
   4.467 -            _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
   4.468 +                           std::vector<Node> &tour, Cost &total_cost) :
   4.469 +            _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
   4.470  
   4.471            void insert(Node n) const {
   4.472              int min = 0;
   4.473              Cost min_val =
   4.474 -              costDiff(_path.front(), _path.back(), n);
   4.475 +              costDiff(_tour.front(), _tour.back(), n);
   4.476  
   4.477 -            for (unsigned int i=1; i<_path.size(); ++i) {
   4.478 -              Cost tmp = costDiff(_path[i-1], _path[i], n);
   4.479 +            for (unsigned int i=1; i<_tour.size(); ++i) {
   4.480 +              Cost tmp = costDiff(_tour[i-1], _tour[i], n);
   4.481                if (tmp < min_val) {
   4.482                  min = i;
   4.483                  min_val = tmp;
   4.484                }
   4.485              }
   4.486  
   4.487 -            _path.insert(_path.begin()+min, n);
   4.488 +            _tour.insert(_tour.begin()+min, n);
   4.489              _total += min_val;
   4.490            }
   4.491  
   4.492          private:
   4.493            const FullGraph &_gr;
   4.494            const CostMap &_cost;
   4.495 -          std::vector<Node> &_path;
   4.496 +          std::vector<Node> &_tour;
   4.497            Cost &_total;
   4.498        };
   4.499  
     5.1 --- a/lemon/nearest_neighbor_tsp.h	Sun Jan 09 00:57:12 2011 +0100
     5.2 +++ b/lemon/nearest_neighbor_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     5.3 @@ -44,8 +44,9 @@
     5.4    /// Finally, it connects the two end points of the path to form a tour.
     5.5    ///
     5.6    /// This method runs in O(n<sup>2</sup>) time.
     5.7 -  /// It quickly finds a short tour for most TSP instances, but in special
     5.8 -  /// cases, it could yield a really bad (or even the worst) solution.
     5.9 +  /// It quickly finds a relatively short tour for most TSP instances,
    5.10 +  /// but it could also yield a really bad (or even the worst) solution
    5.11 +  /// in special cases.
    5.12    ///
    5.13    /// \tparam CM Type of the cost map.
    5.14    template <typename CM>
     6.1 --- a/lemon/opt2_tsp.h	Sun Jan 09 00:57:12 2011 +0100
     6.2 +++ b/lemon/opt2_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     6.3 @@ -45,9 +45,9 @@
     6.4    /// algorithm uses the node sequence determined by the node IDs.
     6.5    /// Oherwise, it starts with the given tour.
     6.6    ///
     6.7 -  /// This is a relatively slow but powerful method. 
     6.8 -  /// A typical usage of it is the improvement of a solution that is resulted
     6.9 -  /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
    6.10 +  /// This is a rather slow but effective method.
    6.11 +  /// Its typical usage is the improvement of the result of a fast tour
    6.12 +  /// construction heuristic (e.g. the InsertionTsp algorithm).
    6.13    ///
    6.14    /// \tparam CM Type of the cost map.
    6.15    template <typename CM>