COIN-OR::LEMON - Graph Library

Changeset 1201:9a51db038228 in lemon for lemon/insertion_tsp.h


Ignore:
Timestamp:
01/08/11 22:51:16 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Document and greatly improve TSP algorithms (#386)

  • Add LEMON headers.
  • Add Doxygen doc for all classes and their members.
  • Clarify and unify the public API of the algorithms.
  • Various small improvements in the implementations to make them clearer and faster.
  • Avoid using adaptors in ChristofidesTsp?.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/insertion_tsp.h

    r1199 r1201  
     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
    119#ifndef LEMON_INSERTION_TSP_H
    220#define LEMON_INSERTION_TSP_H
    321
     22/// \ingroup tsp
     23/// \file
     24/// \brief Insertion algorithm for symmetric TSP
     25
     26#include <vector>
    427#include <lemon/full_graph.h>
    5 #include <lemon/path.h>
    628#include <lemon/maps.h>
    729#include <lemon/random.h>
    8 #include <vector>
    930
    1031namespace lemon {
    1132
    12   namespace insertion_tsp_helper {
    13  
    14     template <class L>
    15     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    16       return L(_path.begin(), _path.end());
    17     };
    18  
    19     template <>
    20     std::vector<FullGraph::Node> vectorConvert(
    21         const std::vector<FullGraph::Node> &_path) {
    22       return _path;
    23     };
    24    
    25   };
    26 
     33  /// \brief Insertion algorithm for symmetric TSP.
     34  ///
     35  /// InsertionTsp implements the insertion heuristic for solving
     36  /// symmetric \ref tsp "TSP".
     37  ///
     38  /// This is a basic TSP heuristic that has many variants.
     39  /// It starts with a subtour containing a few nodes of the graph and it
     40  /// iteratively inserts the other nodes into this subtour according to a
     41  /// certain node selection rule.
     42  ///
     43  /// This implementation provides four different node selection rules,
     44  /// from which the most powerful one is used by default.
     45  /// For more information, see \ref SelectionRule.
     46  ///
     47  /// \tparam CM Type of the cost map.
    2748  template <typename CM>
    28   class InsertionTsp {
     49  class InsertionTsp
     50  {
     51    public:
     52
     53      /// Type of the cost map
     54      typedef CM CostMap;
     55      /// Type of the edge costs
     56      typedef typename CM::Value Cost;
     57
    2958    private:
     59
    3060      GRAPH_TYPEDEFS(FullGraph);
    3161
    32     public:     
    33       typedef CM CostMap;
    34       typedef typename CM::Value Cost;
    35      
    36       InsertionTsp(const FullGraph &gr, const CostMap &cost) :
    37             _gr(gr), _cost(cost) {}
    38      
    39       enum InsertionMethod {
    40         INSERT_NEAREST,
    41         INSERT_FARTHEST,
    42         INSERT_CHEAPEST,
    43         INSERT_RANDOM
    44       };     
    45      
    46       Cost run(InsertionMethod method = INSERT_FARTHEST) {
    47         switch (method) {
    48           case INSERT_NEAREST:
    49             start<InitTour<true>, NearestSelection, DefaultInsert>();
     62      const FullGraph &_gr;
     63      const CostMap &_cost;
     64      std::vector<Node> _notused;
     65      std::vector<Node> _path;
     66      Cost _sum;
     67
     68    public:
     69
     70      /// \brief Constants for specifying the node selection rule.
     71      ///
     72      /// Enum type containing constants for specifying the node selection
     73      /// rule for the \ref run() function.
     74      ///
     75      /// During the algorithm, nodes are selected for addition to the current
     76      /// subtour according to the applied rule.
     77      /// In general, the FARTHEST yields the best tours, thus it is the
     78      /// default option. RANDOM usually gives somewhat worse results, but
     79      /// it is much faster than the others and it is the most robust.
     80      ///
     81      /// The desired selection rule can be specified as a parameter of the
     82      /// \ref run() function.
     83      enum SelectionRule {
     84
     85        /// An unvisited node having minimum distance from the current
     86        /// subtour is selected at each step.
     87        /// The algorithm runs in O(n<sup>3</sup>) time using this
     88        /// selection rule.
     89        NEAREST,
     90
     91        /// An unvisited node having maximum distance from the current
     92        /// subtour is selected at each step.
     93        /// The algorithm runs in O(n<sup>3</sup>) time using this
     94        /// selection rule.
     95        FARTHEST,
     96
     97        /// An unvisited node whose insertion results in the least
     98        /// increase of the subtour's total cost is selected at each step.
     99        /// The algorithm runs in O(n<sup>3</sup>) time using this
     100        /// selection rule.
     101        CHEAPEST,
     102
     103        /// An unvisited node is selected randomly without any evaluation
     104        /// at each step.
     105        /// The global \ref rnd "random number generator instance" is used.
     106        /// You can seed it before executing the algorithm, if you
     107        /// would like to.
     108        /// The algorithm runs in O(n<sup>2</sup>) time using this
     109        /// selection rule.
     110        RANDOM
     111      };
     112
     113    public:
     114
     115      /// \brief Constructor
     116      ///
     117      /// Constructor.
     118      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     119      /// \param cost The cost map.
     120      InsertionTsp(const FullGraph &gr, const CostMap &cost)
     121        : _gr(gr), _cost(cost) {}
     122
     123      /// \name Execution Control
     124      /// @{
     125
     126      /// \brief Runs the algorithm.
     127      ///
     128      /// This function runs the algorithm.
     129      ///
     130      /// \param rule The node selection rule. For more information, see
     131      /// \ref SelectionRule.
     132      ///
     133      /// \return The total cost of the found tour.
     134      Cost run(SelectionRule rule = FARTHEST) {
     135        _path.clear();
     136
     137        if (_gr.nodeNum() == 0) return _sum = 0;
     138        else if (_gr.nodeNum() == 1) {
     139          _path.push_back(_gr(0));
     140          return _sum = 0;
     141        }
     142
     143        switch (rule) {
     144          case NEAREST:
     145            init(true);
     146            start<NearestSelection, DefaultInsertion>();
    50147            break;
    51           case INSERT_FARTHEST:
    52             start<InitTour<false>, FarthestSelection, DefaultInsert>();
     148          case FARTHEST:
     149            init(false);
     150            start<FarthestSelection, DefaultInsertion>();
    53151            break;
    54           case INSERT_CHEAPEST:
    55             start<InitTour<true>, CheapestSelection, CheapestInsert>();
     152          case CHEAPEST:
     153            init(true);
     154            start<CheapestSelection, CheapestInsertion>();
    56155            break;
    57           case INSERT_RANDOM:
    58             start<InitTour<true>, RandomSelection, DefaultInsert>();
     156          case RANDOM:
     157            init(true);
     158            start<RandomSelection, DefaultInsertion>();
    59159            break;
    60160        }
    61         return sum;
    62       }
    63 
    64       template <typename L>
    65       void tourNodes(L &container) {
    66         container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
    67       }
    68      
    69       template <template <typename> class L>
    70       L<Node> tourNodes() {
    71         return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
    72       }
    73      
    74       const std::vector<Node>& tourNodes() {
    75         return nodesPath;
    76       }
    77      
    78       Path<FullGraph> tour() {
    79         Path<FullGraph> p;
    80         if (nodesPath.size()<2)
    81           return p;
    82        
    83         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
    84           p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
    85        
    86         p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
    87         return p;
    88       }
    89      
    90       Cost tourCost() {
    91         return sum;
    92       }
    93 
     161        return _sum;
     162      }
     163
     164      /// @}
     165
     166      /// \name Query Functions
     167      /// @{
     168
     169      /// \brief The total cost of the found tour.
     170      ///
     171      /// This function returns the total cost of the found tour.
     172      ///
     173      /// \pre run() must be called before using this function.
     174      Cost tourCost() const {
     175        return _sum;
     176      }
     177
     178      /// \brief Returns a const reference to the node sequence of the
     179      /// found tour.
     180      ///
     181      /// This function returns a const reference to the internal structure
     182      /// that stores the node sequence of the found tour.
     183      ///
     184      /// \pre run() must be called before using this function.
     185      const std::vector<Node>& tourNodes() const {
     186        return _path;
     187      }
     188
     189      /// \brief Gives back the node sequence of the found tour.
     190      ///
     191      /// This function copies the node sequence of the found tour into
     192      /// the given standard container.
     193      ///
     194      /// \pre run() must be called before using this function.
     195      template <typename Container>
     196      void tourNodes(Container &container) const {
     197        container.assign(_path.begin(), _path.end());
     198      }
     199
     200      /// \brief Gives back the found tour as a path.
     201      ///
     202      /// This function copies the found tour as a list of arcs/edges into
     203      /// the given \ref concept::Path "path structure".
     204      ///
     205      /// \pre run() must be called before using this function.
     206      template <typename Path>
     207      void tour(Path &path) const {
     208        path.clear();
     209        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     210          path.addBack(_gr.arc(_path[i], _path[i+1]));
     211        }
     212        if (int(_path.size()) >= 2) {
     213          path.addBack(_gr.arc(_path.back(), _path.front()));
     214        }
     215      }
     216
     217      /// @}
    94218
    95219    private:
    96220
    97       template <bool MIN>
    98       class InitTour {
    99         public:
    100           InitTour(const FullGraph &gr, const CostMap &cost,
    101                    std::vector<Node> &used, std::vector<Node> &notused,
    102                    Cost &fullcost) :
    103               _gr(gr), _cost(cost), _used(used), _notused(notused),
    104               _fullcost(fullcost) {}
    105 
    106           std::vector<Node> init() const {
    107             Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
    108             std::vector<Node> path;
    109             path.push_back(_gr.u(min));
    110             path.push_back(_gr.v(min));
    111            
    112             _used.clear();
    113             _notused.clear();
    114             for (NodeIt n(_gr); n!=INVALID; ++n) {
    115               if (n != _gr.u(min) && n != _gr.v(min)) {
    116                 _notused.push_back(n);
     221      // Initializes the algorithm
     222      void init(bool min) {
     223        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
     224
     225        _path.clear();
     226        _path.push_back(_gr.u(min_edge));
     227        _path.push_back(_gr.v(min_edge));
     228
     229        _notused.clear();
     230        for (NodeIt n(_gr); n!=INVALID; ++n) {
     231          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
     232            _notused.push_back(n);
     233          }
     234        }
     235
     236        _sum = _cost[min_edge] * 2;
     237      }
     238
     239      // Executes the algorithm
     240      template <class SelectionFunctor, class InsertionFunctor>
     241      void start() {
     242        SelectionFunctor selectNode(_gr, _cost, _path, _notused);
     243        InsertionFunctor insertNode(_gr, _cost, _path, _sum);
     244
     245        for (int i=0; i<_gr.nodeNum()-2; ++i) {
     246          insertNode.insert(selectNode.select());
     247        }
     248
     249        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     250        for (int i = 0; i < int(_path.size())-1; ++i) {
     251          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     252        }
     253      }
     254
     255
     256      // Implementation of the nearest selection rule
     257      class NearestSelection {
     258        public:
     259          NearestSelection(const FullGraph &gr, const CostMap &cost,
     260                           std::vector<Node> &path, std::vector<Node> &notused)
     261            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
     262
     263          Node select() const {
     264            Cost insert_val = 0;
     265            int insert_node = -1;
     266
     267            for (unsigned int i=0; i<_notused.size(); ++i) {
     268              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
     269              int min_node = 0;
     270
     271              for (unsigned int j=1; j<_path.size(); ++j) {
     272                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
     273                if (min_val > curr) {
     274                    min_val = curr;
     275                    min_node = j;
     276                }
     277              }
     278
     279              if (insert_val > min_val || insert_node == -1) {
     280                insert_val = min_val;
     281                insert_node = i;
    117282              }
    118283            }
    119             _used.push_back(_gr.u(min));
    120             _used.push_back(_gr.v(min));
    121            
    122             _fullcost = _cost[min]*2;
    123             return path;
     284
     285            Node n = _notused[insert_node];
     286            _notused.erase(_notused.begin()+insert_node);
     287
     288            return n;
    124289          }
    125290
     
    127292          const FullGraph &_gr;
    128293          const CostMap &_cost;
    129           std::vector<Node> &_used;
     294          std::vector<Node> &_path;
    130295          std::vector<Node> &_notused;
    131           Cost &_fullcost;
    132       };
    133 
    134       class NearestSelection {
    135         public:
    136           NearestSelection(const FullGraph &gr, const CostMap &cost,
    137                            std::vector<Node> &used, std::vector<Node> &notused) :
    138               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
    139      
     296      };
     297
     298
     299      // Implementation of the farthest selection rule
     300      class FarthestSelection {
     301        public:
     302          FarthestSelection(const FullGraph &gr, const CostMap &cost,
     303                            std::vector<Node> &path, std::vector<Node> &notused)
     304            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
     305
    140306          Node select() const {
    141 
    142             Cost insert_val =
    143               std::numeric_limits<Cost>::max();
     307            Cost insert_val = 0;
    144308            int insert_node = -1;
    145            
     309
    146310            for (unsigned int i=0; i<_notused.size(); ++i) {
    147               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
     311              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
    148312              int min_node = 0;
    149            
    150               for (unsigned int j=1; j<_used.size(); ++j) {
    151                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
    152                     min_val = _cost[_gr.edge(_notused[i], _used[j])];
    153                     min_node = j;
    154                 }
    155               }
    156              
    157               if (insert_val > min_val) {
    158                 insert_val = min_val;
    159                 insert_node = i;
    160               }
    161             }
    162            
    163             Node n = _notused[insert_node];
    164             _notused.erase(_notused.begin()+insert_node);
    165            
    166             return n;
    167           }
    168          
    169         private:
    170           const FullGraph &_gr;
    171           const CostMap &_cost;
    172           std::vector<Node> &_used;
    173           std::vector<Node> &_notused;
    174       };
    175 
    176       class FarthestSelection {
    177         public:
    178           FarthestSelection(const FullGraph &gr, const CostMap &cost,
    179                             std::vector<Node> &used, std::vector<Node> &notused) :
    180               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
    181      
    182           Node select() const {
    183 
    184             Cost insert_val =
    185               std::numeric_limits<Cost>::min();
    186             int insert_node = -1;
    187            
    188             for (unsigned int i=0; i<_notused.size(); ++i) {
    189               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
    190               int min_node = 0;
    191              
    192               for (unsigned int j=1; j<_used.size(); ++j) {
    193                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
    194                   min_val = _cost[_gr.edge(_notused[i], _used[j])];
     313
     314              for (unsigned int j=1; j<_path.size(); ++j) {
     315                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
     316                if (min_val > curr) {
     317                  min_val = curr;
    195318                  min_node = j;
    196319                }
    197320              }
    198              
     321
    199322              if (insert_val < min_val || insert_node == -1) {
    200323                insert_val = min_val;
     
    202325              }
    203326            }
    204            
     327
    205328            Node n = _notused[insert_node];
    206329            _notused.erase(_notused.begin()+insert_node);
    207            
     330
    208331            return n;
    209332          }
    210          
     333
    211334        private:
    212335          const FullGraph &_gr;
    213336          const CostMap &_cost;
    214           std::vector<Node> &_used;
     337          std::vector<Node> &_path;
    215338          std::vector<Node> &_notused;
    216339      };
    217340
    218341
     342      // Implementation of the cheapest selection rule
    219343      class CheapestSelection {
    220344        private:
    221345          Cost costDiff(Node u, Node v, Node w) const {
    222             return 
     346            return
    223347              _cost[_gr.edge(u, w)] +
    224348              _cost[_gr.edge(v, w)] -
     
    228352        public:
    229353          CheapestSelection(const FullGraph &gr, const CostMap &cost,
    230                             std::vector<Node> &used, std::vector<Node> &notused) :
    231               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
    232        
     354                            std::vector<Node> &path, std::vector<Node> &notused)
     355            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
     356
    233357          Cost select() const {
    234358            int insert_notused = -1;
    235359            int best_insert_index = -1;
    236             Cost insert_val =
    237               std::numeric_limits<Cost>::max();
    238            
     360            Cost insert_val = 0;
     361
    239362            for (unsigned int i=0; i<_notused.size(); ++i) {
    240363              int min = i;
    241364              int best_insert_tmp = 0;
    242365              Cost min_val =
    243                 costDiff(_used.front(), _used.back(), _notused[i]);
    244              
    245               for (unsigned int j=1; j<_used.size(); ++j) {
     366                costDiff(_path.front(), _path.back(), _notused[i]);
     367
     368              for (unsigned int j=1; j<_path.size(); ++j) {
    246369                Cost tmp =
    247                   costDiff(_used[j-1], _used[j], _notused[i]);
     370                  costDiff(_path[j-1], _path[j], _notused[i]);
    248371
    249372                if (min_val > tmp) {
     
    254377              }
    255378
    256               if (insert_val > min_val) {
     379              if (insert_val > min_val || insert_notused == -1) {
    257380                insert_notused = min;
    258381                insert_val = min_val;
     
    261384            }
    262385
    263             _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
     386            _path.insert(_path.begin()+best_insert_index,
     387                         _notused[insert_notused]);
    264388            _notused.erase(_notused.begin()+insert_notused);
    265389
    266390            return insert_val;
    267391          }
    268          
     392
    269393        private:
    270394          const FullGraph &_gr;
    271395          const CostMap &_cost;
    272           std::vector<Node> &_used;
     396          std::vector<Node> &_path;
    273397          std::vector<Node> &_notused;
    274398      };
    275399
     400      // Implementation of the random selection rule
    276401      class RandomSelection {
    277402        public:
    278403          RandomSelection(const FullGraph &, const CostMap &,
    279                             std::vector<Node> &, std::vector<Node> &notused) :
    280                            _notused(notused) {
    281             rnd.seedFromTime();
    282           }
    283          
     404                          std::vector<Node> &, std::vector<Node> &notused)
     405            : _notused(notused) {}
     406
    284407          Node select() const {
    285408            const int index = rnd[_notused.size()];
     
    293416
    294417
    295       class DefaultInsert {
     418      // Implementation of the default insertion method
     419      class DefaultInsertion {
    296420        private:
    297421          Cost costDiff(Node u, Node v, Node w) const {
    298             return 
     422            return
    299423              _cost[_gr.edge(u, w)] +
    300424              _cost[_gr.edge(v, w)] -
    301425              _cost[_gr.edge(u, v)];
    302426          }
    303  
    304         public:
    305           DefaultInsert(const FullGraph &gr, const CostMap &cost,
    306                         std::vector<Node> &path, Cost &fullcost) :
    307             _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
    308          
     427
     428        public:
     429          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
     430                           std::vector<Node> &path, Cost &total_cost) :
     431            _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
     432
    309433          void insert(Node n) const {
    310434            int min = 0;
    311435            Cost min_val =
    312436              costDiff(_path.front(), _path.back(), n);
    313            
     437
    314438            for (unsigned int i=1; i<_path.size(); ++i) {
    315439              Cost tmp = costDiff(_path[i-1], _path[i], n);
     
    319443              }
    320444            }
    321            
     445
    322446            _path.insert(_path.begin()+min, n);
    323             _fullcost += min_val;
    324           }
    325        
     447            _total += min_val;
     448          }
     449
    326450        private:
    327451          const FullGraph &_gr;
    328452          const CostMap &_cost;
    329453          std::vector<Node> &_path;
    330           Cost &_fullcost;
    331       };
    332  
    333       class CheapestInsert {
     454          Cost &_total;
     455      };
     456
     457      // Implementation of a special insertion method for the cheapest
     458      // selection rule
     459      class CheapestInsertion {
    334460        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
    335461        public:
    336           CheapestInsert(const FullGraph &, const CostMap &,
    337                          std::vector<Node> &, Cost &fullcost) :
    338             _fullcost(fullcost) {}
    339          
     462          CheapestInsertion(const FullGraph &, const CostMap &,
     463                            std::vector<Node> &, Cost &total_cost) :
     464            _total(total_cost) {}
     465
    340466          void insert(Cost diff) const {
    341             _fullcost += diff;
    342           }
    343 
    344         private:
    345           Cost &_fullcost;
    346       }; 
    347      
    348      
    349       template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
    350       void start() {
    351         InitFunctor init(_gr, _cost, nodesPath, notused, sum);
    352         SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
    353         InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
    354        
    355         nodesPath = init.init();
    356        
    357         for (int i=0; i<_gr.nodeNum()-2; ++i) {
    358           insertNode.insert(selectNode.select());
    359         }
    360        
    361         sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
    362         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
    363           sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
    364       }
    365    
    366       const FullGraph &_gr;
    367       const CostMap &_cost;
    368       std::vector<Node> notused;
    369       std::vector<Node> nodesPath;
    370       Cost sum;
     467            _total += diff;
     468          }
     469
     470        private:
     471          Cost &_total;
     472      };
     473
    371474  };
    372  
     475
    373476}; // namespace lemon
    374477
Note: See TracChangeset for help on using the changeset viewer.