1.1 --- a/lemon/insertion_tsp.h Sun Jan 09 00:57:12 2011 +0100
1.2 +++ b/lemon/insertion_tsp.h Sun Jan 09 15:06:55 2011 +0100
1.3 @@ -24,6 +24,7 @@
1.4 /// \brief Insertion algorithm for symmetric TSP
1.5
1.6 #include <vector>
1.7 +#include <functional>
1.8 #include <lemon/full_graph.h>
1.9 #include <lemon/maps.h>
1.10 #include <lemon/random.h>
1.11 @@ -37,13 +38,20 @@
1.12 /// InsertionTsp implements the insertion heuristic for solving
1.13 /// symmetric \ref tsp "TSP".
1.14 ///
1.15 - /// This is a basic TSP heuristic that has many variants.
1.16 + /// This is a fast and effective tour construction method that has
1.17 + /// many variants.
1.18 /// It starts with a subtour containing a few nodes of the graph and it
1.19 /// iteratively inserts the other nodes into this subtour according to a
1.20 /// certain node selection rule.
1.21 ///
1.22 - /// This implementation provides four different node selection rules,
1.23 - /// from which the most powerful one is used by default.
1.24 + /// This method is among the fastest TSP algorithms, and it typically
1.25 + /// provides quite good solutions (usually much better than
1.26 + /// \ref NearestNeighborTsp and \ref GreedyTsp).
1.27 + ///
1.28 + /// InsertionTsp implements four different node selection rules,
1.29 + /// from which the most effective one (\e farthest \e node \e selection)
1.30 + /// is used by default.
1.31 + /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
1.32 /// For more information, see \ref SelectionRule.
1.33 ///
1.34 /// \tparam CM Type of the cost map.
1.35 @@ -64,7 +72,7 @@
1.36 const FullGraph &_gr;
1.37 const CostMap &_cost;
1.38 std::vector<Node> _notused;
1.39 - std::vector<Node> _path;
1.40 + std::vector<Node> _tour;
1.41 Cost _sum;
1.42
1.43 public:
1.44 @@ -76,9 +84,10 @@
1.45 ///
1.46 /// During the algorithm, nodes are selected for addition to the current
1.47 /// subtour according to the applied rule.
1.48 - /// In general, the FARTHEST method yields the best tours, thus it is the
1.49 - /// default option. The RANDOM rule usually gives somewhat worse results,
1.50 - /// but it is much faster than the others and it is the most robust.
1.51 + /// The FARTHEST method is one of the fastest selection rules, and
1.52 + /// it is typically the most effective, thus it is the default
1.53 + /// option. The RANDOM rule usually gives slightly worse results,
1.54 + /// but it is more robust.
1.55 ///
1.56 /// The desired selection rule can be specified as a parameter of the
1.57 /// \ref run() function.
1.58 @@ -86,20 +95,21 @@
1.59
1.60 /// An unvisited node having minimum distance from the current
1.61 /// subtour is selected at each step.
1.62 - /// The algorithm runs in O(n<sup>3</sup>) time using this
1.63 + /// The algorithm runs in O(n<sup>2</sup>) time using this
1.64 /// selection rule.
1.65 NEAREST,
1.66
1.67 /// An unvisited node having maximum distance from the current
1.68 /// subtour is selected at each step.
1.69 - /// The algorithm runs in O(n<sup>3</sup>) time using this
1.70 + /// The algorithm runs in O(n<sup>2</sup>) time using this
1.71 /// selection rule.
1.72 FARTHEST,
1.73
1.74 /// An unvisited node whose insertion results in the least
1.75 /// increase of the subtour's total cost is selected at each step.
1.76 /// The algorithm runs in O(n<sup>3</sup>) time using this
1.77 - /// selection rule.
1.78 + /// selection rule, but in most cases, it is almost as fast as
1.79 + /// with other rules.
1.80 CHEAPEST,
1.81
1.82 /// An unvisited node is selected randomly without any evaluation
1.83 @@ -134,22 +144,24 @@
1.84 ///
1.85 /// \return The total cost of the found tour.
1.86 Cost run(SelectionRule rule = FARTHEST) {
1.87 - _path.clear();
1.88 + _tour.clear();
1.89
1.90 if (_gr.nodeNum() == 0) return _sum = 0;
1.91 else if (_gr.nodeNum() == 1) {
1.92 - _path.push_back(_gr(0));
1.93 + _tour.push_back(_gr(0));
1.94 return _sum = 0;
1.95 }
1.96
1.97 switch (rule) {
1.98 case NEAREST:
1.99 init(true);
1.100 - start<NearestSelection, DefaultInsertion>();
1.101 + start<ComparingSelection<std::less<Cost> >,
1.102 + DefaultInsertion>();
1.103 break;
1.104 case FARTHEST:
1.105 init(false);
1.106 - start<FarthestSelection, DefaultInsertion>();
1.107 + start<ComparingSelection<std::greater<Cost> >,
1.108 + DefaultInsertion>();
1.109 break;
1.110 case CHEAPEST:
1.111 init(true);
1.112 @@ -185,7 +197,7 @@
1.113 ///
1.114 /// \pre run() must be called before using this function.
1.115 const std::vector<Node>& tourNodes() const {
1.116 - return _path;
1.117 + return _tour;
1.118 }
1.119
1.120 /// \brief Gives back the node sequence of the found tour.
1.121 @@ -196,7 +208,7 @@
1.122 /// \pre run() must be called before using this function.
1.123 template <typename Container>
1.124 void tourNodes(Container &container) const {
1.125 - container.assign(_path.begin(), _path.end());
1.126 + container.assign(_tour.begin(), _tour.end());
1.127 }
1.128
1.129 /// \brief Gives back the found tour as a path.
1.130 @@ -208,11 +220,11 @@
1.131 template <typename Path>
1.132 void tour(Path &path) const {
1.133 path.clear();
1.134 - for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.135 - path.addBack(_gr.arc(_path[i], _path[i+1]));
1.136 + for (int i = 0; i < int(_tour.size()) - 1; ++i) {
1.137 + path.addBack(_gr.arc(_tour[i], _tour[i+1]));
1.138 }
1.139 - if (int(_path.size()) >= 2) {
1.140 - path.addBack(_gr.arc(_path.back(), _path.front()));
1.141 + if (int(_tour.size()) >= 2) {
1.142 + path.addBack(_gr.arc(_tour.back(), _tour.front()));
1.143 }
1.144 }
1.145
1.146 @@ -224,9 +236,9 @@
1.147 void init(bool min) {
1.148 Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
1.149
1.150 - _path.clear();
1.151 - _path.push_back(_gr.u(min_edge));
1.152 - _path.push_back(_gr.v(min_edge));
1.153 + _tour.clear();
1.154 + _tour.push_back(_gr.u(min_edge));
1.155 + _tour.push_back(_gr.v(min_edge));
1.156
1.157 _notused.clear();
1.158 for (NodeIt n(_gr); n!=INVALID; ++n) {
1.159 @@ -241,106 +253,82 @@
1.160 // Executes the algorithm
1.161 template <class SelectionFunctor, class InsertionFunctor>
1.162 void start() {
1.163 - SelectionFunctor selectNode(_gr, _cost, _path, _notused);
1.164 - InsertionFunctor insertNode(_gr, _cost, _path, _sum);
1.165 + SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
1.166 + InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
1.167
1.168 for (int i=0; i<_gr.nodeNum()-2; ++i) {
1.169 insertNode.insert(selectNode.select());
1.170 }
1.171
1.172 - _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.173 - for (int i = 0; i < int(_path.size())-1; ++i) {
1.174 - _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.175 + _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
1.176 + for (int i = 0; i < int(_tour.size())-1; ++i) {
1.177 + _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
1.178 }
1.179 }
1.180
1.181
1.182 - // Implementation of the nearest selection rule
1.183 - class NearestSelection {
1.184 + // Implementation of the nearest and farthest selection rule
1.185 + template <typename Comparator>
1.186 + class ComparingSelection {
1.187 public:
1.188 - NearestSelection(const FullGraph &gr, const CostMap &cost,
1.189 - std::vector<Node> &path, std::vector<Node> ¬used)
1.190 - : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
1.191 -
1.192 - Node select() const {
1.193 - Cost insert_val = 0;
1.194 - int insert_node = -1;
1.195 -
1.196 + ComparingSelection(const FullGraph &gr, const CostMap &cost,
1.197 + std::vector<Node> &tour, std::vector<Node> ¬used)
1.198 + : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
1.199 + _dist(gr, 0), _compare()
1.200 + {
1.201 + // Compute initial distances for the unused nodes
1.202 for (unsigned int i=0; i<_notused.size(); ++i) {
1.203 - Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
1.204 - int min_node = 0;
1.205 -
1.206 - for (unsigned int j=1; j<_path.size(); ++j) {
1.207 - Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
1.208 - if (min_val > curr) {
1.209 - min_val = curr;
1.210 - min_node = j;
1.211 + Node u = _notused[i];
1.212 + Cost min_dist = _cost[_gr.edge(u, _tour[0])];
1.213 + for (unsigned int j=1; j<_tour.size(); ++j) {
1.214 + Cost curr = _cost[_gr.edge(u, _tour[j])];
1.215 + if (curr < min_dist) {
1.216 + min_dist = curr;
1.217 }
1.218 }
1.219 + _dist[u] = min_dist;
1.220 + }
1.221 + }
1.222
1.223 - if (insert_val > min_val || insert_node == -1) {
1.224 - insert_val = min_val;
1.225 - insert_node = i;
1.226 + Node select() {
1.227 +
1.228 + // Select an used node with minimum distance
1.229 + Cost ins_dist = 0;
1.230 + int ins_node = -1;
1.231 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.232 + Cost curr = _dist[_notused[i]];
1.233 + if (_compare(curr, ins_dist) || ins_node == -1) {
1.234 + ins_dist = curr;
1.235 + ins_node = i;
1.236 }
1.237 }
1.238
1.239 - Node n = _notused[insert_node];
1.240 - _notused.erase(_notused.begin()+insert_node);
1.241 + // Remove the selected node from the unused vector
1.242 + Node sn = _notused[ins_node];
1.243 + _notused[ins_node] = _notused.back();
1.244 + _notused.pop_back();
1.245
1.246 - return n;
1.247 + // Update the distances of the remaining nodes
1.248 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.249 + Node u = _notused[i];
1.250 + Cost nc = _cost[_gr.edge(sn, u)];
1.251 + if (nc < _dist[u]) {
1.252 + _dist[u] = nc;
1.253 + }
1.254 + }
1.255 +
1.256 + return sn;
1.257 }
1.258
1.259 private:
1.260 const FullGraph &_gr;
1.261 const CostMap &_cost;
1.262 - std::vector<Node> &_path;
1.263 + std::vector<Node> &_tour;
1.264 std::vector<Node> &_notused;
1.265 + FullGraph::NodeMap<Cost> _dist;
1.266 + Comparator _compare;
1.267 };
1.268
1.269 -
1.270 - // Implementation of the farthest selection rule
1.271 - class FarthestSelection {
1.272 - public:
1.273 - FarthestSelection(const FullGraph &gr, const CostMap &cost,
1.274 - std::vector<Node> &path, std::vector<Node> ¬used)
1.275 - : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
1.276 -
1.277 - Node select() const {
1.278 - Cost insert_val = 0;
1.279 - int insert_node = -1;
1.280 -
1.281 - for (unsigned int i=0; i<_notused.size(); ++i) {
1.282 - Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
1.283 - int min_node = 0;
1.284 -
1.285 - for (unsigned int j=1; j<_path.size(); ++j) {
1.286 - Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
1.287 - if (min_val > curr) {
1.288 - min_val = curr;
1.289 - min_node = j;
1.290 - }
1.291 - }
1.292 -
1.293 - if (insert_val < min_val || insert_node == -1) {
1.294 - insert_val = min_val;
1.295 - insert_node = i;
1.296 - }
1.297 - }
1.298 -
1.299 - Node n = _notused[insert_node];
1.300 - _notused.erase(_notused.begin()+insert_node);
1.301 -
1.302 - return n;
1.303 - }
1.304 -
1.305 - private:
1.306 - const FullGraph &_gr;
1.307 - const CostMap &_cost;
1.308 - std::vector<Node> &_path;
1.309 - std::vector<Node> &_notused;
1.310 - };
1.311 -
1.312 -
1.313 // Implementation of the cheapest selection rule
1.314 class CheapestSelection {
1.315 private:
1.316 @@ -353,50 +341,102 @@
1.317
1.318 public:
1.319 CheapestSelection(const FullGraph &gr, const CostMap &cost,
1.320 - std::vector<Node> &path, std::vector<Node> ¬used)
1.321 - : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
1.322 -
1.323 - Cost select() const {
1.324 - int insert_notused = -1;
1.325 - int best_insert_index = -1;
1.326 - Cost insert_val = 0;
1.327 -
1.328 + std::vector<Node> &tour, std::vector<Node> ¬used)
1.329 + : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
1.330 + _ins_cost(gr, 0), _ins_pos(gr, -1)
1.331 + {
1.332 + // Compute insertion cost and position for the unused nodes
1.333 for (unsigned int i=0; i<_notused.size(); ++i) {
1.334 - int min = i;
1.335 - int best_insert_tmp = 0;
1.336 - Cost min_val =
1.337 - costDiff(_path.front(), _path.back(), _notused[i]);
1.338 -
1.339 - for (unsigned int j=1; j<_path.size(); ++j) {
1.340 - Cost tmp =
1.341 - costDiff(_path[j-1], _path[j], _notused[i]);
1.342 -
1.343 - if (min_val > tmp) {
1.344 - min = i;
1.345 - min_val = tmp;
1.346 - best_insert_tmp = j;
1.347 + Node u = _notused[i];
1.348 + Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
1.349 + int min_pos = 0;
1.350 + for (unsigned int j=1; j<_tour.size(); ++j) {
1.351 + Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
1.352 + if (curr_cost < min_cost) {
1.353 + min_cost = curr_cost;
1.354 + min_pos = j;
1.355 }
1.356 }
1.357 + _ins_cost[u] = min_cost;
1.358 + _ins_pos[u] = min_pos;
1.359 + }
1.360 + }
1.361
1.362 - if (insert_val > min_val || insert_notused == -1) {
1.363 - insert_notused = min;
1.364 - insert_val = min_val;
1.365 - best_insert_index = best_insert_tmp;
1.366 + Cost select() {
1.367 +
1.368 + // Select an used node with minimum insertion cost
1.369 + Cost min_cost = 0;
1.370 + int min_node = -1;
1.371 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.372 + Cost curr_cost = _ins_cost[_notused[i]];
1.373 + if (curr_cost < min_cost || min_node == -1) {
1.374 + min_cost = curr_cost;
1.375 + min_node = i;
1.376 }
1.377 }
1.378
1.379 - _path.insert(_path.begin()+best_insert_index,
1.380 - _notused[insert_notused]);
1.381 - _notused.erase(_notused.begin()+insert_notused);
1.382 + // Remove the selected node from the unused vector
1.383 + Node sn = _notused[min_node];
1.384 + _notused[min_node] = _notused.back();
1.385 + _notused.pop_back();
1.386 +
1.387 + // Insert the selected node into the tour
1.388 + const int ipos = _ins_pos[sn];
1.389 + _tour.insert(_tour.begin() + ipos, sn);
1.390
1.391 - return insert_val;
1.392 + // Update the insertion cost and position of the remaining nodes
1.393 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.394 + Node u = _notused[i];
1.395 + Cost curr_cost = _ins_cost[u];
1.396 + int curr_pos = _ins_pos[u];
1.397 +
1.398 + int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
1.399 + int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
1.400 + Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
1.401 + Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
1.402 +
1.403 + if (nc1 <= curr_cost || nc2 <= curr_cost) {
1.404 + // A new position is better than the old one
1.405 + if (nc1 <= nc2) {
1.406 + curr_cost = nc1;
1.407 + curr_pos = ipos;
1.408 + } else {
1.409 + curr_cost = nc2;
1.410 + curr_pos = ipos_next;
1.411 + }
1.412 + }
1.413 + else {
1.414 + if (curr_pos == ipos) {
1.415 + // The minimum should be found again
1.416 + curr_cost = costDiff(_tour.back(), _tour.front(), u);
1.417 + curr_pos = 0;
1.418 + for (unsigned int j=1; j<_tour.size(); ++j) {
1.419 + Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
1.420 + if (tmp_cost < curr_cost) {
1.421 + curr_cost = tmp_cost;
1.422 + curr_pos = j;
1.423 + }
1.424 + }
1.425 + }
1.426 + else if (curr_pos > ipos) {
1.427 + ++curr_pos;
1.428 + }
1.429 + }
1.430 +
1.431 + _ins_cost[u] = curr_cost;
1.432 + _ins_pos[u] = curr_pos;
1.433 + }
1.434 +
1.435 + return min_cost;
1.436 }
1.437
1.438 private:
1.439 const FullGraph &_gr;
1.440 const CostMap &_cost;
1.441 - std::vector<Node> &_path;
1.442 + std::vector<Node> &_tour;
1.443 std::vector<Node> &_notused;
1.444 + FullGraph::NodeMap<Cost> _ins_cost;
1.445 + FullGraph::NodeMap<int> _ins_pos;
1.446 };
1.447
1.448 // Implementation of the random selection rule
1.449 @@ -409,9 +449,11 @@
1.450 Node select() const {
1.451 const int index = rnd[_notused.size()];
1.452 Node n = _notused[index];
1.453 - _notused.erase(_notused.begin()+index);
1.454 + _notused[index] = _notused.back();
1.455 + _notused.pop_back();
1.456 return n;
1.457 }
1.458 +
1.459 private:
1.460 std::vector<Node> &_notused;
1.461 };
1.462 @@ -429,30 +471,30 @@
1.463
1.464 public:
1.465 DefaultInsertion(const FullGraph &gr, const CostMap &cost,
1.466 - std::vector<Node> &path, Cost &total_cost) :
1.467 - _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
1.468 + std::vector<Node> &tour, Cost &total_cost) :
1.469 + _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
1.470
1.471 void insert(Node n) const {
1.472 int min = 0;
1.473 Cost min_val =
1.474 - costDiff(_path.front(), _path.back(), n);
1.475 + costDiff(_tour.front(), _tour.back(), n);
1.476
1.477 - for (unsigned int i=1; i<_path.size(); ++i) {
1.478 - Cost tmp = costDiff(_path[i-1], _path[i], n);
1.479 + for (unsigned int i=1; i<_tour.size(); ++i) {
1.480 + Cost tmp = costDiff(_tour[i-1], _tour[i], n);
1.481 if (tmp < min_val) {
1.482 min = i;
1.483 min_val = tmp;
1.484 }
1.485 }
1.486
1.487 - _path.insert(_path.begin()+min, n);
1.488 + _tour.insert(_tour.begin()+min, n);
1.489 _total += min_val;
1.490 }
1.491
1.492 private:
1.493 const FullGraph &_gr;
1.494 const CostMap &_cost;
1.495 - std::vector<Node> &_path;
1.496 + std::vector<Node> &_tour;
1.497 Cost &_total;
1.498 };
1.499