COIN-OR::LEMON - Graph Library

Changeset 1204:dff32ce3db71 in lemon for 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)

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • 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.