COIN-OR::LEMON - Graph Library

source: lemon/lemon/insertion_tsp.h @ 1201:9a51db038228

Last change on this file since 1201:9a51db038228 was 1201:9a51db038228, checked in by Peter Kovacs <kpeter@…>, 9 years ago

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 size: 14.3 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 <lemon/full_graph.h>
28#include <lemon/maps.h>
29#include <lemon/random.h>
30
31namespace lemon {
32
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.
48  template <typename CM>
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
58    private:
59
60      GRAPH_TYPEDEFS(FullGraph);
61
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>();
147            break;
148          case FARTHEST:
149            init(false);
150            start<FarthestSelection, DefaultInsertion>();
151            break;
152          case CHEAPEST:
153            init(true);
154            start<CheapestSelection, CheapestInsertion>();
155            break;
156          case RANDOM:
157            init(true);
158            start<RandomSelection, DefaultInsertion>();
159            break;
160        }
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      /// @}
218
219    private:
220
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;
282              }
283            }
284
285            Node n = _notused[insert_node];
286            _notused.erase(_notused.begin()+insert_node);
287
288            return n;
289          }
290
291        private:
292          const FullGraph &_gr;
293          const CostMap &_cost;
294          std::vector<Node> &_path;
295          std::vector<Node> &_notused;
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
306          Node select() const {
307            Cost insert_val = 0;
308            int insert_node = -1;
309
310            for (unsigned int i=0; i<_notused.size(); ++i) {
311              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
312              int min_node = 0;
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;
318                  min_node = j;
319                }
320              }
321
322              if (insert_val < min_val || insert_node == -1) {
323                insert_val = min_val;
324                insert_node = i;
325              }
326            }
327
328            Node n = _notused[insert_node];
329            _notused.erase(_notused.begin()+insert_node);
330
331            return n;
332          }
333
334        private:
335          const FullGraph &_gr;
336          const CostMap &_cost;
337          std::vector<Node> &_path;
338          std::vector<Node> &_notused;
339      };
340
341
342      // Implementation of the cheapest selection rule
343      class CheapestSelection {
344        private:
345          Cost costDiff(Node u, Node v, Node w) const {
346            return
347              _cost[_gr.edge(u, w)] +
348              _cost[_gr.edge(v, w)] -
349              _cost[_gr.edge(u, v)];
350          }
351
352        public:
353          CheapestSelection(const FullGraph &gr, const CostMap &cost,
354                            std::vector<Node> &path, std::vector<Node> &notused)
355            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
356
357          Cost select() const {
358            int insert_notused = -1;
359            int best_insert_index = -1;
360            Cost insert_val = 0;
361
362            for (unsigned int i=0; i<_notused.size(); ++i) {
363              int min = i;
364              int best_insert_tmp = 0;
365              Cost min_val =
366                costDiff(_path.front(), _path.back(), _notused[i]);
367
368              for (unsigned int j=1; j<_path.size(); ++j) {
369                Cost tmp =
370                  costDiff(_path[j-1], _path[j], _notused[i]);
371
372                if (min_val > tmp) {
373                  min = i;
374                  min_val = tmp;
375                  best_insert_tmp = j;
376                }
377              }
378
379              if (insert_val > min_val || insert_notused == -1) {
380                insert_notused = min;
381                insert_val = min_val;
382                best_insert_index = best_insert_tmp;
383              }
384            }
385
386            _path.insert(_path.begin()+best_insert_index,
387                         _notused[insert_notused]);
388            _notused.erase(_notused.begin()+insert_notused);
389
390            return insert_val;
391          }
392
393        private:
394          const FullGraph &_gr;
395          const CostMap &_cost;
396          std::vector<Node> &_path;
397          std::vector<Node> &_notused;
398      };
399
400      // Implementation of the random selection rule
401      class RandomSelection {
402        public:
403          RandomSelection(const FullGraph &, const CostMap &,
404                          std::vector<Node> &, std::vector<Node> &notused)
405            : _notused(notused) {}
406
407          Node select() const {
408            const int index = rnd[_notused.size()];
409            Node n = _notused[index];
410            _notused.erase(_notused.begin()+index);
411            return n;
412          }
413        private:
414          std::vector<Node> &_notused;
415      };
416
417
418      // Implementation of the default insertion method
419      class DefaultInsertion {
420        private:
421          Cost costDiff(Node u, Node v, Node w) const {
422            return
423              _cost[_gr.edge(u, w)] +
424              _cost[_gr.edge(v, w)] -
425              _cost[_gr.edge(u, v)];
426          }
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
433          void insert(Node n) const {
434            int min = 0;
435            Cost min_val =
436              costDiff(_path.front(), _path.back(), n);
437
438            for (unsigned int i=1; i<_path.size(); ++i) {
439              Cost tmp = costDiff(_path[i-1], _path[i], n);
440              if (tmp < min_val) {
441                min = i;
442                min_val = tmp;
443              }
444            }
445
446            _path.insert(_path.begin()+min, n);
447            _total += min_val;
448          }
449
450        private:
451          const FullGraph &_gr;
452          const CostMap &_cost;
453          std::vector<Node> &_path;
454          Cost &_total;
455      };
456
457      // Implementation of a special insertion method for the cheapest
458      // selection rule
459      class CheapestInsertion {
460        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
461        public:
462          CheapestInsertion(const FullGraph &, const CostMap &,
463                            std::vector<Node> &, Cost &total_cost) :
464            _total(total_cost) {}
465
466          void insert(Cost diff) const {
467            _total += diff;
468          }
469
470        private:
471          Cost &_total;
472      };
473
474  };
475
476}; // namespace lemon
477
478#endif
Note: See TracBrowser for help on using the repository browser.