COIN-OR::LEMON - Graph Library

Changeset 1204:dff32ce3db71 in lemon


Ignore:
Timestamp:
01/09/11 15:06:55 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Make InsertionTsp? much faster and improve docs (#386)

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1202 r1204  
    573573 - \ref Opt2Tsp 2-opt algorithm
    574574
     575\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     576solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     577
     578\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     579approximation factor: 3/2.
     580
     581\ref Opt2Tsp usually provides the best results in practice, but
     582it is the slowest method. It can also be used to improve given tours,
     583for example, the results of other algorithms.
     584
    575585\image html tsp.png
    576586\image latex tsp.eps "Traveling salesman problem" width=\textwidth
  • lemon/christofides_tsp.h

    r1202 r1204  
    4141  /// This a well-known approximation method for the TSP problem with
    4242  /// metric cost function.
    43   /// It yields a tour whose total cost is at most 3/2 of the optimum,
    44   /// but it is usually much better.
     43  /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour
     44  /// whose total cost is at most 3/2 of the optimum), but it usually
     45  /// provides better solutions in practice.
    4546  /// This implementation runs in O(n<sup>3</sup>log(n)) time.
    4647  ///
  • lemon/greedy_tsp.h

    r1202 r1204  
    4444  /// not increase the degree of any node above two.
    4545  ///
    46   /// This method runs in O(n<sup>2</sup>log(n)) time.
    47   /// It quickly finds a short tour for most TSP instances, but in special
    48   /// cases, it could yield a really bad (or even the worst) solution.
     46  /// This method runs in O(n<sup>2</sup>) time.
     47  /// It quickly finds a relatively short tour for most TSP instances,
     48  /// but it could also yield a really bad (or even the worst) solution
     49  /// in special cases.
    4950  ///
    5051  /// \tparam CM Type of the cost map.
  • lemon/insertion_tsp.h

    r1202 r1204  
    2525
    2626#include <vector>
     27#include <functional>
    2728#include <lemon/full_graph.h>
    2829#include <lemon/maps.h>
     
    3839  /// symmetric \ref tsp "TSP".
    3940  ///
    40   /// This is a basic TSP heuristic that has many variants.
     41  /// This is a fast and effective tour construction method that has
     42  /// many variants.
    4143  /// It starts with a subtour containing a few nodes of the graph and it
    4244  /// iteratively inserts the other nodes into this subtour according to a
    4345  /// certain node selection rule.
    4446  ///
    45   /// This implementation provides four different node selection rules,
    46   /// from which the most powerful one is used by default.
     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.
    4755  /// For more information, see \ref SelectionRule.
    4856  ///
     
    6573      const CostMap &_cost;
    6674      std::vector<Node> _notused;
    67       std::vector<Node> _path;
     75      std::vector<Node> _tour;
    6876      Cost _sum;
    6977
     
    7785      /// During the algorithm, nodes are selected for addition to the current
    7886      /// subtour according to the applied rule.
    79       /// In general, the FARTHEST method yields the best tours, thus it is the
    80       /// default option. The RANDOM rule usually gives somewhat worse results,
    81       /// but it is much faster than the others and it is the most robust.
     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.
    8291      ///
    8392      /// The desired selection rule can be specified as a parameter of the
     
    8796        /// An unvisited node having minimum distance from the current
    8897        /// subtour is selected at each step.
    89         /// The algorithm runs in O(n<sup>3</sup>) time using this
     98        /// The algorithm runs in O(n<sup>2</sup>) time using this
    9099        /// selection rule.
    91100        NEAREST,
     
    93102        /// An unvisited node having maximum distance from the current
    94103        /// subtour is selected at each step.
    95         /// The algorithm runs in O(n<sup>3</sup>) time using this
     104        /// The algorithm runs in O(n<sup>2</sup>) time using this
    96105        /// selection rule.
    97106        FARTHEST,
     
    100109        /// increase of the subtour's total cost is selected at each step.
    101110        /// The algorithm runs in O(n<sup>3</sup>) time using this
    102         /// selection rule.
     111        /// selection rule, but in most cases, it is almost as fast as
     112        /// with other rules.
    103113        CHEAPEST,
    104114
     
    135145      /// \return The total cost of the found tour.
    136146      Cost run(SelectionRule rule = FARTHEST) {
    137         _path.clear();
     147        _tour.clear();
    138148
    139149        if (_gr.nodeNum() == 0) return _sum = 0;
    140150        else if (_gr.nodeNum() == 1) {
    141           _path.push_back(_gr(0));
     151          _tour.push_back(_gr(0));
    142152          return _sum = 0;
    143153        }
     
    146156          case NEAREST:
    147157            init(true);
    148             start<NearestSelection, DefaultInsertion>();
     158            start<ComparingSelection<std::less<Cost> >,
     159                  DefaultInsertion>();
    149160            break;
    150161          case FARTHEST:
    151162            init(false);
    152             start<FarthestSelection, DefaultInsertion>();
     163            start<ComparingSelection<std::greater<Cost> >,
     164                  DefaultInsertion>();
    153165            break;
    154166          case CHEAPEST:
     
    186198      /// \pre run() must be called before using this function.
    187199      const std::vector<Node>& tourNodes() const {
    188         return _path;
     200        return _tour;
    189201      }
    190202
     
    197209      template <typename Container>
    198210      void tourNodes(Container &container) const {
    199         container.assign(_path.begin(), _path.end());
     211        container.assign(_tour.begin(), _tour.end());
    200212      }
    201213
     
    209221      void tour(Path &path) const {
    210222        path.clear();
    211         for (int i = 0; i < int(_path.size()) - 1; ++i) {
    212           path.addBack(_gr.arc(_path[i], _path[i+1]));
    213         }
    214         if (int(_path.size()) >= 2) {
    215           path.addBack(_gr.arc(_path.back(), _path.front()));
     223        for (int i = 0; i < int(_tour.size()) - 1; ++i) {
     224          path.addBack(_gr.arc(_tour[i], _tour[i+1]));
     225        }
     226        if (int(_tour.size()) >= 2) {
     227          path.addBack(_gr.arc(_tour.back(), _tour.front()));
    216228        }
    217229      }
     
    225237        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
    226238
    227         _path.clear();
    228         _path.push_back(_gr.u(min_edge));
    229         _path.push_back(_gr.v(min_edge));
     239        _tour.clear();
     240        _tour.push_back(_gr.u(min_edge));
     241        _tour.push_back(_gr.v(min_edge));
    230242
    231243        _notused.clear();
     
    242254      template <class SelectionFunctor, class InsertionFunctor>
    243255      void start() {
    244         SelectionFunctor selectNode(_gr, _cost, _path, _notused);
    245         InsertionFunctor insertNode(_gr, _cost, _path, _sum);
     256        SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
     257        InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
    246258
    247259        for (int i=0; i<_gr.nodeNum()-2; ++i) {
     
    249261        }
    250262
    251         _sum = _cost[_gr.edge(_path.back(), _path.front())];
    252         for (int i = 0; i < int(_path.size())-1; ++i) {
    253           _sum += _cost[_gr.edge(_path[i], _path[i+1])];
    254         }
    255       }
    256 
    257 
    258       // Implementation of the nearest selection rule
    259       class NearestSelection {
     263        _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
     264        for (int i = 0; i < int(_tour.size())-1; ++i) {
     265          _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
     266        }
     267      }
     268
     269
     270      // Implementation of the nearest and farthest selection rule
     271      template <typename Comparator>
     272      class ComparingSelection {
    260273        public:
    261           NearestSelection(const FullGraph &gr, const CostMap &cost,
    262                            std::vector<Node> &path, std::vector<Node> &notused)
    263             : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
    264 
    265           Node select() const {
    266             Cost insert_val = 0;
    267             int insert_node = -1;
    268 
     274          ComparingSelection(const FullGraph &gr, const CostMap &cost,
     275                  std::vector<Node> &tour, std::vector<Node> &notused)
     276            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
     277              _dist(gr, 0), _compare()
     278          {
     279            // Compute initial distances for the unused nodes
    269280            for (unsigned int i=0; i<_notused.size(); ++i) {
    270               Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
    271               int min_node = 0;
    272 
    273               for (unsigned int j=1; j<_path.size(); ++j) {
    274                 Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
    275                 if (min_val > curr) {
    276                     min_val = curr;
    277                     min_node = j;
     281              Node u = _notused[i];
     282              Cost min_dist = _cost[_gr.edge(u, _tour[0])];
     283              for (unsigned int j=1; j<_tour.size(); ++j) {
     284                Cost curr = _cost[_gr.edge(u, _tour[j])];
     285                if (curr < min_dist) {
     286                  min_dist = curr;
    278287                }
    279288              }
    280 
    281               if (insert_val > min_val || insert_node == -1) {
    282                 insert_val = min_val;
    283                 insert_node = i;
    284               }
    285             }
    286 
    287             Node n = _notused[insert_node];
    288             _notused.erase(_notused.begin()+insert_node);
    289 
    290             return n;
     289              _dist[u] = min_dist;
     290            }
     291          }
     292
     293          Node select() {
     294
     295            // Select an used node with minimum distance
     296            Cost ins_dist = 0;
     297            int ins_node = -1;
     298            for (unsigned int i=0; i<_notused.size(); ++i) {
     299              Cost curr = _dist[_notused[i]];
     300              if (_compare(curr, ins_dist) || ins_node == -1) {
     301                ins_dist = curr;
     302                ins_node = i;
     303              }
     304            }
     305
     306            // Remove the selected node from the unused vector
     307            Node sn = _notused[ins_node];
     308            _notused[ins_node] = _notused.back();
     309            _notused.pop_back();
     310
     311            // Update the distances of the remaining nodes
     312            for (unsigned int i=0; i<_notused.size(); ++i) {
     313              Node u = _notused[i];
     314              Cost nc = _cost[_gr.edge(sn, u)];
     315              if (nc < _dist[u]) {
     316                _dist[u] = nc;
     317              }
     318            }
     319
     320            return sn;
    291321          }
    292322
     
    294324          const FullGraph &_gr;
    295325          const CostMap &_cost;
    296           std::vector<Node> &_path;
     326          std::vector<Node> &_tour;
    297327          std::vector<Node> &_notused;
     328          FullGraph::NodeMap<Cost> _dist;
     329          Comparator _compare;
    298330      };
    299 
    300 
    301       // Implementation of the farthest selection rule
    302       class FarthestSelection {
    303         public:
    304           FarthestSelection(const FullGraph &gr, const CostMap &cost,
    305                             std::vector<Node> &path, std::vector<Node> &notused)
    306             : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
    307 
    308           Node select() const {
    309             Cost insert_val = 0;
    310             int insert_node = -1;
    311 
    312             for (unsigned int i=0; i<_notused.size(); ++i) {
    313               Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
    314               int min_node = 0;
    315 
    316               for (unsigned int j=1; j<_path.size(); ++j) {
    317                 Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
    318                 if (min_val > curr) {
    319                   min_val = curr;
    320                   min_node = j;
    321                 }
    322               }
    323 
    324               if (insert_val < min_val || insert_node == -1) {
    325                 insert_val = min_val;
    326                 insert_node = i;
    327               }
    328             }
    329 
    330             Node n = _notused[insert_node];
    331             _notused.erase(_notused.begin()+insert_node);
    332 
    333             return n;
    334           }
    335 
    336         private:
    337           const FullGraph &_gr;
    338           const CostMap &_cost;
    339           std::vector<Node> &_path;
    340           std::vector<Node> &_notused;
    341       };
    342 
    343331
    344332      // Implementation of the cheapest selection rule
     
    354342        public:
    355343          CheapestSelection(const FullGraph &gr, const CostMap &cost,
    356                             std::vector<Node> &path, std::vector<Node> &notused)
    357             : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
    358 
    359           Cost select() const {
    360             int insert_notused = -1;
    361             int best_insert_index = -1;
    362             Cost insert_val = 0;
    363 
     344                            std::vector<Node> &tour, std::vector<Node> &notused)
     345            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
     346              _ins_cost(gr, 0), _ins_pos(gr, -1)
     347          {
     348            // Compute insertion cost and position for the unused nodes
    364349            for (unsigned int i=0; i<_notused.size(); ++i) {
    365               int min = i;
    366               int best_insert_tmp = 0;
    367               Cost min_val =
    368                 costDiff(_path.front(), _path.back(), _notused[i]);
    369 
    370               for (unsigned int j=1; j<_path.size(); ++j) {
    371                 Cost tmp =
    372                   costDiff(_path[j-1], _path[j], _notused[i]);
    373 
    374                 if (min_val > tmp) {
    375                   min = i;
    376                   min_val = tmp;
    377                   best_insert_tmp = j;
     350              Node u = _notused[i];
     351              Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
     352              int min_pos = 0;             
     353              for (unsigned int j=1; j<_tour.size(); ++j) {
     354                Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
     355                if (curr_cost < min_cost) {
     356                  min_cost = curr_cost;
     357                  min_pos = j;
    378358                }
    379359              }
    380 
    381               if (insert_val > min_val || insert_notused == -1) {
    382                 insert_notused = min;
    383                 insert_val = min_val;
    384                 best_insert_index = best_insert_tmp;
    385               }
    386             }
    387 
    388             _path.insert(_path.begin()+best_insert_index,
    389                          _notused[insert_notused]);
    390             _notused.erase(_notused.begin()+insert_notused);
    391 
    392             return insert_val;
     360              _ins_cost[u] = min_cost;
     361              _ins_pos[u] = min_pos;
     362            }
     363          }
     364
     365          Cost select() {
     366
     367            // Select an used node with minimum insertion cost
     368            Cost min_cost = 0;
     369            int min_node = -1;
     370            for (unsigned int i=0; i<_notused.size(); ++i) {
     371              Cost curr_cost = _ins_cost[_notused[i]];
     372              if (curr_cost < min_cost || min_node == -1) {
     373                min_cost = curr_cost;
     374                min_node = i;
     375              }
     376            }
     377
     378            // Remove the selected node from the unused vector
     379            Node sn = _notused[min_node];
     380            _notused[min_node] = _notused.back();
     381            _notused.pop_back();
     382           
     383            // Insert the selected node into the tour
     384            const int ipos = _ins_pos[sn];
     385            _tour.insert(_tour.begin() + ipos, sn);
     386
     387            // Update the insertion cost and position of the remaining nodes
     388            for (unsigned int i=0; i<_notused.size(); ++i) {
     389              Node u = _notused[i];
     390              Cost curr_cost = _ins_cost[u];
     391              int curr_pos = _ins_pos[u];
     392
     393              int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
     394              int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
     395              Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
     396              Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
     397             
     398              if (nc1 <= curr_cost || nc2 <= curr_cost) {
     399                // A new position is better than the old one
     400                if (nc1 <= nc2) {
     401                  curr_cost = nc1;
     402                  curr_pos = ipos;
     403                } else {
     404                  curr_cost = nc2;
     405                  curr_pos = ipos_next;
     406                }
     407              }
     408              else {
     409                if (curr_pos == ipos) {
     410                  // The minimum should be found again
     411                  curr_cost = costDiff(_tour.back(), _tour.front(), u);
     412                  curr_pos = 0;             
     413                  for (unsigned int j=1; j<_tour.size(); ++j) {
     414                    Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
     415                    if (tmp_cost < curr_cost) {
     416                      curr_cost = tmp_cost;
     417                      curr_pos = j;
     418                    }
     419                  }
     420                }
     421                else if (curr_pos > ipos) {
     422                  ++curr_pos;
     423                }
     424              }
     425             
     426              _ins_cost[u] = curr_cost;
     427              _ins_pos[u] = curr_pos;
     428            }
     429
     430            return min_cost;
    393431          }
    394432
     
    396434          const FullGraph &_gr;
    397435          const CostMap &_cost;
    398           std::vector<Node> &_path;
     436          std::vector<Node> &_tour;
    399437          std::vector<Node> &_notused;
     438          FullGraph::NodeMap<Cost> _ins_cost;
     439          FullGraph::NodeMap<int> _ins_pos;
    400440      };
    401441
     
    410450            const int index = rnd[_notused.size()];
    411451            Node n = _notused[index];
    412             _notused.erase(_notused.begin()+index);
     452            _notused[index] = _notused.back();
     453            _notused.pop_back();
    413454            return n;
    414455          }
     456
    415457        private:
    416458          std::vector<Node> &_notused;
     
    430472        public:
    431473          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
    432                            std::vector<Node> &path, Cost &total_cost) :
    433             _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
     474                           std::vector<Node> &tour, Cost &total_cost) :
     475            _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
    434476
    435477          void insert(Node n) const {
    436478            int min = 0;
    437479            Cost min_val =
    438               costDiff(_path.front(), _path.back(), n);
    439 
    440             for (unsigned int i=1; i<_path.size(); ++i) {
    441               Cost tmp = costDiff(_path[i-1], _path[i], n);
     480              costDiff(_tour.front(), _tour.back(), n);
     481
     482            for (unsigned int i=1; i<_tour.size(); ++i) {
     483              Cost tmp = costDiff(_tour[i-1], _tour[i], n);
    442484              if (tmp < min_val) {
    443485                min = i;
     
    446488            }
    447489
    448             _path.insert(_path.begin()+min, n);
     490            _tour.insert(_tour.begin()+min, n);
    449491            _total += min_val;
    450492          }
     
    453495          const FullGraph &_gr;
    454496          const CostMap &_cost;
    455           std::vector<Node> &_path;
     497          std::vector<Node> &_tour;
    456498          Cost &_total;
    457499      };
  • lemon/nearest_neighbor_tsp.h

    r1202 r1204  
    4545  ///
    4646  /// This method runs in O(n<sup>2</sup>) time.
    47   /// It quickly finds a short tour for most TSP instances, but in special
    48   /// cases, it could yield a really bad (or even the worst) solution.
     47  /// It quickly finds a relatively short tour for most TSP instances,
     48  /// but it could also yield a really bad (or even the worst) solution
     49  /// in special cases.
    4950  ///
    5051  /// \tparam CM Type of the cost map.
  • lemon/opt2_tsp.h

    r1202 r1204  
    4646  /// Oherwise, it starts with the given tour.
    4747  ///
    48   /// This is a relatively slow but powerful method.
    49   /// A typical usage of it is the improvement of a solution that is resulted
    50   /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
     48  /// This is a rather slow but effective method.
     49  /// Its typical usage is the improvement of the result of a fast tour
     50  /// construction heuristic (e.g. the InsertionTsp algorithm).
    5151  ///
    5252  /// \tparam CM Type of the cost map.
Note: See TracChangeset for help on using the changeset viewer.