COIN-OR::LEMON - Graph Library

source: lemon/lemon/opt2_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: 10.2 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_OPT2_TSP_H
20#define LEMON_OPT2_TSP_H
21
22/// \ingroup tsp
23/// \file
24/// \brief 2-opt algorithm for symmetric TSP
25
26#include <vector>
27#include <lemon/full_graph.h>
28
29namespace lemon {
30
31  /// \brief 2-opt algorithm for symmetric TSP.
32  ///
33  /// Opt2Tsp implements the 2-opt heuristic for solving
34  /// symmetric \ref tsp "TSP".
35  ///
36  /// This algorithm starts with an initial tour and iteratively improves it.
37  /// At each step, it removes two edges and the reconnects the created two
38  /// paths in the other way if the resulting tour is shorter.
39  /// The algorithm finishes when no such 2-opt move can be applied, and so
40  /// the tour is 2-optimal.
41  ///
42  /// If no starting tour is given to the \ref run() function, then the
43  /// algorithm uses the node sequence determined by the node IDs.
44  /// Oherwise, it starts with the given tour.
45  ///
46  /// This is a relatively slow but powerful method.
47  /// A typical usage of it is the improvement of a solution that is resulted
48  /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
49  ///
50  /// \tparam CM Type of the cost map.
51  template <typename CM>
52  class Opt2Tsp
53  {
54    public:
55
56      /// Type of the cost map
57      typedef CM CostMap;
58      /// Type of the edge costs
59      typedef typename CM::Value Cost;
60
61    private:
62
63      GRAPH_TYPEDEFS(FullGraph);
64
65      const FullGraph &_gr;
66      const CostMap &_cost;
67      Cost _sum;
68      std::vector<int> _plist;
69      std::vector<Node> _path;
70
71    public:
72
73      /// \brief Constructor
74      ///
75      /// Constructor.
76      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
77      /// \param cost The cost map.
78      Opt2Tsp(const FullGraph &gr, const CostMap &cost)
79        : _gr(gr), _cost(cost) {}
80
81      /// \name Execution Control
82      /// @{
83
84      /// \brief Runs the algorithm from scratch.
85      ///
86      /// This function runs the algorithm starting from the tour that is
87      /// determined by the node ID sequence.
88      ///
89      /// \return The total cost of the found tour.
90      Cost run() {
91        _path.clear();
92
93        if (_gr.nodeNum() == 0) return _sum = 0;
94        else if (_gr.nodeNum() == 1) {
95          _path.push_back(_gr(0));
96          return _sum = 0;
97        }
98        else if (_gr.nodeNum() == 2) {
99          _path.push_back(_gr(0));
100          _path.push_back(_gr(1));
101          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
102        }
103
104        _plist.resize(2*_gr.nodeNum());
105        for (int i = 1; i < _gr.nodeNum()-1; ++i) {
106          _plist[2*i] = i-1;
107          _plist[2*i+1] = i+1;
108        }
109        _plist[0] = _gr.nodeNum()-1;
110        _plist[1] = 1;
111        _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
112        _plist[2*_gr.nodeNum()-1] = 0;
113
114        return start();
115      }
116
117      /// \brief Runs the algorithm from the given tour.
118      ///
119      /// This function runs the algorithm starting from the given tour.
120      ///
121      /// \param tour The tour as a path structure. It must be a
122      /// \ref checkPath() "valid path" containing excactly n arcs.
123      ///
124      /// \return The total cost of the found tour.
125      template <typename Path>
126      Cost run(const Path& tour) {
127        _path.clear();
128
129        if (_gr.nodeNum() == 0) return _sum = 0;
130        else if (_gr.nodeNum() == 1) {
131          _path.push_back(_gr(0));
132          return _sum = 0;
133        }
134        else if (_gr.nodeNum() == 2) {
135          _path.push_back(_gr(0));
136          _path.push_back(_gr(1));
137          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
138        }
139
140        _plist.resize(2*_gr.nodeNum());
141        typename Path::ArcIt it(tour);
142        int first = _gr.id(_gr.source(it)),
143            prev = first,
144            curr = _gr.id(_gr.target(it)),
145            next = -1;
146        _plist[2*first+1] = curr;
147        for (++it; it != INVALID; ++it) {
148          next = _gr.id(_gr.target(it));
149          _plist[2*curr] = prev;
150          _plist[2*curr+1] = next;
151          prev = curr;
152          curr = next;
153        }
154        _plist[2*first] = prev;
155
156        return start();
157      }
158
159      /// \brief Runs the algorithm from the given tour.
160      ///
161      /// This function runs the algorithm starting from the given tour.
162      ///
163      /// \param tour The tour as a node sequence. It must be a standard
164      /// sequence container storing all <tt>Node</tt>s in the desired order.
165      ///
166      /// \return The total cost of the found tour.
167      template <template <typename> class Container>
168      Cost run(const Container<Node>& tour) {
169        _path.clear();
170
171        if (_gr.nodeNum() == 0) return _sum = 0;
172        else if (_gr.nodeNum() == 1) {
173          _path.push_back(_gr(0));
174          return _sum = 0;
175        }
176        else if (_gr.nodeNum() == 2) {
177          _path.push_back(_gr(0));
178          _path.push_back(_gr(1));
179          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
180        }
181
182        _plist.resize(2*_gr.nodeNum());
183        typename Container<Node>::const_iterator it = tour.begin();
184        int first = _gr.id(*it),
185            prev = first,
186            curr = _gr.id(*(++it)),
187            next = -1;
188        _plist[2*first+1] = curr;
189        for (++it; it != tour.end(); ++it) {
190          next = _gr.id(*it);
191          _plist[2*curr] = prev;
192          _plist[2*curr+1] = next;
193          prev = curr;
194          curr = next;
195        }
196        _plist[2*first] = curr;
197        _plist[2*curr] = prev;
198        _plist[2*curr+1] = first;
199
200        return start();
201      }
202
203      /// @}
204
205      /// \name Query Functions
206      /// @{
207
208      /// \brief The total cost of the found tour.
209      ///
210      /// This function returns the total cost of the found tour.
211      ///
212      /// \pre run() must be called before using this function.
213      Cost tourCost() const {
214        return _sum;
215      }
216
217      /// \brief Returns a const reference to the node sequence of the
218      /// found tour.
219      ///
220      /// This function returns a const reference to the internal structure
221      /// that stores the node sequence of the found tour.
222      ///
223      /// \pre run() must be called before using this function.
224      const std::vector<Node>& tourNodes() const {
225        return _path;
226      }
227
228      /// \brief Gives back the node sequence of the found tour.
229      ///
230      /// This function copies the node sequence of the found tour into
231      /// the given standard container.
232      ///
233      /// \pre run() must be called before using this function.
234      template <typename Container>
235      void tourNodes(Container &container) const {
236        container.assign(_path.begin(), _path.end());
237      }
238
239      /// \brief Gives back the found tour as a path.
240      ///
241      /// This function copies the found tour as a list of arcs/edges into
242      /// the given \ref concept::Path "path structure".
243      ///
244      /// \pre run() must be called before using this function.
245      template <typename Path>
246      void tour(Path &path) const {
247        path.clear();
248        for (int i = 0; i < int(_path.size()) - 1; ++i) {
249          path.addBack(_gr.arc(_path[i], _path[i+1]));
250        }
251        if (int(_path.size()) >= 2) {
252          path.addBack(_gr.arc(_path.back(), _path.front()));
253        }
254      }
255
256      /// @}
257
258    private:
259
260      // Iterator class for the linked list storage of the tour
261      class PathListIt {
262        public:
263          PathListIt(const std::vector<int> &pl, int i=0)
264            : plist(&pl), act(i), last(pl[2*act]) {}
265          PathListIt(const std::vector<int> &pl, int i, int l)
266            : plist(&pl), act(i), last(l) {}
267
268          int nextIndex() const {
269            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
270          }
271
272          int prevIndex() const {
273            return (*plist)[2*act] == last ? 2*act : 2*act+1;
274          }
275
276          int next() const {
277            int x = (*plist)[2*act];
278            return x == last ? (*plist)[2*act+1] : x;
279          }
280
281          int prev() const {
282            return last;
283          }
284
285          PathListIt& operator++() {
286            int tmp = act;
287            act = next();
288            last = tmp;
289            return *this;
290          }
291
292          operator int() const {
293            return act;
294          }
295
296        private:
297          const std::vector<int> *plist;
298          int act;
299          int last;
300      };
301
302      // Checks and applies 2-opt move (if it improves the tour)
303      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
304        Node u  = _gr.nodeFromId(i),
305             un = _gr.nodeFromId(i.next()),
306             v  = _gr.nodeFromId(j),
307             vn = _gr.nodeFromId(j.next());
308
309        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
310            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
311        {
312          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
313          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
314
315          _plist[i.nextIndex()] = j;
316          _plist[j.nextIndex()] = i;
317
318          return true;
319        }
320
321        return false;
322     }
323
324      // Executes the algorithm from the initial tour
325      Cost start() {
326
327      restart_search:
328        for (PathListIt i(_plist); true; ++i) {
329          PathListIt j = i;
330          if (++j == 0 || ++j == 0) break;
331          for (; j != 0 && j != i.prev(); ++j) {
332            if (checkOpt2(i, j))
333              goto restart_search;
334          }
335        }
336
337        PathListIt i(_plist);
338        _path.push_back(_gr.nodeFromId(i));
339        for (++i; i != 0; ++i)
340          _path.push_back(_gr.nodeFromId(i));
341
342        _sum = _cost[_gr.edge(_path.back(), _path.front())];
343        for (int i = 0; i < int(_path.size())-1; ++i) {
344          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
345        }
346
347        return _sum;
348      }
349
350  };
351
352}; // namespace lemon
353
354#endif
Note: See TracBrowser for help on using the repository browser.