COIN-OR::LEMON - Graph Library

source: lemon/lemon/insertion_tsp.h @ 1202:ef200e268af2

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

Unifications and improvements in TSP algorithms (#386)

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  /// \ingroup tsp
34  ///
35  /// \brief Insertion algorithm for symmetric TSP.
36  ///
37  /// InsertionTsp implements the insertion heuristic for solving
38  /// symmetric \ref tsp "TSP".
39  ///
40  /// This is a basic TSP heuristic that has many variants.
41  /// It starts with a subtour containing a few nodes of the graph and it
42  /// iteratively inserts the other nodes into this subtour according to a
43  /// certain node selection rule.
44  ///
45  /// This implementation provides four different node selection rules,
46  /// from which the most powerful one is used by default.
47  /// For more information, see \ref SelectionRule.
48  ///
49  /// \tparam CM Type of the cost map.
50  template <typename CM>
51  class InsertionTsp
52  {
53    public:
54
55      /// Type of the cost map
56      typedef CM CostMap;
57      /// Type of the edge costs
58      typedef typename CM::Value Cost;
59
60    private:
61
62      GRAPH_TYPEDEFS(FullGraph);
63
64      const FullGraph &_gr;
65      const CostMap &_cost;
66      std::vector<Node> _notused;
67      std::vector<Node> _path;
68      Cost _sum;
69
70    public:
71
72      /// \brief Constants for specifying the node selection rule.
73      ///
74      /// Enum type containing constants for specifying the node selection
75      /// rule for the \ref run() function.
76      ///
77      /// During the algorithm, nodes are selected for addition to the current
78      /// 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.
82      ///
83      /// The desired selection rule can be specified as a parameter of the
84      /// \ref run() function.
85      enum SelectionRule {
86
87        /// An unvisited node having minimum distance from the current
88        /// subtour is selected at each step.
89        /// The algorithm runs in O(n<sup>3</sup>) time using this
90        /// selection rule.
91        NEAREST,
92
93        /// An unvisited node having maximum distance from the current
94        /// subtour is selected at each step.
95        /// The algorithm runs in O(n<sup>3</sup>) time using this
96        /// selection rule.
97        FARTHEST,
98
99        /// An unvisited node whose insertion results in the least
100        /// increase of the subtour's total cost is selected at each step.
101        /// The algorithm runs in O(n<sup>3</sup>) time using this
102        /// selection rule.
103        CHEAPEST,
104
105        /// An unvisited node is selected randomly without any evaluation
106        /// at each step.
107        /// The global \ref rnd "random number generator instance" is used.
108        /// You can seed it before executing the algorithm, if you
109        /// would like to.
110        /// The algorithm runs in O(n<sup>2</sup>) time using this
111        /// selection rule.
112        RANDOM
113      };
114
115    public:
116
117      /// \brief Constructor
118      ///
119      /// Constructor.
120      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
121      /// \param cost The cost map.
122      InsertionTsp(const FullGraph &gr, const CostMap &cost)
123        : _gr(gr), _cost(cost) {}
124
125      /// \name Execution Control
126      /// @{
127
128      /// \brief Runs the algorithm.
129      ///
130      /// This function runs the algorithm.
131      ///
132      /// \param rule The node selection rule. For more information, see
133      /// \ref SelectionRule.
134      ///
135      /// \return The total cost of the found tour.
136      Cost run(SelectionRule rule = FARTHEST) {
137        _path.clear();
138
139        if (_gr.nodeNum() == 0) return _sum = 0;
140        else if (_gr.nodeNum() == 1) {
141          _path.push_back(_gr(0));
142          return _sum = 0;
143        }
144
145        switch (rule) {
146          case NEAREST:
147            init(true);
148            start<NearestSelection, DefaultInsertion>();
149            break;
150          case FARTHEST:
151            init(false);
152            start<FarthestSelection, DefaultInsertion>();
153            break;
154          case CHEAPEST:
155            init(true);
156            start<CheapestSelection, CheapestInsertion>();
157            break;
158          case RANDOM:
159            init(true);
160            start<RandomSelection, DefaultInsertion>();
161            break;
162        }
163        return _sum;
164      }
165
166      /// @}
167
168      /// \name Query Functions
169      /// @{
170
171      /// \brief The total cost of the found tour.
172      ///
173      /// This function returns the total cost of the found tour.
174      ///
175      /// \pre run() must be called before using this function.
176      Cost tourCost() const {
177        return _sum;
178      }
179
180      /// \brief Returns a const reference to the node sequence of the
181      /// found tour.
182      ///
183      /// This function returns a const reference to a vector
184      /// that stores the node sequence of the found tour.
185      ///
186      /// \pre run() must be called before using this function.
187      const std::vector<Node>& tourNodes() const {
188        return _path;
189      }
190
191      /// \brief Gives back the node sequence of the found tour.
192      ///
193      /// This function copies the node sequence of the found tour into
194      /// the given standard container.
195      ///
196      /// \pre run() must be called before using this function.
197      template <typename Container>
198      void tourNodes(Container &container) const {
199        container.assign(_path.begin(), _path.end());
200      }
201
202      /// \brief Gives back the found tour as a path.
203      ///
204      /// This function copies the found tour as a list of arcs/edges into
205      /// the given \ref concept::Path "path structure".
206      ///
207      /// \pre run() must be called before using this function.
208      template <typename Path>
209      void tour(Path &path) const {
210        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()));
216        }
217      }
218
219      /// @}
220
221    private:
222
223      // Initializes the algorithm
224      void init(bool min) {
225        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
226
227        _path.clear();
228        _path.push_back(_gr.u(min_edge));
229        _path.push_back(_gr.v(min_edge));
230
231        _notused.clear();
232        for (NodeIt n(_gr); n!=INVALID; ++n) {
233          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
234            _notused.push_back(n);
235          }
236        }
237
238        _sum = _cost[min_edge] * 2;
239      }
240
241      // Executes the algorithm
242      template <class SelectionFunctor, class InsertionFunctor>
243      void start() {
244        SelectionFunctor selectNode(_gr, _cost, _path, _notused);
245        InsertionFunctor insertNode(_gr, _cost, _path, _sum);
246
247        for (int i=0; i<_gr.nodeNum()-2; ++i) {
248          insertNode.insert(selectNode.select());
249        }
250
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 {
260        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
269            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;
278                }
279              }
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;
291          }
292
293        private:
294          const FullGraph &_gr;
295          const CostMap &_cost;
296          std::vector<Node> &_path;
297          std::vector<Node> &_notused;
298      };
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
343
344      // Implementation of the cheapest selection rule
345      class CheapestSelection {
346        private:
347          Cost costDiff(Node u, Node v, Node w) const {
348            return
349              _cost[_gr.edge(u, w)] +
350              _cost[_gr.edge(v, w)] -
351              _cost[_gr.edge(u, v)];
352          }
353
354        public:
355          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
364            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;
378                }
379              }
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;
393          }
394
395        private:
396          const FullGraph &_gr;
397          const CostMap &_cost;
398          std::vector<Node> &_path;
399          std::vector<Node> &_notused;
400      };
401
402      // Implementation of the random selection rule
403      class RandomSelection {
404        public:
405          RandomSelection(const FullGraph &, const CostMap &,
406                          std::vector<Node> &, std::vector<Node> &notused)
407            : _notused(notused) {}
408
409          Node select() const {
410            const int index = rnd[_notused.size()];
411            Node n = _notused[index];
412            _notused.erase(_notused.begin()+index);
413            return n;
414          }
415        private:
416          std::vector<Node> &_notused;
417      };
418
419
420      // Implementation of the default insertion method
421      class DefaultInsertion {
422        private:
423          Cost costDiff(Node u, Node v, Node w) const {
424            return
425              _cost[_gr.edge(u, w)] +
426              _cost[_gr.edge(v, w)] -
427              _cost[_gr.edge(u, v)];
428          }
429
430        public:
431          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) {}
434
435          void insert(Node n) const {
436            int min = 0;
437            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);
442              if (tmp < min_val) {
443                min = i;
444                min_val = tmp;
445              }
446            }
447
448            _path.insert(_path.begin()+min, n);
449            _total += min_val;
450          }
451
452        private:
453          const FullGraph &_gr;
454          const CostMap &_cost;
455          std::vector<Node> &_path;
456          Cost &_total;
457      };
458
459      // Implementation of a special insertion method for the cheapest
460      // selection rule
461      class CheapestInsertion {
462        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
463        public:
464          CheapestInsertion(const FullGraph &, const CostMap &,
465                            std::vector<Node> &, Cost &total_cost) :
466            _total(total_cost) {}
467
468          void insert(Cost diff) const {
469            _total += diff;
470          }
471
472        private:
473          Cost &_total;
474      };
475
476  };
477
478}; // namespace lemon
479
480#endif
Note: See TracBrowser for help on using the repository browser.