COIN-OR::LEMON - Graph Library

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