lemon/insertion_tsp.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 06 Aug 2013 12:28:37 +0200
changeset 1079 5958cc5c0a98
parent 1037 d3dcc49e6403
child 1092 dceba191c00d
permissions -rw-r--r--
Merge further fixes #470
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_INSERTION_TSP_H
    20 #define LEMON_INSERTION_TSP_H
    21 
    22 /// \ingroup tsp
    23 /// \file
    24 /// \brief Insertion algorithm for symmetric TSP
    25 
    26 #include <vector>
    27 #include <functional>
    28 #include <lemon/full_graph.h>
    29 #include <lemon/maps.h>
    30 #include <lemon/random.h>
    31 
    32 namespace lemon {
    33 
    34   /// \ingroup tsp
    35   ///
    36   /// \brief Insertion algorithm for symmetric TSP.
    37   ///
    38   /// InsertionTsp implements the insertion heuristic for solving
    39   /// symmetric \ref tsp "TSP".
    40   ///
    41   /// This is a fast and effective tour construction method that has
    42   /// many variants.
    43   /// It starts with a subtour containing a few nodes of the graph and it
    44   /// iteratively inserts the other nodes into this subtour according to a
    45   /// certain node selection rule.
    46   ///
    47   /// This method is among the fastest TSP algorithms, and it typically
    48   /// provides quite good solutions (usually much better than
    49   /// \ref NearestNeighborTsp and \ref GreedyTsp).
    50   ///
    51   /// InsertionTsp implements four different node selection rules,
    52   /// from which the most effective one (\e farthest \e node \e selection)
    53   /// is used by default.
    54   /// With this choice, the algorithm runs in O(n<sup>2</sup>) time.
    55   /// For more information, see \ref SelectionRule.
    56   ///
    57   /// \tparam CM Type of the cost map.
    58   template <typename CM>
    59   class InsertionTsp
    60   {
    61     public:
    62 
    63       /// Type of the cost map
    64       typedef CM CostMap;
    65       /// Type of the edge costs
    66       typedef typename CM::Value Cost;
    67 
    68     private:
    69 
    70       GRAPH_TYPEDEFS(FullGraph);
    71 
    72       const FullGraph &_gr;
    73       const CostMap &_cost;
    74       std::vector<Node> _notused;
    75       std::vector<Node> _tour;
    76       Cost _sum;
    77 
    78     public:
    79 
    80       /// \brief Constants for specifying the node selection rule.
    81       ///
    82       /// Enum type containing constants for specifying the node selection
    83       /// rule for the \ref run() function.
    84       ///
    85       /// During the algorithm, nodes are selected for addition to the current
    86       /// subtour according to the applied rule.
    87       /// The FARTHEST method is one of the fastest selection rules, and
    88       /// it is typically the most effective, thus it is the default
    89       /// option. The RANDOM rule usually gives slightly worse results,
    90       /// but it is more robust.
    91       ///
    92       /// The desired selection rule can be specified as a parameter of the
    93       /// \ref run() function.
    94       enum SelectionRule {
    95 
    96         /// An unvisited node having minimum distance from the current
    97         /// subtour is selected at each step.
    98         /// The algorithm runs in O(n<sup>2</sup>) time using this
    99         /// selection rule.
   100         NEAREST,
   101 
   102         /// An unvisited node having maximum distance from the current
   103         /// subtour is selected at each step.
   104         /// The algorithm runs in O(n<sup>2</sup>) time using this
   105         /// selection rule.
   106         FARTHEST,
   107 
   108         /// An unvisited node whose insertion results in the least
   109         /// increase of the subtour's total cost is selected at each step.
   110         /// The algorithm runs in O(n<sup>3</sup>) time using this
   111         /// selection rule, but in most cases, it is almost as fast as
   112         /// with other rules.
   113         CHEAPEST,
   114 
   115         /// An unvisited node is selected randomly without any evaluation
   116         /// at each step.
   117         /// The global \ref rnd "random number generator instance" is used.
   118         /// You can seed it before executing the algorithm, if you
   119         /// would like to.
   120         /// The algorithm runs in O(n<sup>2</sup>) time using this
   121         /// selection rule.
   122         RANDOM
   123       };
   124 
   125     public:
   126 
   127       /// \brief Constructor
   128       ///
   129       /// Constructor.
   130       /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
   131       /// \param cost The cost map.
   132       InsertionTsp(const FullGraph &gr, const CostMap &cost)
   133         : _gr(gr), _cost(cost) {}
   134 
   135       /// \name Execution Control
   136       /// @{
   137 
   138       /// \brief Runs the algorithm.
   139       ///
   140       /// This function runs the algorithm.
   141       ///
   142       /// \param rule The node selection rule. For more information, see
   143       /// \ref SelectionRule.
   144       ///
   145       /// \return The total cost of the found tour.
   146       Cost run(SelectionRule rule = FARTHEST) {
   147         _tour.clear();
   148 
   149         if (_gr.nodeNum() == 0) return _sum = 0;
   150         else if (_gr.nodeNum() == 1) {
   151           _tour.push_back(_gr(0));
   152           return _sum = 0;
   153         }
   154 
   155         switch (rule) {
   156           case NEAREST:
   157             init(true);
   158             start<ComparingSelection<std::less<Cost> >,
   159                   DefaultInsertion>();
   160             break;
   161           case FARTHEST:
   162             init(false);
   163             start<ComparingSelection<std::greater<Cost> >,
   164                   DefaultInsertion>();
   165             break;
   166           case CHEAPEST:
   167             init(true);
   168             start<CheapestSelection, CheapestInsertion>();
   169             break;
   170           case RANDOM:
   171             init(true);
   172             start<RandomSelection, DefaultInsertion>();
   173             break;
   174         }
   175         return _sum;
   176       }
   177 
   178       /// @}
   179 
   180       /// \name Query Functions
   181       /// @{
   182 
   183       /// \brief The total cost of the found tour.
   184       ///
   185       /// This function returns the total cost of the found tour.
   186       ///
   187       /// \pre run() must be called before using this function.
   188       Cost tourCost() const {
   189         return _sum;
   190       }
   191 
   192       /// \brief Returns a const reference to the node sequence of the
   193       /// found tour.
   194       ///
   195       /// This function returns a const reference to a vector
   196       /// that stores the node sequence of the found tour.
   197       ///
   198       /// \pre run() must be called before using this function.
   199       const std::vector<Node>& tourNodes() const {
   200         return _tour;
   201       }
   202 
   203       /// \brief Gives back the node sequence of the found tour.
   204       ///
   205       /// This function copies the node sequence of the found tour into
   206       /// an STL container through the given output iterator. The
   207       /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
   208       /// For example,
   209       /// \code
   210       /// std::vector<FullGraph::Node> nodes(countNodes(graph));
   211       /// tsp.tourNodes(nodes.begin());
   212       /// \endcode
   213       /// or
   214       /// \code
   215       /// std::list<FullGraph::Node> nodes;
   216       /// tsp.tourNodes(std::back_inserter(nodes));
   217       /// \endcode
   218       ///
   219       /// \pre run() must be called before using this function.
   220       template <typename Iterator>
   221       void tourNodes(Iterator out) const {
   222         std::copy(_tour.begin(), _tour.end(), out);
   223       }
   224 
   225       /// \brief Gives back the found tour as a path.
   226       ///
   227       /// This function copies the found tour as a list of arcs/edges into
   228       /// the given \ref lemon::concepts::Path "path structure".
   229       ///
   230       /// \pre run() must be called before using this function.
   231       template <typename Path>
   232       void tour(Path &path) const {
   233         path.clear();
   234         for (int i = 0; i < int(_tour.size()) - 1; ++i) {
   235           path.addBack(_gr.arc(_tour[i], _tour[i+1]));
   236         }
   237         if (int(_tour.size()) >= 2) {
   238           path.addBack(_gr.arc(_tour.back(), _tour.front()));
   239         }
   240       }
   241 
   242       /// @}
   243 
   244     private:
   245 
   246       // Initializes the algorithm
   247       void init(bool min) {
   248         Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
   249 
   250         _tour.clear();
   251         _tour.push_back(_gr.u(min_edge));
   252         _tour.push_back(_gr.v(min_edge));
   253 
   254         _notused.clear();
   255         for (NodeIt n(_gr); n!=INVALID; ++n) {
   256           if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
   257             _notused.push_back(n);
   258           }
   259         }
   260 
   261         _sum = _cost[min_edge] * 2;
   262       }
   263 
   264       // Executes the algorithm
   265       template <class SelectionFunctor, class InsertionFunctor>
   266       void start() {
   267         SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
   268         InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
   269 
   270         for (int i=0; i<_gr.nodeNum()-2; ++i) {
   271           insertNode.insert(selectNode.select());
   272         }
   273 
   274         _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
   275         for (int i = 0; i < int(_tour.size())-1; ++i) {
   276           _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
   277         }
   278       }
   279 
   280 
   281       // Implementation of the nearest and farthest selection rule
   282       template <typename Comparator>
   283       class ComparingSelection {
   284         public:
   285           ComparingSelection(const FullGraph &gr, const CostMap &cost,
   286                   std::vector<Node> &tour, std::vector<Node> &notused)
   287             : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
   288               _dist(gr, 0), _compare()
   289           {
   290             // Compute initial distances for the unused nodes
   291             for (unsigned int i=0; i<_notused.size(); ++i) {
   292               Node u = _notused[i];
   293               Cost min_dist = _cost[_gr.edge(u, _tour[0])];
   294               for (unsigned int j=1; j<_tour.size(); ++j) {
   295                 Cost curr = _cost[_gr.edge(u, _tour[j])];
   296                 if (curr < min_dist) {
   297                   min_dist = curr;
   298                 }
   299               }
   300               _dist[u] = min_dist;
   301             }
   302           }
   303 
   304           Node select() {
   305 
   306             // Select an used node with minimum distance
   307             Cost ins_dist = 0;
   308             int ins_node = -1;
   309             for (unsigned int i=0; i<_notused.size(); ++i) {
   310               Cost curr = _dist[_notused[i]];
   311               if (_compare(curr, ins_dist) || ins_node == -1) {
   312                 ins_dist = curr;
   313                 ins_node = i;
   314               }
   315             }
   316 
   317             // Remove the selected node from the unused vector
   318             Node sn = _notused[ins_node];
   319             _notused[ins_node] = _notused.back();
   320             _notused.pop_back();
   321 
   322             // Update the distances of the remaining nodes
   323             for (unsigned int i=0; i<_notused.size(); ++i) {
   324               Node u = _notused[i];
   325               Cost nc = _cost[_gr.edge(sn, u)];
   326               if (nc < _dist[u]) {
   327                 _dist[u] = nc;
   328               }
   329             }
   330 
   331             return sn;
   332           }
   333 
   334         private:
   335           const FullGraph &_gr;
   336           const CostMap &_cost;
   337           std::vector<Node> &_tour;
   338           std::vector<Node> &_notused;
   339           FullGraph::NodeMap<Cost> _dist;
   340           Comparator _compare;
   341       };
   342 
   343       // Implementation of the cheapest selection rule
   344       class CheapestSelection {
   345         private:
   346           Cost costDiff(Node u, Node v, Node w) const {
   347             return
   348               _cost[_gr.edge(u, w)] +
   349               _cost[_gr.edge(v, w)] -
   350               _cost[_gr.edge(u, v)];
   351           }
   352 
   353         public:
   354           CheapestSelection(const FullGraph &gr, const CostMap &cost,
   355                             std::vector<Node> &tour, std::vector<Node> &notused)
   356             : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
   357               _ins_cost(gr, 0), _ins_pos(gr, -1)
   358           {
   359             // Compute insertion cost and position for the unused nodes
   360             for (unsigned int i=0; i<_notused.size(); ++i) {
   361               Node u = _notused[i];
   362               Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
   363               int min_pos = 0;              
   364               for (unsigned int j=1; j<_tour.size(); ++j) {
   365                 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
   366                 if (curr_cost < min_cost) {
   367                   min_cost = curr_cost;
   368                   min_pos = j;
   369                 }
   370               }
   371               _ins_cost[u] = min_cost;
   372               _ins_pos[u] = min_pos;
   373             }
   374           }
   375 
   376           Cost select() {
   377 
   378             // Select an used node with minimum insertion cost
   379             Cost min_cost = 0;
   380             int min_node = -1;
   381             for (unsigned int i=0; i<_notused.size(); ++i) {
   382               Cost curr_cost = _ins_cost[_notused[i]];
   383               if (curr_cost < min_cost || min_node == -1) {
   384                 min_cost = curr_cost;
   385                 min_node = i;
   386               }
   387             }
   388 
   389             // Remove the selected node from the unused vector
   390             Node sn = _notused[min_node];
   391             _notused[min_node] = _notused.back();
   392             _notused.pop_back();
   393             
   394             // Insert the selected node into the tour
   395             const int ipos = _ins_pos[sn];
   396             _tour.insert(_tour.begin() + ipos, sn);
   397 
   398             // Update the insertion cost and position of the remaining nodes
   399             for (unsigned int i=0; i<_notused.size(); ++i) {
   400               Node u = _notused[i];
   401               Cost curr_cost = _ins_cost[u];
   402               int curr_pos = _ins_pos[u];
   403 
   404               int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
   405               int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
   406               Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
   407               Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
   408               
   409               if (nc1 <= curr_cost || nc2 <= curr_cost) {
   410                 // A new position is better than the old one
   411                 if (nc1 <= nc2) {
   412                   curr_cost = nc1;
   413                   curr_pos = ipos;
   414                 } else {
   415                   curr_cost = nc2;
   416                   curr_pos = ipos_next;
   417                 }
   418               }
   419               else {
   420                 if (curr_pos == ipos) {
   421                   // The minimum should be found again
   422                   curr_cost = costDiff(_tour.back(), _tour.front(), u);
   423                   curr_pos = 0;              
   424                   for (unsigned int j=1; j<_tour.size(); ++j) {
   425                     Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
   426                     if (tmp_cost < curr_cost) {
   427                       curr_cost = tmp_cost;
   428                       curr_pos = j;
   429                     }
   430                   }
   431                 }
   432                 else if (curr_pos > ipos) {
   433                   ++curr_pos;
   434                 }
   435               }
   436               
   437               _ins_cost[u] = curr_cost;
   438               _ins_pos[u] = curr_pos;
   439             }
   440 
   441             return min_cost;
   442           }
   443 
   444         private:
   445           const FullGraph &_gr;
   446           const CostMap &_cost;
   447           std::vector<Node> &_tour;
   448           std::vector<Node> &_notused;
   449           FullGraph::NodeMap<Cost> _ins_cost;
   450           FullGraph::NodeMap<int> _ins_pos;
   451       };
   452 
   453       // Implementation of the random selection rule
   454       class RandomSelection {
   455         public:
   456           RandomSelection(const FullGraph &, const CostMap &,
   457                           std::vector<Node> &, std::vector<Node> &notused)
   458             : _notused(notused) {}
   459 
   460           Node select() const {
   461             const int index = rnd[_notused.size()];
   462             Node n = _notused[index];
   463             _notused[index] = _notused.back();
   464             _notused.pop_back();
   465             return n;
   466           }
   467 
   468         private:
   469           std::vector<Node> &_notused;
   470       };
   471 
   472 
   473       // Implementation of the default insertion method
   474       class DefaultInsertion {
   475         private:
   476           Cost costDiff(Node u, Node v, Node w) const {
   477             return
   478               _cost[_gr.edge(u, w)] +
   479               _cost[_gr.edge(v, w)] -
   480               _cost[_gr.edge(u, v)];
   481           }
   482 
   483         public:
   484           DefaultInsertion(const FullGraph &gr, const CostMap &cost,
   485                            std::vector<Node> &tour, Cost &total_cost) :
   486             _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
   487 
   488           void insert(Node n) const {
   489             int min = 0;
   490             Cost min_val =
   491               costDiff(_tour.front(), _tour.back(), n);
   492 
   493             for (unsigned int i=1; i<_tour.size(); ++i) {
   494               Cost tmp = costDiff(_tour[i-1], _tour[i], n);
   495               if (tmp < min_val) {
   496                 min = i;
   497                 min_val = tmp;
   498               }
   499             }
   500 
   501             _tour.insert(_tour.begin()+min, n);
   502             _total += min_val;
   503           }
   504 
   505         private:
   506           const FullGraph &_gr;
   507           const CostMap &_cost;
   508           std::vector<Node> &_tour;
   509           Cost &_total;
   510       };
   511 
   512       // Implementation of a special insertion method for the cheapest
   513       // selection rule
   514       class CheapestInsertion {
   515         TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
   516         public:
   517           CheapestInsertion(const FullGraph &, const CostMap &,
   518                             std::vector<Node> &, Cost &total_cost) :
   519             _total(total_cost) {}
   520 
   521           void insert(Cost diff) const {
   522             _total += diff;
   523           }
   524 
   525         private:
   526           Cost &_total;
   527       };
   528 
   529   };
   530 
   531 }; // namespace lemon
   532 
   533 #endif