1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/insertion_tsp.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,533 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2013
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_INSERTION_TSP_H
1.23 +#define LEMON_INSERTION_TSP_H
1.24 +
1.25 +/// \ingroup tsp
1.26 +/// \file
1.27 +/// \brief Insertion algorithm for symmetric TSP
1.28 +
1.29 +#include <vector>
1.30 +#include <functional>
1.31 +#include <lemon/full_graph.h>
1.32 +#include <lemon/maps.h>
1.33 +#include <lemon/random.h>
1.34 +
1.35 +namespace lemon {
1.36 +
1.37 + /// \ingroup tsp
1.38 + ///
1.39 + /// \brief Insertion algorithm for symmetric TSP.
1.40 + ///
1.41 + /// InsertionTsp implements the insertion heuristic for solving
1.42 + /// symmetric \ref tsp "TSP".
1.43 + ///
1.44 + /// This is a fast and effective tour construction method that has
1.45 + /// many variants.
1.46 + /// It starts with a subtour containing a few nodes of the graph and it
1.47 + /// iteratively inserts the other nodes into this subtour according to a
1.48 + /// certain node selection rule.
1.49 + ///
1.50 + /// This method is among the fastest TSP algorithms, and it typically
1.51 + /// provides quite good solutions (usually much better than
1.52 + /// \ref NearestNeighborTsp and \ref GreedyTsp).
1.53 + ///
1.54 + /// InsertionTsp implements four different node selection rules,
1.55 + /// from which the most effective one (\e farthest \e node \e selection)
1.56 + /// is used by default.
1.57 + /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
1.58 + /// For more information, see \ref SelectionRule.
1.59 + ///
1.60 + /// \tparam CM Type of the cost map.
1.61 + template <typename CM>
1.62 + class InsertionTsp
1.63 + {
1.64 + public:
1.65 +
1.66 + /// Type of the cost map
1.67 + typedef CM CostMap;
1.68 + /// Type of the edge costs
1.69 + typedef typename CM::Value Cost;
1.70 +
1.71 + private:
1.72 +
1.73 + GRAPH_TYPEDEFS(FullGraph);
1.74 +
1.75 + const FullGraph &_gr;
1.76 + const CostMap &_cost;
1.77 + std::vector<Node> _notused;
1.78 + std::vector<Node> _tour;
1.79 + Cost _sum;
1.80 +
1.81 + public:
1.82 +
1.83 + /// \brief Constants for specifying the node selection rule.
1.84 + ///
1.85 + /// Enum type containing constants for specifying the node selection
1.86 + /// rule for the \ref run() function.
1.87 + ///
1.88 + /// During the algorithm, nodes are selected for addition to the current
1.89 + /// subtour according to the applied rule.
1.90 + /// The FARTHEST method is one of the fastest selection rules, and
1.91 + /// it is typically the most effective, thus it is the default
1.92 + /// option. The RANDOM rule usually gives slightly worse results,
1.93 + /// but it is more robust.
1.94 + ///
1.95 + /// The desired selection rule can be specified as a parameter of the
1.96 + /// \ref run() function.
1.97 + enum SelectionRule {
1.98 +
1.99 + /// An unvisited node having minimum distance from the current
1.100 + /// subtour is selected at each step.
1.101 + /// The algorithm runs in O(n<sup>2</sup>) time using this
1.102 + /// selection rule.
1.103 + NEAREST,
1.104 +
1.105 + /// An unvisited node having maximum distance from the current
1.106 + /// subtour is selected at each step.
1.107 + /// The algorithm runs in O(n<sup>2</sup>) time using this
1.108 + /// selection rule.
1.109 + FARTHEST,
1.110 +
1.111 + /// An unvisited node whose insertion results in the least
1.112 + /// increase of the subtour's total cost is selected at each step.
1.113 + /// The algorithm runs in O(n<sup>3</sup>) time using this
1.114 + /// selection rule, but in most cases, it is almost as fast as
1.115 + /// with other rules.
1.116 + CHEAPEST,
1.117 +
1.118 + /// An unvisited node is selected randomly without any evaluation
1.119 + /// at each step.
1.120 + /// The global \ref rnd "random number generator instance" is used.
1.121 + /// You can seed it before executing the algorithm, if you
1.122 + /// would like to.
1.123 + /// The algorithm runs in O(n<sup>2</sup>) time using this
1.124 + /// selection rule.
1.125 + RANDOM
1.126 + };
1.127 +
1.128 + public:
1.129 +
1.130 + /// \brief Constructor
1.131 + ///
1.132 + /// Constructor.
1.133 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.134 + /// \param cost The cost map.
1.135 + InsertionTsp(const FullGraph &gr, const CostMap &cost)
1.136 + : _gr(gr), _cost(cost) {}
1.137 +
1.138 + /// \name Execution Control
1.139 + /// @{
1.140 +
1.141 + /// \brief Runs the algorithm.
1.142 + ///
1.143 + /// This function runs the algorithm.
1.144 + ///
1.145 + /// \param rule The node selection rule. For more information, see
1.146 + /// \ref SelectionRule.
1.147 + ///
1.148 + /// \return The total cost of the found tour.
1.149 + Cost run(SelectionRule rule = FARTHEST) {
1.150 + _tour.clear();
1.151 +
1.152 + if (_gr.nodeNum() == 0) return _sum = 0;
1.153 + else if (_gr.nodeNum() == 1) {
1.154 + _tour.push_back(_gr(0));
1.155 + return _sum = 0;
1.156 + }
1.157 +
1.158 + switch (rule) {
1.159 + case NEAREST:
1.160 + init(true);
1.161 + start<ComparingSelection<std::less<Cost> >,
1.162 + DefaultInsertion>();
1.163 + break;
1.164 + case FARTHEST:
1.165 + init(false);
1.166 + start<ComparingSelection<std::greater<Cost> >,
1.167 + DefaultInsertion>();
1.168 + break;
1.169 + case CHEAPEST:
1.170 + init(true);
1.171 + start<CheapestSelection, CheapestInsertion>();
1.172 + break;
1.173 + case RANDOM:
1.174 + init(true);
1.175 + start<RandomSelection, DefaultInsertion>();
1.176 + break;
1.177 + }
1.178 + return _sum;
1.179 + }
1.180 +
1.181 + /// @}
1.182 +
1.183 + /// \name Query Functions
1.184 + /// @{
1.185 +
1.186 + /// \brief The total cost of the found tour.
1.187 + ///
1.188 + /// This function returns the total cost of the found tour.
1.189 + ///
1.190 + /// \pre run() must be called before using this function.
1.191 + Cost tourCost() const {
1.192 + return _sum;
1.193 + }
1.194 +
1.195 + /// \brief Returns a const reference to the node sequence of the
1.196 + /// found tour.
1.197 + ///
1.198 + /// This function returns a const reference to a vector
1.199 + /// that stores the node sequence of the found tour.
1.200 + ///
1.201 + /// \pre run() must be called before using this function.
1.202 + const std::vector<Node>& tourNodes() const {
1.203 + return _tour;
1.204 + }
1.205 +
1.206 + /// \brief Gives back the node sequence of the found tour.
1.207 + ///
1.208 + /// This function copies the node sequence of the found tour into
1.209 + /// an STL container through the given output iterator. The
1.210 + /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
1.211 + /// For example,
1.212 + /// \code
1.213 + /// std::vector<FullGraph::Node> nodes(countNodes(graph));
1.214 + /// tsp.tourNodes(nodes.begin());
1.215 + /// \endcode
1.216 + /// or
1.217 + /// \code
1.218 + /// std::list<FullGraph::Node> nodes;
1.219 + /// tsp.tourNodes(std::back_inserter(nodes));
1.220 + /// \endcode
1.221 + ///
1.222 + /// \pre run() must be called before using this function.
1.223 + template <typename Iterator>
1.224 + void tourNodes(Iterator out) const {
1.225 + std::copy(_tour.begin(), _tour.end(), out);
1.226 + }
1.227 +
1.228 + /// \brief Gives back the found tour as a path.
1.229 + ///
1.230 + /// This function copies the found tour as a list of arcs/edges into
1.231 + /// the given \ref lemon::concepts::Path "path structure".
1.232 + ///
1.233 + /// \pre run() must be called before using this function.
1.234 + template <typename Path>
1.235 + void tour(Path &path) const {
1.236 + path.clear();
1.237 + for (int i = 0; i < int(_tour.size()) - 1; ++i) {
1.238 + path.addBack(_gr.arc(_tour[i], _tour[i+1]));
1.239 + }
1.240 + if (int(_tour.size()) >= 2) {
1.241 + path.addBack(_gr.arc(_tour.back(), _tour.front()));
1.242 + }
1.243 + }
1.244 +
1.245 + /// @}
1.246 +
1.247 + private:
1.248 +
1.249 + // Initializes the algorithm
1.250 + void init(bool min) {
1.251 + Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
1.252 +
1.253 + _tour.clear();
1.254 + _tour.push_back(_gr.u(min_edge));
1.255 + _tour.push_back(_gr.v(min_edge));
1.256 +
1.257 + _notused.clear();
1.258 + for (NodeIt n(_gr); n!=INVALID; ++n) {
1.259 + if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
1.260 + _notused.push_back(n);
1.261 + }
1.262 + }
1.263 +
1.264 + _sum = _cost[min_edge] * 2;
1.265 + }
1.266 +
1.267 + // Executes the algorithm
1.268 + template <class SelectionFunctor, class InsertionFunctor>
1.269 + void start() {
1.270 + SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
1.271 + InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
1.272 +
1.273 + for (int i=0; i<_gr.nodeNum()-2; ++i) {
1.274 + insertNode.insert(selectNode.select());
1.275 + }
1.276 +
1.277 + _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
1.278 + for (int i = 0; i < int(_tour.size())-1; ++i) {
1.279 + _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
1.280 + }
1.281 + }
1.282 +
1.283 +
1.284 + // Implementation of the nearest and farthest selection rule
1.285 + template <typename Comparator>
1.286 + class ComparingSelection {
1.287 + public:
1.288 + ComparingSelection(const FullGraph &gr, const CostMap &cost,
1.289 + std::vector<Node> &tour, std::vector<Node> ¬used)
1.290 + : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
1.291 + _dist(gr, 0), _compare()
1.292 + {
1.293 + // Compute initial distances for the unused nodes
1.294 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.295 + Node u = _notused[i];
1.296 + Cost min_dist = _cost[_gr.edge(u, _tour[0])];
1.297 + for (unsigned int j=1; j<_tour.size(); ++j) {
1.298 + Cost curr = _cost[_gr.edge(u, _tour[j])];
1.299 + if (curr < min_dist) {
1.300 + min_dist = curr;
1.301 + }
1.302 + }
1.303 + _dist[u] = min_dist;
1.304 + }
1.305 + }
1.306 +
1.307 + Node select() {
1.308 +
1.309 + // Select an used node with minimum distance
1.310 + Cost ins_dist = 0;
1.311 + int ins_node = -1;
1.312 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.313 + Cost curr = _dist[_notused[i]];
1.314 + if (_compare(curr, ins_dist) || ins_node == -1) {
1.315 + ins_dist = curr;
1.316 + ins_node = i;
1.317 + }
1.318 + }
1.319 +
1.320 + // Remove the selected node from the unused vector
1.321 + Node sn = _notused[ins_node];
1.322 + _notused[ins_node] = _notused.back();
1.323 + _notused.pop_back();
1.324 +
1.325 + // Update the distances of the remaining nodes
1.326 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.327 + Node u = _notused[i];
1.328 + Cost nc = _cost[_gr.edge(sn, u)];
1.329 + if (nc < _dist[u]) {
1.330 + _dist[u] = nc;
1.331 + }
1.332 + }
1.333 +
1.334 + return sn;
1.335 + }
1.336 +
1.337 + private:
1.338 + const FullGraph &_gr;
1.339 + const CostMap &_cost;
1.340 + std::vector<Node> &_tour;
1.341 + std::vector<Node> &_notused;
1.342 + FullGraph::NodeMap<Cost> _dist;
1.343 + Comparator _compare;
1.344 + };
1.345 +
1.346 + // Implementation of the cheapest selection rule
1.347 + class CheapestSelection {
1.348 + private:
1.349 + Cost costDiff(Node u, Node v, Node w) const {
1.350 + return
1.351 + _cost[_gr.edge(u, w)] +
1.352 + _cost[_gr.edge(v, w)] -
1.353 + _cost[_gr.edge(u, v)];
1.354 + }
1.355 +
1.356 + public:
1.357 + CheapestSelection(const FullGraph &gr, const CostMap &cost,
1.358 + std::vector<Node> &tour, std::vector<Node> ¬used)
1.359 + : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
1.360 + _ins_cost(gr, 0), _ins_pos(gr, -1)
1.361 + {
1.362 + // Compute insertion cost and position for the unused nodes
1.363 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.364 + Node u = _notused[i];
1.365 + Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
1.366 + int min_pos = 0;
1.367 + for (unsigned int j=1; j<_tour.size(); ++j) {
1.368 + Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
1.369 + if (curr_cost < min_cost) {
1.370 + min_cost = curr_cost;
1.371 + min_pos = j;
1.372 + }
1.373 + }
1.374 + _ins_cost[u] = min_cost;
1.375 + _ins_pos[u] = min_pos;
1.376 + }
1.377 + }
1.378 +
1.379 + Cost select() {
1.380 +
1.381 + // Select an used node with minimum insertion cost
1.382 + Cost min_cost = 0;
1.383 + int min_node = -1;
1.384 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.385 + Cost curr_cost = _ins_cost[_notused[i]];
1.386 + if (curr_cost < min_cost || min_node == -1) {
1.387 + min_cost = curr_cost;
1.388 + min_node = i;
1.389 + }
1.390 + }
1.391 +
1.392 + // Remove the selected node from the unused vector
1.393 + Node sn = _notused[min_node];
1.394 + _notused[min_node] = _notused.back();
1.395 + _notused.pop_back();
1.396 +
1.397 + // Insert the selected node into the tour
1.398 + const int ipos = _ins_pos[sn];
1.399 + _tour.insert(_tour.begin() + ipos, sn);
1.400 +
1.401 + // Update the insertion cost and position of the remaining nodes
1.402 + for (unsigned int i=0; i<_notused.size(); ++i) {
1.403 + Node u = _notused[i];
1.404 + Cost curr_cost = _ins_cost[u];
1.405 + int curr_pos = _ins_pos[u];
1.406 +
1.407 + int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
1.408 + int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
1.409 + Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
1.410 + Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
1.411 +
1.412 + if (nc1 <= curr_cost || nc2 <= curr_cost) {
1.413 + // A new position is better than the old one
1.414 + if (nc1 <= nc2) {
1.415 + curr_cost = nc1;
1.416 + curr_pos = ipos;
1.417 + } else {
1.418 + curr_cost = nc2;
1.419 + curr_pos = ipos_next;
1.420 + }
1.421 + }
1.422 + else {
1.423 + if (curr_pos == ipos) {
1.424 + // The minimum should be found again
1.425 + curr_cost = costDiff(_tour.back(), _tour.front(), u);
1.426 + curr_pos = 0;
1.427 + for (unsigned int j=1; j<_tour.size(); ++j) {
1.428 + Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
1.429 + if (tmp_cost < curr_cost) {
1.430 + curr_cost = tmp_cost;
1.431 + curr_pos = j;
1.432 + }
1.433 + }
1.434 + }
1.435 + else if (curr_pos > ipos) {
1.436 + ++curr_pos;
1.437 + }
1.438 + }
1.439 +
1.440 + _ins_cost[u] = curr_cost;
1.441 + _ins_pos[u] = curr_pos;
1.442 + }
1.443 +
1.444 + return min_cost;
1.445 + }
1.446 +
1.447 + private:
1.448 + const FullGraph &_gr;
1.449 + const CostMap &_cost;
1.450 + std::vector<Node> &_tour;
1.451 + std::vector<Node> &_notused;
1.452 + FullGraph::NodeMap<Cost> _ins_cost;
1.453 + FullGraph::NodeMap<int> _ins_pos;
1.454 + };
1.455 +
1.456 + // Implementation of the random selection rule
1.457 + class RandomSelection {
1.458 + public:
1.459 + RandomSelection(const FullGraph &, const CostMap &,
1.460 + std::vector<Node> &, std::vector<Node> ¬used)
1.461 + : _notused(notused) {}
1.462 +
1.463 + Node select() const {
1.464 + const int index = rnd[_notused.size()];
1.465 + Node n = _notused[index];
1.466 + _notused[index] = _notused.back();
1.467 + _notused.pop_back();
1.468 + return n;
1.469 + }
1.470 +
1.471 + private:
1.472 + std::vector<Node> &_notused;
1.473 + };
1.474 +
1.475 +
1.476 + // Implementation of the default insertion method
1.477 + class DefaultInsertion {
1.478 + private:
1.479 + Cost costDiff(Node u, Node v, Node w) const {
1.480 + return
1.481 + _cost[_gr.edge(u, w)] +
1.482 + _cost[_gr.edge(v, w)] -
1.483 + _cost[_gr.edge(u, v)];
1.484 + }
1.485 +
1.486 + public:
1.487 + DefaultInsertion(const FullGraph &gr, const CostMap &cost,
1.488 + std::vector<Node> &tour, Cost &total_cost) :
1.489 + _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
1.490 +
1.491 + void insert(Node n) const {
1.492 + int min = 0;
1.493 + Cost min_val =
1.494 + costDiff(_tour.front(), _tour.back(), n);
1.495 +
1.496 + for (unsigned int i=1; i<_tour.size(); ++i) {
1.497 + Cost tmp = costDiff(_tour[i-1], _tour[i], n);
1.498 + if (tmp < min_val) {
1.499 + min = i;
1.500 + min_val = tmp;
1.501 + }
1.502 + }
1.503 +
1.504 + _tour.insert(_tour.begin()+min, n);
1.505 + _total += min_val;
1.506 + }
1.507 +
1.508 + private:
1.509 + const FullGraph &_gr;
1.510 + const CostMap &_cost;
1.511 + std::vector<Node> &_tour;
1.512 + Cost &_total;
1.513 + };
1.514 +
1.515 + // Implementation of a special insertion method for the cheapest
1.516 + // selection rule
1.517 + class CheapestInsertion {
1.518 + TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
1.519 + public:
1.520 + CheapestInsertion(const FullGraph &, const CostMap &,
1.521 + std::vector<Node> &, Cost &total_cost) :
1.522 + _total(total_cost) {}
1.523 +
1.524 + void insert(Cost diff) const {
1.525 + _total += diff;
1.526 + }
1.527 +
1.528 + private:
1.529 + Cost &_total;
1.530 + };
1.531 +
1.532 + };
1.533 +
1.534 +}; // namespace lemon
1.535 +
1.536 +#endif