1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_OPT2_TSP_H
20 #define LEMON_OPT2_TSP_H
24 /// \brief 2-opt algorithm for symmetric TSP
27 #include <lemon/full_graph.h>
31 /// \brief 2-opt algorithm for symmetric TSP.
33 /// Opt2Tsp implements the 2-opt heuristic for solving
34 /// symmetric \ref tsp "TSP".
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.
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.
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).
50 /// \tparam CM Type of the cost map.
51 template <typename CM>
56 /// Type of the cost map
58 /// Type of the edge costs
59 typedef typename CM::Value Cost;
63 GRAPH_TYPEDEFS(FullGraph);
68 std::vector<int> _plist;
69 std::vector<Node> _path;
73 /// \brief 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) {}
81 /// \name Execution Control
84 /// \brief Runs the algorithm from scratch.
86 /// This function runs the algorithm starting from the tour that is
87 /// determined by the node ID sequence.
89 /// \return The total cost of the found tour.
93 if (_gr.nodeNum() == 0) return _sum = 0;
94 else if (_gr.nodeNum() == 1) {
95 _path.push_back(_gr(0));
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))];
104 _plist.resize(2*_gr.nodeNum());
105 for (int i = 1; i < _gr.nodeNum()-1; ++i) {
109 _plist[0] = _gr.nodeNum()-1;
111 _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
112 _plist[2*_gr.nodeNum()-1] = 0;
117 /// \brief Runs the algorithm from the given tour.
119 /// This function runs the algorithm starting from the given tour.
121 /// \param tour The tour as a path structure. It must be a
122 /// \ref checkPath() "valid path" containing excactly n arcs.
124 /// \return The total cost of the found tour.
125 template <typename Path>
126 Cost run(const Path& tour) {
129 if (_gr.nodeNum() == 0) return _sum = 0;
130 else if (_gr.nodeNum() == 1) {
131 _path.push_back(_gr(0));
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))];
140 _plist.resize(2*_gr.nodeNum());
141 typename Path::ArcIt it(tour);
142 int first = _gr.id(_gr.source(it)),
144 curr = _gr.id(_gr.target(it)),
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;
154 _plist[2*first] = prev;
159 /// \brief Runs the algorithm from the given tour.
161 /// This function runs the algorithm starting from the given tour.
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.
166 /// \return The total cost of the found tour.
167 template <template <typename> class Container>
168 Cost run(const Container<Node>& tour) {
171 if (_gr.nodeNum() == 0) return _sum = 0;
172 else if (_gr.nodeNum() == 1) {
173 _path.push_back(_gr(0));
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))];
182 _plist.resize(2*_gr.nodeNum());
183 typename Container<Node>::const_iterator it = tour.begin();
184 int first = _gr.id(*it),
186 curr = _gr.id(*(++it)),
188 _plist[2*first+1] = curr;
189 for (++it; it != tour.end(); ++it) {
191 _plist[2*curr] = prev;
192 _plist[2*curr+1] = next;
196 _plist[2*first] = curr;
197 _plist[2*curr] = prev;
198 _plist[2*curr+1] = first;
205 /// \name Query Functions
208 /// \brief The total cost of the found tour.
210 /// This function returns the total cost of the found tour.
212 /// \pre run() must be called before using this function.
213 Cost tourCost() const {
217 /// \brief Returns a const reference to the node sequence of the
220 /// This function returns a const reference to the internal structure
221 /// that stores the node sequence of the found tour.
223 /// \pre run() must be called before using this function.
224 const std::vector<Node>& tourNodes() const {
228 /// \brief Gives back the node sequence of the found tour.
230 /// This function copies the node sequence of the found tour into
231 /// the given standard container.
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());
239 /// \brief Gives back the found tour as a path.
241 /// This function copies the found tour as a list of arcs/edges into
242 /// the given \ref concept::Path "path structure".
244 /// \pre run() must be called before using this function.
245 template <typename Path>
246 void tour(Path &path) const {
248 for (int i = 0; i < int(_path.size()) - 1; ++i) {
249 path.addBack(_gr.arc(_path[i], _path[i+1]));
251 if (int(_path.size()) >= 2) {
252 path.addBack(_gr.arc(_path.back(), _path.front()));
260 // Iterator class for the linked list storage of the tour
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) {}
268 int nextIndex() const {
269 return (*plist)[2*act] == last ? 2*act+1 : 2*act;
272 int prevIndex() const {
273 return (*plist)[2*act] == last ? 2*act : 2*act+1;
277 int x = (*plist)[2*act];
278 return x == last ? (*plist)[2*act+1] : x;
285 PathListIt& operator++() {
292 operator int() const {
297 const std::vector<int> *plist;
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());
309 if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
310 _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
312 _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
313 _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
315 _plist[i.nextIndex()] = j;
316 _plist[j.nextIndex()] = i;
324 // Executes the algorithm from the initial tour
328 for (PathListIt i(_plist); true; ++i) {
330 if (++j == 0 || ++j == 0) break;
331 for (; j != 0 && j != i.prev(); ++j) {
337 PathListIt i(_plist);
338 _path.push_back(_gr.nodeFromId(i));
339 for (++i; i != 0; ++i)
340 _path.push_back(_gr.nodeFromId(i));
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])];
352 }; // namespace lemon