COIN-OR::LEMON - Graph Library

source: lemon/lemon/opt2_tsp.h @ 1337:4add05447ca0

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

Apply unify-sources.sh to the source tree

File size: 10.5 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_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      /// an STL container through the given output iterator. The
234      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
235      /// For example,
236      /// \code
237      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
238      /// tsp.tourNodes(nodes.begin());
239      /// \endcode
240      /// or
241      /// \code
242      /// std::list<FullGraph::Node> nodes;
243      /// tsp.tourNodes(std::back_inserter(nodes));
244      /// \endcode
245      ///
246      /// \pre run() must be called before using this function.
247      template <typename Iterator>
248      void tourNodes(Iterator out) const {
249        std::copy(_path.begin(), _path.end(), out);
250      }
251
252      /// \brief Gives back the found tour as a path.
253      ///
254      /// This function copies the found tour as a list of arcs/edges into
255      /// the given \ref lemon::concepts::Path "path structure".
256      ///
257      /// \pre run() must be called before using this function.
258      template <typename Path>
259      void tour(Path &path) const {
260        path.clear();
261        for (int i = 0; i < int(_path.size()) - 1; ++i) {
262          path.addBack(_gr.arc(_path[i], _path[i+1]));
263        }
264        if (int(_path.size()) >= 2) {
265          path.addBack(_gr.arc(_path.back(), _path.front()));
266        }
267      }
268
269      /// @}
270
271    private:
272
273      // Iterator class for the linked list storage of the tour
274      class PathListIt {
275        public:
276          PathListIt(const std::vector<int> &pl, int i=0)
277            : plist(&pl), act(i), last(pl[2*act]) {}
278          PathListIt(const std::vector<int> &pl, int i, int l)
279            : plist(&pl), act(i), last(l) {}
280
281          int nextIndex() const {
282            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
283          }
284
285          int prevIndex() const {
286            return (*plist)[2*act] == last ? 2*act : 2*act+1;
287          }
288
289          int next() const {
290            int x = (*plist)[2*act];
291            return x == last ? (*plist)[2*act+1] : x;
292          }
293
294          int prev() const {
295            return last;
296          }
297
298          PathListIt& operator++() {
299            int tmp = act;
300            act = next();
301            last = tmp;
302            return *this;
303          }
304
305          operator int() const {
306            return act;
307          }
308
309        private:
310          const std::vector<int> *plist;
311          int act;
312          int last;
313      };
314
315      // Checks and applies 2-opt move (if it improves the tour)
316      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
317        Node u  = _gr.nodeFromId(i),
318             un = _gr.nodeFromId(i.next()),
319             v  = _gr.nodeFromId(j),
320             vn = _gr.nodeFromId(j.next());
321
322        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
323            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
324        {
325          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
326          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
327
328          _plist[i.nextIndex()] = j;
329          _plist[j.nextIndex()] = i;
330
331          return true;
332        }
333
334        return false;
335     }
336
337      // Executes the algorithm from the initial tour
338      Cost start() {
339
340      restart_search:
341        for (PathListIt i(_plist); true; ++i) {
342          PathListIt j = i;
343          if (++j == 0 || ++j == 0) break;
344          for (; j != 0 && j != i.prev(); ++j) {
345            if (checkOpt2(i, j))
346              goto restart_search;
347          }
348        }
349
350        PathListIt i(_plist);
351        _path.push_back(_gr.nodeFromId(i));
352        for (++i; i != 0; ++i)
353          _path.push_back(_gr.nodeFromId(i));
354
355        _sum = _cost[_gr.edge(_path.back(), _path.front())];
356        for (int i = 0; i < int(_path.size())-1; ++i) {
357          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
358        }
359
360        return _sum;
361      }
362
363  };
364
365}; // namespace lemon
366
367#endif
Note: See TracBrowser for help on using the repository browser.