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> ¬used)
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> ¬used)
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> ¬used)
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> ¬used)
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> ¬used)
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>