COIN-OR::LEMON - Graph Library

source: lemon/lemon/insertion_tsp.h @ 1270:dceba191c00d

Last change on this file since 1270:dceba191c00d was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 16.8 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-2013
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      /// an STL container through the given output iterator. The
207      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
208      /// For example,
209      /// \code
210      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
211      /// tsp.tourNodes(nodes.begin());
212      /// \endcode
213      /// or
214      /// \code
215      /// std::list<FullGraph::Node> nodes;
216      /// tsp.tourNodes(std::back_inserter(nodes));
217      /// \endcode
218      ///
219      /// \pre run() must be called before using this function.
220      template <typename Iterator>
221      void tourNodes(Iterator out) const {
222        std::copy(_tour.begin(), _tour.end(), out);
223      }
224
225      /// \brief Gives back the found tour as a path.
226      ///
227      /// This function copies the found tour as a list of arcs/edges into
228      /// the given \ref lemon::concepts::Path "path structure".
229      ///
230      /// \pre run() must be called before using this function.
231      template <typename Path>
232      void tour(Path &path) const {
233        path.clear();
234        for (int i = 0; i < int(_tour.size()) - 1; ++i) {
235          path.addBack(_gr.arc(_tour[i], _tour[i+1]));
236        }
237        if (int(_tour.size()) >= 2) {
238          path.addBack(_gr.arc(_tour.back(), _tour.front()));
239        }
240      }
241
242      /// @}
243
244    private:
245
246      // Initializes the algorithm
247      void init(bool min) {
248        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
249
250        _tour.clear();
251        _tour.push_back(_gr.u(min_edge));
252        _tour.push_back(_gr.v(min_edge));
253
254        _notused.clear();
255        for (NodeIt n(_gr); n!=INVALID; ++n) {
256          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
257            _notused.push_back(n);
258          }
259        }
260
261        _sum = _cost[min_edge] * 2;
262      }
263
264      // Executes the algorithm
265      template <class SelectionFunctor, class InsertionFunctor>
266      void start() {
267        SelectionFunctor selectNode(_gr, _cost, _tour, _notused);
268        InsertionFunctor insertNode(_gr, _cost, _tour, _sum);
269
270        for (int i=0; i<_gr.nodeNum()-2; ++i) {
271          insertNode.insert(selectNode.select());
272        }
273
274        _sum = _cost[_gr.edge(_tour.back(), _tour.front())];
275        for (int i = 0; i < int(_tour.size())-1; ++i) {
276          _sum += _cost[_gr.edge(_tour[i], _tour[i+1])];
277        }
278      }
279
280
281      // Implementation of the nearest and farthest selection rule
282      template <typename Comparator>
283      class ComparingSelection {
284        public:
285          ComparingSelection(const FullGraph &gr, const CostMap &cost,
286                  std::vector<Node> &tour, std::vector<Node> &notused)
287            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
288              _dist(gr, 0), _compare()
289          {
290            // Compute initial distances for the unused nodes
291            for (unsigned int i=0; i<_notused.size(); ++i) {
292              Node u = _notused[i];
293              Cost min_dist = _cost[_gr.edge(u, _tour[0])];
294              for (unsigned int j=1; j<_tour.size(); ++j) {
295                Cost curr = _cost[_gr.edge(u, _tour[j])];
296                if (curr < min_dist) {
297                  min_dist = curr;
298                }
299              }
300              _dist[u] = min_dist;
301            }
302          }
303
304          Node select() {
305
306            // Select an used node with minimum distance
307            Cost ins_dist = 0;
308            int ins_node = -1;
309            for (unsigned int i=0; i<_notused.size(); ++i) {
310              Cost curr = _dist[_notused[i]];
311              if (_compare(curr, ins_dist) || ins_node == -1) {
312                ins_dist = curr;
313                ins_node = i;
314              }
315            }
316
317            // Remove the selected node from the unused vector
318            Node sn = _notused[ins_node];
319            _notused[ins_node] = _notused.back();
320            _notused.pop_back();
321
322            // Update the distances of the remaining nodes
323            for (unsigned int i=0; i<_notused.size(); ++i) {
324              Node u = _notused[i];
325              Cost nc = _cost[_gr.edge(sn, u)];
326              if (nc < _dist[u]) {
327                _dist[u] = nc;
328              }
329            }
330
331            return sn;
332          }
333
334        private:
335          const FullGraph &_gr;
336          const CostMap &_cost;
337          std::vector<Node> &_tour;
338          std::vector<Node> &_notused;
339          FullGraph::NodeMap<Cost> _dist;
340          Comparator _compare;
341      };
342
343      // Implementation of the cheapest selection rule
344      class CheapestSelection {
345        private:
346          Cost costDiff(Node u, Node v, Node w) const {
347            return
348              _cost[_gr.edge(u, w)] +
349              _cost[_gr.edge(v, w)] -
350              _cost[_gr.edge(u, v)];
351          }
352
353        public:
354          CheapestSelection(const FullGraph &gr, const CostMap &cost,
355                            std::vector<Node> &tour, std::vector<Node> &notused)
356            : _gr(gr), _cost(cost), _tour(tour), _notused(notused),
357              _ins_cost(gr, 0), _ins_pos(gr, -1)
358          {
359            // Compute insertion cost and position for the unused nodes
360            for (unsigned int i=0; i<_notused.size(); ++i) {
361              Node u = _notused[i];
362              Cost min_cost = costDiff(_tour.back(), _tour.front(), u);
363              int min_pos = 0;
364              for (unsigned int j=1; j<_tour.size(); ++j) {
365                Cost curr_cost = costDiff(_tour[j-1], _tour[j], u);
366                if (curr_cost < min_cost) {
367                  min_cost = curr_cost;
368                  min_pos = j;
369                }
370              }
371              _ins_cost[u] = min_cost;
372              _ins_pos[u] = min_pos;
373            }
374          }
375
376          Cost select() {
377
378            // Select an used node with minimum insertion cost
379            Cost min_cost = 0;
380            int min_node = -1;
381            for (unsigned int i=0; i<_notused.size(); ++i) {
382              Cost curr_cost = _ins_cost[_notused[i]];
383              if (curr_cost < min_cost || min_node == -1) {
384                min_cost = curr_cost;
385                min_node = i;
386              }
387            }
388
389            // Remove the selected node from the unused vector
390            Node sn = _notused[min_node];
391            _notused[min_node] = _notused.back();
392            _notused.pop_back();
393
394            // Insert the selected node into the tour
395            const int ipos = _ins_pos[sn];
396            _tour.insert(_tour.begin() + ipos, sn);
397
398            // Update the insertion cost and position of the remaining nodes
399            for (unsigned int i=0; i<_notused.size(); ++i) {
400              Node u = _notused[i];
401              Cost curr_cost = _ins_cost[u];
402              int curr_pos = _ins_pos[u];
403
404              int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1;
405              int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1;
406              Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u);
407              Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u);
408
409              if (nc1 <= curr_cost || nc2 <= curr_cost) {
410                // A new position is better than the old one
411                if (nc1 <= nc2) {
412                  curr_cost = nc1;
413                  curr_pos = ipos;
414                } else {
415                  curr_cost = nc2;
416                  curr_pos = ipos_next;
417                }
418              }
419              else {
420                if (curr_pos == ipos) {
421                  // The minimum should be found again
422                  curr_cost = costDiff(_tour.back(), _tour.front(), u);
423                  curr_pos = 0;
424                  for (unsigned int j=1; j<_tour.size(); ++j) {
425                    Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u);
426                    if (tmp_cost < curr_cost) {
427                      curr_cost = tmp_cost;
428                      curr_pos = j;
429                    }
430                  }
431                }
432                else if (curr_pos > ipos) {
433                  ++curr_pos;
434                }
435              }
436
437              _ins_cost[u] = curr_cost;
438              _ins_pos[u] = curr_pos;
439            }
440
441            return min_cost;
442          }
443
444        private:
445          const FullGraph &_gr;
446          const CostMap &_cost;
447          std::vector<Node> &_tour;
448          std::vector<Node> &_notused;
449          FullGraph::NodeMap<Cost> _ins_cost;
450          FullGraph::NodeMap<int> _ins_pos;
451      };
452
453      // Implementation of the random selection rule
454      class RandomSelection {
455        public:
456          RandomSelection(const FullGraph &, const CostMap &,
457                          std::vector<Node> &, std::vector<Node> &notused)
458            : _notused(notused) {}
459
460          Node select() const {
461            const int index = rnd[_notused.size()];
462            Node n = _notused[index];
463            _notused[index] = _notused.back();
464            _notused.pop_back();
465            return n;
466          }
467
468        private:
469          std::vector<Node> &_notused;
470      };
471
472
473      // Implementation of the default insertion method
474      class DefaultInsertion {
475        private:
476          Cost costDiff(Node u, Node v, Node w) const {
477            return
478              _cost[_gr.edge(u, w)] +
479              _cost[_gr.edge(v, w)] -
480              _cost[_gr.edge(u, v)];
481          }
482
483        public:
484          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
485                           std::vector<Node> &tour, Cost &total_cost) :
486            _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {}
487
488          void insert(Node n) const {
489            int min = 0;
490            Cost min_val =
491              costDiff(_tour.front(), _tour.back(), n);
492
493            for (unsigned int i=1; i<_tour.size(); ++i) {
494              Cost tmp = costDiff(_tour[i-1], _tour[i], n);
495              if (tmp < min_val) {
496                min = i;
497                min_val = tmp;
498              }
499            }
500
501            _tour.insert(_tour.begin()+min, n);
502            _total += min_val;
503          }
504
505        private:
506          const FullGraph &_gr;
507          const CostMap &_cost;
508          std::vector<Node> &_tour;
509          Cost &_total;
510      };
511
512      // Implementation of a special insertion method for the cheapest
513      // selection rule
514      class CheapestInsertion {
515        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
516        public:
517          CheapestInsertion(const FullGraph &, const CostMap &,
518                            std::vector<Node> &, Cost &total_cost) :
519            _total(total_cost) {}
520
521          void insert(Cost diff) const {
522            _total += diff;
523          }
524
525        private:
526          Cost &_total;
527      };
528
529  };
530
531}; // namespace lemon
532
533#endif
Note: See TracBrowser for help on using the repository browser.