kpeter@1033
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@1033
|
2 |
*
|
kpeter@1033
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@1033
|
4 |
*
|
kpeter@1033
|
5 |
* Copyright (C) 2003-2010
|
kpeter@1033
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@1033
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@1033
|
8 |
*
|
kpeter@1033
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@1033
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@1033
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@1033
|
12 |
*
|
kpeter@1033
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@1033
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@1033
|
15 |
* purpose.
|
kpeter@1033
|
16 |
*
|
kpeter@1033
|
17 |
*/
|
kpeter@1033
|
18 |
|
f4c3@1031
|
19 |
#ifndef LEMON_INSERTION_TSP_H
|
f4c3@1031
|
20 |
#define LEMON_INSERTION_TSP_H
|
f4c3@1031
|
21 |
|
kpeter@1033
|
22 |
/// \ingroup tsp
|
kpeter@1033
|
23 |
/// \file
|
kpeter@1033
|
24 |
/// \brief Insertion algorithm for symmetric TSP
|
kpeter@1033
|
25 |
|
kpeter@1033
|
26 |
#include <vector>
|
f4c3@1031
|
27 |
#include <lemon/full_graph.h>
|
f4c3@1031
|
28 |
#include <lemon/maps.h>
|
f4c3@1031
|
29 |
#include <lemon/random.h>
|
f4c3@1031
|
30 |
|
f4c3@1031
|
31 |
namespace lemon {
|
f4c3@1031
|
32 |
|
kpeter@1034
|
33 |
/// \ingroup tsp
|
kpeter@1034
|
34 |
///
|
kpeter@1033
|
35 |
/// \brief Insertion algorithm for symmetric TSP.
|
kpeter@1033
|
36 |
///
|
kpeter@1033
|
37 |
/// InsertionTsp implements the insertion heuristic for solving
|
kpeter@1033
|
38 |
/// symmetric \ref tsp "TSP".
|
kpeter@1033
|
39 |
///
|
kpeter@1033
|
40 |
/// This is a basic TSP heuristic that has many variants.
|
kpeter@1033
|
41 |
/// It starts with a subtour containing a few nodes of the graph and it
|
kpeter@1033
|
42 |
/// iteratively inserts the other nodes into this subtour according to a
|
kpeter@1033
|
43 |
/// certain node selection rule.
|
kpeter@1033
|
44 |
///
|
kpeter@1033
|
45 |
/// This implementation provides four different node selection rules,
|
kpeter@1033
|
46 |
/// from which the most powerful one is used by default.
|
kpeter@1033
|
47 |
/// For more information, see \ref SelectionRule.
|
kpeter@1033
|
48 |
///
|
kpeter@1033
|
49 |
/// \tparam CM Type of the cost map.
|
kpeter@1033
|
50 |
template <typename CM>
|
kpeter@1033
|
51 |
class InsertionTsp
|
kpeter@1033
|
52 |
{
|
kpeter@1033
|
53 |
public:
|
f4c3@1031
|
54 |
|
kpeter@1033
|
55 |
/// Type of the cost map
|
f4c3@1031
|
56 |
typedef CM CostMap;
|
kpeter@1033
|
57 |
/// Type of the edge costs
|
f4c3@1031
|
58 |
typedef typename CM::Value Cost;
|
f4c3@1031
|
59 |
|
f4c3@1031
|
60 |
private:
|
f4c3@1031
|
61 |
|
kpeter@1033
|
62 |
GRAPH_TYPEDEFS(FullGraph);
|
kpeter@1033
|
63 |
|
kpeter@1033
|
64 |
const FullGraph &_gr;
|
kpeter@1033
|
65 |
const CostMap &_cost;
|
kpeter@1033
|
66 |
std::vector<Node> _notused;
|
kpeter@1033
|
67 |
std::vector<Node> _path;
|
kpeter@1033
|
68 |
Cost _sum;
|
kpeter@1033
|
69 |
|
kpeter@1033
|
70 |
public:
|
kpeter@1033
|
71 |
|
kpeter@1033
|
72 |
/// \brief Constants for specifying the node selection rule.
|
kpeter@1033
|
73 |
///
|
kpeter@1033
|
74 |
/// Enum type containing constants for specifying the node selection
|
kpeter@1033
|
75 |
/// rule for the \ref run() function.
|
kpeter@1033
|
76 |
///
|
kpeter@1033
|
77 |
/// During the algorithm, nodes are selected for addition to the current
|
kpeter@1033
|
78 |
/// subtour according to the applied rule.
|
kpeter@1034
|
79 |
/// In general, the FARTHEST method yields the best tours, thus it is the
|
kpeter@1034
|
80 |
/// default option. The RANDOM rule usually gives somewhat worse results,
|
kpeter@1034
|
81 |
/// but it is much faster than the others and it is the most robust.
|
kpeter@1033
|
82 |
///
|
kpeter@1033
|
83 |
/// The desired selection rule can be specified as a parameter of the
|
kpeter@1033
|
84 |
/// \ref run() function.
|
kpeter@1033
|
85 |
enum SelectionRule {
|
kpeter@1033
|
86 |
|
kpeter@1033
|
87 |
/// An unvisited node having minimum distance from the current
|
kpeter@1033
|
88 |
/// subtour is selected at each step.
|
kpeter@1033
|
89 |
/// The algorithm runs in O(n<sup>3</sup>) time using this
|
kpeter@1033
|
90 |
/// selection rule.
|
kpeter@1033
|
91 |
NEAREST,
|
kpeter@1033
|
92 |
|
kpeter@1033
|
93 |
/// An unvisited node having maximum distance from the current
|
kpeter@1033
|
94 |
/// subtour is selected at each step.
|
kpeter@1033
|
95 |
/// The algorithm runs in O(n<sup>3</sup>) time using this
|
kpeter@1033
|
96 |
/// selection rule.
|
kpeter@1033
|
97 |
FARTHEST,
|
kpeter@1033
|
98 |
|
kpeter@1033
|
99 |
/// An unvisited node whose insertion results in the least
|
kpeter@1033
|
100 |
/// increase of the subtour's total cost is selected at each step.
|
kpeter@1033
|
101 |
/// The algorithm runs in O(n<sup>3</sup>) time using this
|
kpeter@1033
|
102 |
/// selection rule.
|
kpeter@1033
|
103 |
CHEAPEST,
|
kpeter@1033
|
104 |
|
kpeter@1033
|
105 |
/// An unvisited node is selected randomly without any evaluation
|
kpeter@1033
|
106 |
/// at each step.
|
kpeter@1033
|
107 |
/// The global \ref rnd "random number generator instance" is used.
|
kpeter@1033
|
108 |
/// You can seed it before executing the algorithm, if you
|
kpeter@1033
|
109 |
/// would like to.
|
kpeter@1033
|
110 |
/// The algorithm runs in O(n<sup>2</sup>) time using this
|
kpeter@1033
|
111 |
/// selection rule.
|
kpeter@1033
|
112 |
RANDOM
|
kpeter@1033
|
113 |
};
|
kpeter@1033
|
114 |
|
kpeter@1033
|
115 |
public:
|
kpeter@1033
|
116 |
|
kpeter@1033
|
117 |
/// \brief Constructor
|
kpeter@1033
|
118 |
///
|
kpeter@1033
|
119 |
/// Constructor.
|
kpeter@1033
|
120 |
/// \param gr The \ref FullGraph "full graph" the algorithm runs on.
|
kpeter@1033
|
121 |
/// \param cost The cost map.
|
kpeter@1033
|
122 |
InsertionTsp(const FullGraph &gr, const CostMap &cost)
|
kpeter@1033
|
123 |
: _gr(gr), _cost(cost) {}
|
kpeter@1033
|
124 |
|
kpeter@1033
|
125 |
/// \name Execution Control
|
kpeter@1033
|
126 |
/// @{
|
kpeter@1033
|
127 |
|
kpeter@1033
|
128 |
/// \brief Runs the algorithm.
|
kpeter@1033
|
129 |
///
|
kpeter@1033
|
130 |
/// This function runs the algorithm.
|
kpeter@1033
|
131 |
///
|
kpeter@1033
|
132 |
/// \param rule The node selection rule. For more information, see
|
kpeter@1033
|
133 |
/// \ref SelectionRule.
|
kpeter@1033
|
134 |
///
|
kpeter@1033
|
135 |
/// \return The total cost of the found tour.
|
kpeter@1033
|
136 |
Cost run(SelectionRule rule = FARTHEST) {
|
kpeter@1033
|
137 |
_path.clear();
|
kpeter@1033
|
138 |
|
kpeter@1033
|
139 |
if (_gr.nodeNum() == 0) return _sum = 0;
|
kpeter@1033
|
140 |
else if (_gr.nodeNum() == 1) {
|
kpeter@1033
|
141 |
_path.push_back(_gr(0));
|
kpeter@1033
|
142 |
return _sum = 0;
|
kpeter@1033
|
143 |
}
|
kpeter@1033
|
144 |
|
kpeter@1033
|
145 |
switch (rule) {
|
kpeter@1033
|
146 |
case NEAREST:
|
kpeter@1033
|
147 |
init(true);
|
kpeter@1033
|
148 |
start<NearestSelection, DefaultInsertion>();
|
kpeter@1033
|
149 |
break;
|
kpeter@1033
|
150 |
case FARTHEST:
|
kpeter@1033
|
151 |
init(false);
|
kpeter@1033
|
152 |
start<FarthestSelection, DefaultInsertion>();
|
kpeter@1033
|
153 |
break;
|
kpeter@1033
|
154 |
case CHEAPEST:
|
kpeter@1033
|
155 |
init(true);
|
kpeter@1033
|
156 |
start<CheapestSelection, CheapestInsertion>();
|
kpeter@1033
|
157 |
break;
|
kpeter@1033
|
158 |
case RANDOM:
|
kpeter@1033
|
159 |
init(true);
|
kpeter@1033
|
160 |
start<RandomSelection, DefaultInsertion>();
|
kpeter@1033
|
161 |
break;
|
kpeter@1033
|
162 |
}
|
kpeter@1033
|
163 |
return _sum;
|
kpeter@1033
|
164 |
}
|
kpeter@1033
|
165 |
|
kpeter@1033
|
166 |
/// @}
|
kpeter@1033
|
167 |
|
kpeter@1033
|
168 |
/// \name Query Functions
|
kpeter@1033
|
169 |
/// @{
|
kpeter@1033
|
170 |
|
kpeter@1033
|
171 |
/// \brief The total cost of the found tour.
|
kpeter@1033
|
172 |
///
|
kpeter@1033
|
173 |
/// This function returns the total cost of the found tour.
|
kpeter@1033
|
174 |
///
|
kpeter@1033
|
175 |
/// \pre run() must be called before using this function.
|
kpeter@1033
|
176 |
Cost tourCost() const {
|
kpeter@1033
|
177 |
return _sum;
|
kpeter@1033
|
178 |
}
|
kpeter@1033
|
179 |
|
kpeter@1033
|
180 |
/// \brief Returns a const reference to the node sequence of the
|
kpeter@1033
|
181 |
/// found tour.
|
kpeter@1033
|
182 |
///
|
kpeter@1034
|
183 |
/// This function returns a const reference to a vector
|
kpeter@1033
|
184 |
/// that stores the node sequence of the found tour.
|
kpeter@1033
|
185 |
///
|
kpeter@1033
|
186 |
/// \pre run() must be called before using this function.
|
kpeter@1033
|
187 |
const std::vector<Node>& tourNodes() const {
|
kpeter@1033
|
188 |
return _path;
|
kpeter@1033
|
189 |
}
|
kpeter@1033
|
190 |
|
kpeter@1033
|
191 |
/// \brief Gives back the node sequence of the found tour.
|
kpeter@1033
|
192 |
///
|
kpeter@1033
|
193 |
/// This function copies the node sequence of the found tour into
|
kpeter@1033
|
194 |
/// the given standard container.
|
kpeter@1033
|
195 |
///
|
kpeter@1033
|
196 |
/// \pre run() must be called before using this function.
|
kpeter@1033
|
197 |
template <typename Container>
|
kpeter@1033
|
198 |
void tourNodes(Container &container) const {
|
kpeter@1033
|
199 |
container.assign(_path.begin(), _path.end());
|
kpeter@1033
|
200 |
}
|
kpeter@1033
|
201 |
|
kpeter@1033
|
202 |
/// \brief Gives back the found tour as a path.
|
kpeter@1033
|
203 |
///
|
kpeter@1033
|
204 |
/// This function copies the found tour as a list of arcs/edges into
|
kpeter@1033
|
205 |
/// the given \ref concept::Path "path structure".
|
kpeter@1033
|
206 |
///
|
kpeter@1033
|
207 |
/// \pre run() must be called before using this function.
|
kpeter@1033
|
208 |
template <typename Path>
|
kpeter@1033
|
209 |
void tour(Path &path) const {
|
kpeter@1033
|
210 |
path.clear();
|
kpeter@1033
|
211 |
for (int i = 0; i < int(_path.size()) - 1; ++i) {
|
kpeter@1033
|
212 |
path.addBack(_gr.arc(_path[i], _path[i+1]));
|
kpeter@1033
|
213 |
}
|
kpeter@1033
|
214 |
if (int(_path.size()) >= 2) {
|
kpeter@1033
|
215 |
path.addBack(_gr.arc(_path.back(), _path.front()));
|
kpeter@1033
|
216 |
}
|
kpeter@1033
|
217 |
}
|
kpeter@1033
|
218 |
|
kpeter@1033
|
219 |
/// @}
|
kpeter@1033
|
220 |
|
kpeter@1033
|
221 |
private:
|
kpeter@1033
|
222 |
|
kpeter@1033
|
223 |
// Initializes the algorithm
|
kpeter@1033
|
224 |
void init(bool min) {
|
kpeter@1033
|
225 |
Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
|
kpeter@1033
|
226 |
|
kpeter@1033
|
227 |
_path.clear();
|
kpeter@1033
|
228 |
_path.push_back(_gr.u(min_edge));
|
kpeter@1033
|
229 |
_path.push_back(_gr.v(min_edge));
|
kpeter@1033
|
230 |
|
kpeter@1033
|
231 |
_notused.clear();
|
kpeter@1033
|
232 |
for (NodeIt n(_gr); n!=INVALID; ++n) {
|
kpeter@1033
|
233 |
if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
|
kpeter@1033
|
234 |
_notused.push_back(n);
|
kpeter@1033
|
235 |
}
|
kpeter@1033
|
236 |
}
|
kpeter@1033
|
237 |
|
kpeter@1033
|
238 |
_sum = _cost[min_edge] * 2;
|
kpeter@1033
|
239 |
}
|
kpeter@1033
|
240 |
|
kpeter@1033
|
241 |
// Executes the algorithm
|
kpeter@1033
|
242 |
template <class SelectionFunctor, class InsertionFunctor>
|
kpeter@1033
|
243 |
void start() {
|
kpeter@1033
|
244 |
SelectionFunctor selectNode(_gr, _cost, _path, _notused);
|
kpeter@1033
|
245 |
InsertionFunctor insertNode(_gr, _cost, _path, _sum);
|
kpeter@1033
|
246 |
|
kpeter@1033
|
247 |
for (int i=0; i<_gr.nodeNum()-2; ++i) {
|
kpeter@1033
|
248 |
insertNode.insert(selectNode.select());
|
kpeter@1033
|
249 |
}
|
kpeter@1033
|
250 |
|
kpeter@1033
|
251 |
_sum = _cost[_gr.edge(_path.back(), _path.front())];
|
kpeter@1033
|
252 |
for (int i = 0; i < int(_path.size())-1; ++i) {
|
kpeter@1033
|
253 |
_sum += _cost[_gr.edge(_path[i], _path[i+1])];
|
kpeter@1033
|
254 |
}
|
kpeter@1033
|
255 |
}
|
kpeter@1033
|
256 |
|
kpeter@1033
|
257 |
|
kpeter@1033
|
258 |
// Implementation of the nearest selection rule
|
kpeter@1033
|
259 |
class NearestSelection {
|
f4c3@1031
|
260 |
public:
|
kpeter@1033
|
261 |
NearestSelection(const FullGraph &gr, const CostMap &cost,
|
kpeter@1033
|
262 |
std::vector<Node> &path, std::vector<Node> ¬used)
|
kpeter@1033
|
263 |
: _gr(gr), _cost(cost), _path(path), _notused(notused) {}
|
f4c3@1031
|
264 |
|
kpeter@1033
|
265 |
Node select() const {
|
kpeter@1033
|
266 |
Cost insert_val = 0;
|
kpeter@1033
|
267 |
int insert_node = -1;
|
kpeter@1033
|
268 |
|
kpeter@1033
|
269 |
for (unsigned int i=0; i<_notused.size(); ++i) {
|
kpeter@1033
|
270 |
Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
|
kpeter@1033
|
271 |
int min_node = 0;
|
kpeter@1033
|
272 |
|
kpeter@1033
|
273 |
for (unsigned int j=1; j<_path.size(); ++j) {
|
kpeter@1033
|
274 |
Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
|
kpeter@1033
|
275 |
if (min_val > curr) {
|
kpeter@1033
|
276 |
min_val = curr;
|
kpeter@1033
|
277 |
min_node = j;
|
kpeter@1033
|
278 |
}
|
kpeter@1033
|
279 |
}
|
kpeter@1033
|
280 |
|
kpeter@1033
|
281 |
if (insert_val > min_val || insert_node == -1) {
|
kpeter@1033
|
282 |
insert_val = min_val;
|
kpeter@1033
|
283 |
insert_node = i;
|
f4c3@1031
|
284 |
}
|
f4c3@1031
|
285 |
}
|
kpeter@1033
|
286 |
|
kpeter@1033
|
287 |
Node n = _notused[insert_node];
|
kpeter@1033
|
288 |
_notused.erase(_notused.begin()+insert_node);
|
kpeter@1033
|
289 |
|
kpeter@1033
|
290 |
return n;
|
f4c3@1031
|
291 |
}
|
f4c3@1031
|
292 |
|
f4c3@1031
|
293 |
private:
|
f4c3@1031
|
294 |
const FullGraph &_gr;
|
f4c3@1031
|
295 |
const CostMap &_cost;
|
kpeter@1033
|
296 |
std::vector<Node> &_path;
|
f4c3@1031
|
297 |
std::vector<Node> &_notused;
|
f4c3@1031
|
298 |
};
|
f4c3@1031
|
299 |
|
kpeter@1033
|
300 |
|
kpeter@1033
|
301 |
// Implementation of the farthest selection rule
|
f4c3@1031
|
302 |
class FarthestSelection {
|
f4c3@1031
|
303 |
public:
|
f4c3@1031
|
304 |
FarthestSelection(const FullGraph &gr, const CostMap &cost,
|
kpeter@1033
|
305 |
std::vector<Node> &path, std::vector<Node> ¬used)
|
kpeter@1033
|
306 |
: _gr(gr), _cost(cost), _path(path), _notused(notused) {}
|
kpeter@1033
|
307 |
|
f4c3@1031
|
308 |
Node select() const {
|
kpeter@1033
|
309 |
Cost insert_val = 0;
|
kpeter@1033
|
310 |
int insert_node = -1;
|
f4c3@1031
|
311 |
|
f4c3@1031
|
312 |
for (unsigned int i=0; i<_notused.size(); ++i) {
|
kpeter@1033
|
313 |
Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
|
f4c3@1031
|
314 |
int min_node = 0;
|
kpeter@1033
|
315 |
|
kpeter@1033
|
316 |
for (unsigned int j=1; j<_path.size(); ++j) {
|
kpeter@1033
|
317 |
Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
|
kpeter@1033
|
318 |
if (min_val > curr) {
|
kpeter@1033
|
319 |
min_val = curr;
|
f4c3@1031
|
320 |
min_node = j;
|
f4c3@1031
|
321 |
}
|
f4c3@1031
|
322 |
}
|
kpeter@1033
|
323 |
|
f4c3@1031
|
324 |
if (insert_val < min_val || insert_node == -1) {
|
f4c3@1031
|
325 |
insert_val = min_val;
|
f4c3@1031
|
326 |
insert_node = i;
|
f4c3@1031
|
327 |
}
|
f4c3@1031
|
328 |
}
|
kpeter@1033
|
329 |
|
f4c3@1031
|
330 |
Node n = _notused[insert_node];
|
f4c3@1031
|
331 |
_notused.erase(_notused.begin()+insert_node);
|
kpeter@1033
|
332 |
|
f4c3@1031
|
333 |
return n;
|
f4c3@1031
|
334 |
}
|
kpeter@1033
|
335 |
|
f4c3@1031
|
336 |
private:
|
f4c3@1031
|
337 |
const FullGraph &_gr;
|
f4c3@1031
|
338 |
const CostMap &_cost;
|
kpeter@1033
|
339 |
std::vector<Node> &_path;
|
f4c3@1031
|
340 |
std::vector<Node> &_notused;
|
f4c3@1031
|
341 |
};
|
f4c3@1031
|
342 |
|
f4c3@1031
|
343 |
|
kpeter@1033
|
344 |
// Implementation of the cheapest selection rule
|
f4c3@1031
|
345 |
class CheapestSelection {
|
f4c3@1031
|
346 |
private:
|
f4c3@1031
|
347 |
Cost costDiff(Node u, Node v, Node w) const {
|
kpeter@1033
|
348 |
return
|
f4c3@1031
|
349 |
_cost[_gr.edge(u, w)] +
|
f4c3@1031
|
350 |
_cost[_gr.edge(v, w)] -
|
f4c3@1031
|
351 |
_cost[_gr.edge(u, v)];
|
f4c3@1031
|
352 |
}
|
f4c3@1031
|
353 |
|
f4c3@1031
|
354 |
public:
|
f4c3@1031
|
355 |
CheapestSelection(const FullGraph &gr, const CostMap &cost,
|
kpeter@1033
|
356 |
std::vector<Node> &path, std::vector<Node> ¬used)
|
kpeter@1033
|
357 |
: _gr(gr), _cost(cost), _path(path), _notused(notused) {}
|
kpeter@1033
|
358 |
|
f4c3@1031
|
359 |
Cost select() const {
|
f4c3@1031
|
360 |
int insert_notused = -1;
|
f4c3@1031
|
361 |
int best_insert_index = -1;
|
kpeter@1033
|
362 |
Cost insert_val = 0;
|
kpeter@1033
|
363 |
|
f4c3@1031
|
364 |
for (unsigned int i=0; i<_notused.size(); ++i) {
|
f4c3@1031
|
365 |
int min = i;
|
f4c3@1031
|
366 |
int best_insert_tmp = 0;
|
f4c3@1031
|
367 |
Cost min_val =
|
kpeter@1033
|
368 |
costDiff(_path.front(), _path.back(), _notused[i]);
|
kpeter@1033
|
369 |
|
kpeter@1033
|
370 |
for (unsigned int j=1; j<_path.size(); ++j) {
|
f4c3@1031
|
371 |
Cost tmp =
|
kpeter@1033
|
372 |
costDiff(_path[j-1], _path[j], _notused[i]);
|
f4c3@1031
|
373 |
|
f4c3@1031
|
374 |
if (min_val > tmp) {
|
f4c3@1031
|
375 |
min = i;
|
f4c3@1031
|
376 |
min_val = tmp;
|
f4c3@1031
|
377 |
best_insert_tmp = j;
|
f4c3@1031
|
378 |
}
|
f4c3@1031
|
379 |
}
|
f4c3@1031
|
380 |
|
kpeter@1033
|
381 |
if (insert_val > min_val || insert_notused == -1) {
|
f4c3@1031
|
382 |
insert_notused = min;
|
f4c3@1031
|
383 |
insert_val = min_val;
|
f4c3@1031
|
384 |
best_insert_index = best_insert_tmp;
|
f4c3@1031
|
385 |
}
|
f4c3@1031
|
386 |
}
|
f4c3@1031
|
387 |
|
kpeter@1033
|
388 |
_path.insert(_path.begin()+best_insert_index,
|
kpeter@1033
|
389 |
_notused[insert_notused]);
|
f4c3@1031
|
390 |
_notused.erase(_notused.begin()+insert_notused);
|
f4c3@1031
|
391 |
|
f4c3@1031
|
392 |
return insert_val;
|
f4c3@1031
|
393 |
}
|
kpeter@1033
|
394 |
|
f4c3@1031
|
395 |
private:
|
f4c3@1031
|
396 |
const FullGraph &_gr;
|
f4c3@1031
|
397 |
const CostMap &_cost;
|
kpeter@1033
|
398 |
std::vector<Node> &_path;
|
f4c3@1031
|
399 |
std::vector<Node> &_notused;
|
f4c3@1031
|
400 |
};
|
f4c3@1031
|
401 |
|
kpeter@1033
|
402 |
// Implementation of the random selection rule
|
f4c3@1031
|
403 |
class RandomSelection {
|
f4c3@1031
|
404 |
public:
|
f4c3@1031
|
405 |
RandomSelection(const FullGraph &, const CostMap &,
|
kpeter@1033
|
406 |
std::vector<Node> &, std::vector<Node> ¬used)
|
kpeter@1033
|
407 |
: _notused(notused) {}
|
kpeter@1033
|
408 |
|
f4c3@1031
|
409 |
Node select() const {
|
f4c3@1031
|
410 |
const int index = rnd[_notused.size()];
|
f4c3@1031
|
411 |
Node n = _notused[index];
|
f4c3@1031
|
412 |
_notused.erase(_notused.begin()+index);
|
f4c3@1031
|
413 |
return n;
|
f4c3@1031
|
414 |
}
|
f4c3@1031
|
415 |
private:
|
f4c3@1031
|
416 |
std::vector<Node> &_notused;
|
f4c3@1031
|
417 |
};
|
f4c3@1031
|
418 |
|
f4c3@1031
|
419 |
|
kpeter@1033
|
420 |
// Implementation of the default insertion method
|
kpeter@1033
|
421 |
class DefaultInsertion {
|
f4c3@1031
|
422 |
private:
|
f4c3@1031
|
423 |
Cost costDiff(Node u, Node v, Node w) const {
|
kpeter@1033
|
424 |
return
|
f4c3@1031
|
425 |
_cost[_gr.edge(u, w)] +
|
f4c3@1031
|
426 |
_cost[_gr.edge(v, w)] -
|
f4c3@1031
|
427 |
_cost[_gr.edge(u, v)];
|
f4c3@1031
|
428 |
}
|
kpeter@1033
|
429 |
|
f4c3@1031
|
430 |
public:
|
kpeter@1033
|
431 |
DefaultInsertion(const FullGraph &gr, const CostMap &cost,
|
kpeter@1033
|
432 |
std::vector<Node> &path, Cost &total_cost) :
|
kpeter@1033
|
433 |
_gr(gr), _cost(cost), _path(path), _total(total_cost) {}
|
kpeter@1033
|
434 |
|
f4c3@1031
|
435 |
void insert(Node n) const {
|
f4c3@1031
|
436 |
int min = 0;
|
f4c3@1031
|
437 |
Cost min_val =
|
f4c3@1031
|
438 |
costDiff(_path.front(), _path.back(), n);
|
kpeter@1033
|
439 |
|
f4c3@1031
|
440 |
for (unsigned int i=1; i<_path.size(); ++i) {
|
f4c3@1031
|
441 |
Cost tmp = costDiff(_path[i-1], _path[i], n);
|
f4c3@1031
|
442 |
if (tmp < min_val) {
|
f4c3@1031
|
443 |
min = i;
|
f4c3@1031
|
444 |
min_val = tmp;
|
f4c3@1031
|
445 |
}
|
f4c3@1031
|
446 |
}
|
kpeter@1033
|
447 |
|
f4c3@1031
|
448 |
_path.insert(_path.begin()+min, n);
|
kpeter@1033
|
449 |
_total += min_val;
|
f4c3@1031
|
450 |
}
|
kpeter@1033
|
451 |
|
f4c3@1031
|
452 |
private:
|
f4c3@1031
|
453 |
const FullGraph &_gr;
|
f4c3@1031
|
454 |
const CostMap &_cost;
|
f4c3@1031
|
455 |
std::vector<Node> &_path;
|
kpeter@1033
|
456 |
Cost &_total;
|
f4c3@1031
|
457 |
};
|
kpeter@1033
|
458 |
|
kpeter@1033
|
459 |
// Implementation of a special insertion method for the cheapest
|
kpeter@1033
|
460 |
// selection rule
|
kpeter@1033
|
461 |
class CheapestInsertion {
|
f4c3@1031
|
462 |
TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
|
f4c3@1031
|
463 |
public:
|
kpeter@1033
|
464 |
CheapestInsertion(const FullGraph &, const CostMap &,
|
kpeter@1033
|
465 |
std::vector<Node> &, Cost &total_cost) :
|
kpeter@1033
|
466 |
_total(total_cost) {}
|
kpeter@1033
|
467 |
|
f4c3@1031
|
468 |
void insert(Cost diff) const {
|
kpeter@1033
|
469 |
_total += diff;
|
f4c3@1031
|
470 |
}
|
f4c3@1031
|
471 |
|
f4c3@1031
|
472 |
private:
|
kpeter@1033
|
473 |
Cost &_total;
|
kpeter@1033
|
474 |
};
|
kpeter@1033
|
475 |
|
f4c3@1031
|
476 |
};
|
kpeter@1033
|
477 |
|
f4c3@1031
|
478 |
}; // namespace lemon
|
f4c3@1031
|
479 |
|
f4c3@1031
|
480 |
#endif
|