|
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 |
1 #ifndef LEMON_OPT2_TSP_H |
19 #ifndef LEMON_OPT2_TSP_H |
2 #define LEMON_OPT2_TSP_H |
20 #define LEMON_OPT2_TSP_H |
3 |
21 |
|
22 /// \ingroup tsp |
|
23 /// \file |
|
24 /// \brief 2-opt algorithm for symmetric TSP |
|
25 |
4 #include <vector> |
26 #include <vector> |
5 #include <lemon/full_graph.h> |
27 #include <lemon/full_graph.h> |
6 #include <lemon/path.h> |
|
7 |
28 |
8 namespace lemon { |
29 namespace lemon { |
9 |
30 |
10 namespace opt2_helper { |
31 /// \brief 2-opt algorithm for symmetric TSP. |
11 template <class L> |
32 /// |
12 L vectorConvert(const std::vector<FullGraph::Node> &_path) { |
33 /// Opt2Tsp implements the 2-opt heuristic for solving |
13 return L(_path.begin(), _path.end()); |
34 /// symmetric \ref tsp "TSP". |
14 } |
35 /// |
15 |
36 /// This algorithm starts with an initial tour and iteratively improves it. |
16 template <> |
37 /// At each step, it removes two edges and the reconnects the created two |
17 std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) { |
38 /// paths in the other way if the resulting tour is shorter. |
18 return _path; |
39 /// The algorithm finishes when no such 2-opt move can be applied, and so |
19 } |
40 /// the tour is 2-optimal. |
20 } |
41 /// |
21 |
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. |
22 template <typename CM> |
51 template <typename CM> |
23 class Opt2Tsp { |
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 |
24 private: |
61 private: |
|
62 |
25 GRAPH_TYPEDEFS(FullGraph); |
63 GRAPH_TYPEDEFS(FullGraph); |
26 |
64 |
|
65 const FullGraph &_gr; |
|
66 const CostMap &_cost; |
|
67 Cost _sum; |
|
68 std::vector<int> _plist; |
|
69 std::vector<Node> _path; |
|
70 |
27 public: |
71 public: |
28 typedef CM CostMap; |
72 |
29 typedef typename CM::Value Cost; |
73 /// \brief Constructor |
30 |
74 /// |
31 |
75 /// Constructor. |
32 Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost), |
76 /// \param gr The \ref FullGraph "full graph" the algorithm runs on. |
33 tmppath(_gr.nodeNum()*2) { |
77 /// \param cost The cost map. |
34 |
78 Opt2Tsp(const FullGraph &gr, const CostMap &cost) |
35 for (int i=1; i<_gr.nodeNum()-1; ++i) { |
79 : _gr(gr), _cost(cost) {} |
36 tmppath[2*i] = i-1; |
80 |
37 tmppath[2*i+1] = i+1; |
81 /// \name Execution Control |
38 } |
82 /// @{ |
39 tmppath[0] = _gr.nodeNum()-1; |
83 |
40 tmppath[1] = 1; |
84 /// \brief Runs the algorithm from scratch. |
41 tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2; |
85 /// |
42 tmppath[2*(_gr.nodeNum()-1)+1] = 0; |
86 /// This function runs the algorithm starting from the tour that is |
43 } |
87 /// determined by the node ID sequence. |
44 |
88 /// |
45 Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) : |
89 /// \return The total cost of the found tour. |
46 _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) { |
90 Cost run() { |
47 |
91 _path.clear(); |
48 for (unsigned int i=1; i<path.size()-1; ++i) { |
92 |
49 tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]); |
93 if (_gr.nodeNum() == 0) return _sum = 0; |
50 tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]); |
94 else if (_gr.nodeNum() == 1) { |
51 } |
95 _path.push_back(_gr(0)); |
52 |
96 return _sum = 0; |
53 tmppath[2*_gr.id(path[0])] = _gr.id(path.back()); |
97 } |
54 tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]); |
98 else if (_gr.nodeNum() == 2) { |
55 tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]); |
99 _path.push_back(_gr(0)); |
56 tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front()); |
100 _path.push_back(_gr(1)); |
57 } |
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 /// @} |
58 |
257 |
59 private: |
258 private: |
60 Cost c(int u, int v) { |
259 |
61 return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))]; |
260 // Iterator class for the linked list storage of the tour |
62 } |
261 class PathListIt { |
63 |
|
64 class It { |
|
65 public: |
262 public: |
66 It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {} |
263 PathListIt(const std::vector<int> &pl, int i=0) |
67 It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {} |
264 : plist(&pl), act(i), last(pl[2*act]) {} |
68 |
265 PathListIt(const std::vector<int> &pl, int i, int l) |
69 int next_index() const { |
266 : plist(&pl), act(i), last(l) {} |
70 return (tmppath[2*act]==last)? 2*act+1 : 2*act; |
267 |
71 } |
268 int nextIndex() const { |
72 |
269 return (*plist)[2*act] == last ? 2*act+1 : 2*act; |
73 int prev_index() const { |
270 } |
74 return (tmppath[2*act]==last)? 2*act : 2*act+1; |
271 |
75 } |
272 int prevIndex() const { |
76 |
273 return (*plist)[2*act] == last ? 2*act : 2*act+1; |
|
274 } |
|
275 |
77 int next() const { |
276 int next() const { |
78 return tmppath[next_index()]; |
277 int x = (*plist)[2*act]; |
|
278 return x == last ? (*plist)[2*act+1] : x; |
79 } |
279 } |
80 |
280 |
81 int prev() const { |
281 int prev() const { |
82 return tmppath[prev_index()]; |
282 return last; |
83 } |
283 } |
84 |
284 |
85 It& operator++() { |
285 PathListIt& operator++() { |
86 int tmp = act; |
286 int tmp = act; |
87 act = next(); |
287 act = next(); |
88 last = tmp; |
288 last = tmp; |
89 return *this; |
289 return *this; |
90 } |
290 } |
91 |
291 |
92 operator int() const { |
292 operator int() const { |
93 return act; |
293 return act; |
94 } |
294 } |
95 |
295 |
96 private: |
296 private: |
97 const std::vector<int> &tmppath; |
297 const std::vector<int> *plist; |
98 int act; |
298 int act; |
99 int last; |
299 int last; |
100 }; |
300 }; |
101 |
301 |
102 bool check(std::vector<int> &path, It i, It j) { |
302 // Checks and applies 2-opt move (if it improves the tour) |
103 if (c(i, i.next()) + c(j, j.next()) > |
303 bool checkOpt2(const PathListIt& i, const PathListIt& j) { |
104 c(i, j) + c(j.next(), i.next())) { |
304 Node u = _gr.nodeFromId(i), |
105 |
305 un = _gr.nodeFromId(i.next()), |
106 path[ It(path, i.next(), i).prev_index() ] = j.next(); |
306 v = _gr.nodeFromId(j), |
107 path[ It(path, j.next(), j).prev_index() ] = i.next(); |
307 vn = _gr.nodeFromId(j.next()); |
108 |
308 |
109 path[i.next_index()] = j; |
309 if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] > |
110 path[j.next_index()] = i; |
310 _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)]) |
111 |
311 { |
112 return true; |
312 _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next(); |
113 } |
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 |
114 return false; |
321 return false; |
115 } |
322 } |
116 |
323 |
117 public: |
324 // Executes the algorithm from the initial tour |
118 |
325 Cost start() { |
119 Cost run() { |
326 |
120 _path.clear(); |
327 restart_search: |
121 |
328 for (PathListIt i(_plist); true; ++i) { |
122 if (_gr.nodeNum()>3) { |
329 PathListIt j = i; |
123 |
330 if (++j == 0 || ++j == 0) break; |
124 opt2_tsp_label: |
331 for (; j != 0 && j != i.prev(); ++j) { |
125 It i(tmppath); |
332 if (checkOpt2(i, j)) |
126 It j(tmppath, i, i.prev()); |
333 goto restart_search; |
127 ++j; ++j; |
334 } |
128 for (; j.next()!=0; ++j) { |
335 } |
129 if (check(tmppath, i, j)) |
336 |
130 goto opt2_tsp_label; |
337 PathListIt i(_plist); |
131 } |
338 _path.push_back(_gr.nodeFromId(i)); |
132 |
339 for (++i; i != 0; ++i) |
133 for (++i; i.next()!=0; ++i) { |
340 _path.push_back(_gr.nodeFromId(i)); |
134 It j(tmppath, i, i.prev()); |
341 |
135 if (++j==0) |
342 _sum = _cost[_gr.edge(_path.back(), _path.front())]; |
136 break; |
343 for (int i = 0; i < int(_path.size())-1; ++i) { |
137 if (++j==0) |
344 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; |
138 break; |
345 } |
139 |
346 |
140 for (; j!=0; ++j) { |
|
141 if (check(tmppath, i, j)) |
|
142 goto opt2_tsp_label; |
|
143 } |
|
144 } |
|
145 } |
|
146 |
|
147 It k(tmppath); |
|
148 _path.push_back(_gr.nodeFromId(k)); |
|
149 for (++k; k!=0; ++k) |
|
150 _path.push_back(_gr.nodeFromId(k)); |
|
151 |
|
152 |
|
153 |
|
154 _sum = _cost[ _gr.edge(_path.back(), _path.front()) ]; |
|
155 for (unsigned int i=0; i<_path.size()-1; ++i) |
|
156 _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ]; |
|
157 return _sum; |
347 return _sum; |
158 } |
348 } |
159 |
349 |
160 |
|
161 template <typename L> |
|
162 void tourNodes(L &container) { |
|
163 container(opt2_helper::vectorConvert<L>(_path)); |
|
164 } |
|
165 |
|
166 template <template <typename> class L> |
|
167 L<Node> tourNodes() { |
|
168 return opt2_helper::vectorConvert<L<Node> >(_path); |
|
169 } |
|
170 |
|
171 const std::vector<Node>& tourNodes() { |
|
172 return _path; |
|
173 } |
|
174 |
|
175 Path<FullGraph> tour() { |
|
176 Path<FullGraph> p; |
|
177 if (_path.size()<2) |
|
178 return p; |
|
179 |
|
180 for (unsigned int i=0; i<_path.size()-1; ++i) { |
|
181 p.addBack(_gr.arc(_path[i], _path[i+1])); |
|
182 } |
|
183 p.addBack(_gr.arc(_path.back(), _path.front())); |
|
184 return p; |
|
185 } |
|
186 |
|
187 Cost tourCost() { |
|
188 return _sum; |
|
189 } |
|
190 |
|
191 |
|
192 private: |
|
193 const FullGraph &_gr; |
|
194 const CostMap &_cost; |
|
195 Cost _sum; |
|
196 std::vector<int> tmppath; |
|
197 std::vector<Node> _path; |
|
198 }; |
350 }; |
199 |
351 |
200 |
|
201 }; // namespace lemon |
352 }; // namespace lemon |
202 |
353 |
203 #endif |
354 #endif |