COIN-OR::LEMON - Graph Library

source: lemon/lemon/insertion_tsp.h @ 1204:dff32ce3db71

Last change on this file since 1204:dff32ce3db71 was 1204:dff32ce3db71, checked in by Peter Kovacs <kpeter@…>, 11 years ago

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

File size: 16.4 KB
Line 
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
32namespace 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      /// the given standard container.
207      ///
208      /// \pre run() must be called before using this function.
209      template <typename Container>
210      void tourNodes(Container &container) const {
211        container.assign(_tour.begin(), _tour.end());
212      }
213
214      /// \brief Gives back the found tour as a path.
215      ///
216      /// This function copies the found tour as a list of arcs/edges into
217      /// the given \ref concept::Path "path structure".
218      ///
219      /// \pre run() must be called before using this function.
220      template <typename Path>
221      void tour(Path &path) const {
222        path.clear();
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()));
228        }
229      }
230
231      /// @}
232
233    private:
234
235      // Initializes the algorithm
236      void init(bool min) {
237        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
238
239        _tour.clear();
240        _tour.push_back(_gr.u(min_edge));
241        _tour.push_back(_gr.v(min_edge));
242
243        _notused.clear();
244        for (NodeIt n(_gr); n!=INVALID; ++n) {
245          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
246            _notused.push_back(n);
247          }
248        }
249
250        _sum = _cost[min_edge] * 2;
251      }
252
253      // Executes the algorithm
254      template <class SelectionFunctor, class InsertionFunctor>
255      void start() {
256        SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
257        InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
258
259        for (int i=0; i<_gr.nodeNum()-2; ++i) {
260          insertNode.insert(selectNode.select());
261        }
262
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 {
273        public:
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
280            for (unsigned int i=0; i<_notused.size(); ++i) {
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;
287                }
288              }
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;
321          }
322
323        private:
324          const FullGraph &_gr;
325          const CostMap &_cost;
326          std::vector<Node> &_tour;
327          std::vector<Node> &_notused;
328          FullGraph::NodeMap<Cost> _dist;
329          Comparator _compare;
330      };
331
332      // Implementation of the cheapest selection rule
333      class CheapestSelection {
334        private:
335          Cost costDiff(Node u, Node v, Node w) const {
336            return
337              _cost[_gr.edge(u, w)] +
338              _cost[_gr.edge(v, w)] -
339              _cost[_gr.edge(u, v)];
340          }
341
342        public:
343          CheapestSelection(const FullGraph &gr, const CostMap &cost,
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
349            for (unsigned int i=0; i<_notused.size(); ++i) {
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;
358                }
359              }
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;
431          }
432
433        private:
434          const FullGraph &_gr;
435          const CostMap &_cost;
436          std::vector<Node> &_tour;
437          std::vector<Node> &_notused;
438          FullGraph::NodeMap<Cost> _ins_cost;
439          FullGraph::NodeMap<int> _ins_pos;
440      };
441
442      // Implementation of the random selection rule
443      class RandomSelection {
444        public:
445          RandomSelection(const FullGraph &, const CostMap &,
446                          std::vector<Node> &, std::vector<Node> &notused)
447            : _notused(notused) {}
448
449          Node select() const {
450            const int index = rnd[_notused.size()];
451            Node n = _notused[index];
452            _notused[index] = _notused.back();
453            _notused.pop_back();
454            return n;
455          }
456
457        private:
458          std::vector<Node> &_notused;
459      };
460
461
462      // Implementation of the default insertion method
463      class DefaultInsertion {
464        private:
465          Cost costDiff(Node u, Node v, Node w) const {
466            return
467              _cost[_gr.edge(u, w)] +
468              _cost[_gr.edge(v, w)] -
469              _cost[_gr.edge(u, v)];
470          }
471
472        public:
473          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
474                           std::vector<Node> &tour, Cost &total_cost) :
475            _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
476
477          void insert(Node n) const {
478            int min = 0;
479            Cost min_val =
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);
484              if (tmp < min_val) {
485                min = i;
486                min_val = tmp;
487              }
488            }
489
490            _tour.insert(_tour.begin()+min, n);
491            _total += min_val;
492          }
493
494        private:
495          const FullGraph &_gr;
496          const CostMap &_cost;
497          std::vector<Node> &_tour;
498          Cost &_total;
499      };
500
501      // Implementation of a special insertion method for the cheapest
502      // selection rule
503      class CheapestInsertion {
504        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
505        public:
506          CheapestInsertion(const FullGraph &, const CostMap &,
507                            std::vector<Node> &, Cost &total_cost) :
508            _total(total_cost) {}
509
510          void insert(Cost diff) const {
511            _total += diff;
512          }
513
514        private:
515          Cost &_total;
516      };
517
518  };
519
520}; // namespace lemon
521
522#endif
Note: See TracBrowser for help on using the repository browser.