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_INSERTION_TSP_H
20 #define LEMON_INSERTION_TSP_H
24 /// \brief Insertion algorithm for symmetric TSP
27 #include <lemon/full_graph.h>
28 #include <lemon/maps.h>
29 #include <lemon/random.h>
35 /// \brief Insertion algorithm for symmetric TSP.
37 /// InsertionTsp implements the insertion heuristic for solving
38 /// symmetric \ref tsp "TSP".
40 /// This is a basic TSP heuristic that has many variants.
41 /// It starts with a subtour containing a few nodes of the graph and it
42 /// iteratively inserts the other nodes into this subtour according to a
43 /// certain node selection rule.
45 /// This implementation provides four different node selection rules,
46 /// from which the most powerful one is used by default.
47 /// For more information, see \ref SelectionRule.
49 /// \tparam CM Type of the cost map.
50 template <typename CM>
55 /// Type of the cost map
57 /// Type of the edge costs
58 typedef typename CM::Value Cost;
62 GRAPH_TYPEDEFS(FullGraph);
66 std::vector<Node> _notused;
67 std::vector<Node> _path;
72 /// \brief Constants for specifying the node selection rule.
74 /// Enum type containing constants for specifying the node selection
75 /// rule for the \ref run() function.
77 /// During the algorithm, nodes are selected for addition to the current
78 /// subtour according to the applied rule.
79 /// In general, the FARTHEST method yields the best tours, thus it is the
80 /// default option. The RANDOM rule usually gives somewhat worse results,
81 /// but it is much faster than the others and it is the most robust.
83 /// The desired selection rule can be specified as a parameter of the
84 /// \ref run() function.
87 /// An unvisited node having minimum distance from the current
88 /// subtour is selected at each step.
89 /// The algorithm runs in O(n<sup>3</sup>) time using this
93 /// An unvisited node having maximum distance from the current
94 /// subtour is selected at each step.
95 /// The algorithm runs in O(n<sup>3</sup>) time using this
99 /// An unvisited node whose insertion results in the least
100 /// increase of the subtour's total cost is selected at each step.
101 /// The algorithm runs in O(n<sup>3</sup>) time using this
105 /// An unvisited node is selected randomly without any evaluation
107 /// The global \ref rnd "random number generator instance" is used.
108 /// You can seed it before executing the algorithm, if you
110 /// The algorithm runs in O(n<sup>2</sup>) time using this
117 /// \brief Constructor
120 /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
121 /// \param cost The cost map.
122 InsertionTsp(const FullGraph &gr, const CostMap &cost)
123 : _gr(gr), _cost(cost) {}
125 /// \name Execution Control
128 /// \brief Runs the algorithm.
130 /// This function runs the algorithm.
132 /// \param rule The node selection rule. For more information, see
133 /// \ref SelectionRule.
135 /// \return The total cost of the found tour.
136 Cost run(SelectionRule rule = FARTHEST) {
139 if (_gr.nodeNum() == 0) return _sum = 0;
140 else if (_gr.nodeNum() == 1) {
141 _path.push_back(_gr(0));
148 start<NearestSelection, DefaultInsertion>();
152 start<FarthestSelection, DefaultInsertion>();
156 start<CheapestSelection, CheapestInsertion>();
160 start<RandomSelection, DefaultInsertion>();
168 /// \name Query Functions
171 /// \brief The total cost of the found tour.
173 /// This function returns the total cost of the found tour.
175 /// \pre run() must be called before using this function.
176 Cost tourCost() const {
180 /// \brief Returns a const reference to the node sequence of the
183 /// This function returns a const reference to a vector
184 /// that stores the node sequence of the found tour.
186 /// \pre run() must be called before using this function.
187 const std::vector<Node>& tourNodes() const {
191 /// \brief Gives back the node sequence of the found tour.
193 /// This function copies the node sequence of the found tour into
194 /// the given standard container.
196 /// \pre run() must be called before using this function.
197 template <typename Container>
198 void tourNodes(Container &container) const {
199 container.assign(_path.begin(), _path.end());
202 /// \brief Gives back the found tour as a path.
204 /// This function copies the found tour as a list of arcs/edges into
205 /// the given \ref concept::Path "path structure".
207 /// \pre run() must be called before using this function.
208 template <typename Path>
209 void tour(Path &path) const {
211 for (int i = 0; i < int(_path.size()) - 1; ++i) {
212 path.addBack(_gr.arc(_path[i], _path[i+1]));
214 if (int(_path.size()) >= 2) {
215 path.addBack(_gr.arc(_path.back(), _path.front()));
223 // Initializes the algorithm
224 void init(bool min) {
225 Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
228 _path.push_back(_gr.u(min_edge));
229 _path.push_back(_gr.v(min_edge));
232 for (NodeIt n(_gr); n!=INVALID; ++n) {
233 if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
234 _notused.push_back(n);
238 _sum = _cost[min_edge] * 2;
241 // Executes the algorithm
242 template <class SelectionFunctor, class InsertionFunctor>
244 SelectionFunctor selectNode(_gr, _cost, _path, _notused);
245 InsertionFunctor insertNode(_gr, _cost, _path, _sum);
247 for (int i=0; i<_gr.nodeNum()-2; ++i) {
248 insertNode.insert(selectNode.select());
251 _sum = _cost[_gr.edge(_path.back(), _path.front())];
252 for (int i = 0; i < int(_path.size())-1; ++i) {
253 _sum += _cost[_gr.edge(_path[i], _path[i+1])];
258 // Implementation of the nearest selection rule
259 class NearestSelection {
261 NearestSelection(const FullGraph &gr, const CostMap &cost,
262 std::vector<Node> &path, std::vector<Node> ¬used)
263 : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
265 Node select() const {
267 int insert_node = -1;
269 for (unsigned int i=0; i<_notused.size(); ++i) {
270 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
273 for (unsigned int j=1; j<_path.size(); ++j) {
274 Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
275 if (min_val > curr) {
281 if (insert_val > min_val || insert_node == -1) {
282 insert_val = min_val;
287 Node n = _notused[insert_node];
288 _notused.erase(_notused.begin()+insert_node);
294 const FullGraph &_gr;
295 const CostMap &_cost;
296 std::vector<Node> &_path;
297 std::vector<Node> &_notused;
301 // Implementation of the farthest selection rule
302 class FarthestSelection {
304 FarthestSelection(const FullGraph &gr, const CostMap &cost,
305 std::vector<Node> &path, std::vector<Node> ¬used)
306 : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
308 Node select() const {
310 int insert_node = -1;
312 for (unsigned int i=0; i<_notused.size(); ++i) {
313 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
316 for (unsigned int j=1; j<_path.size(); ++j) {
317 Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
318 if (min_val > curr) {
324 if (insert_val < min_val || insert_node == -1) {
325 insert_val = min_val;
330 Node n = _notused[insert_node];
331 _notused.erase(_notused.begin()+insert_node);
337 const FullGraph &_gr;
338 const CostMap &_cost;
339 std::vector<Node> &_path;
340 std::vector<Node> &_notused;
344 // Implementation of the cheapest selection rule
345 class CheapestSelection {
347 Cost costDiff(Node u, Node v, Node w) const {
349 _cost[_gr.edge(u, w)] +
350 _cost[_gr.edge(v, w)] -
351 _cost[_gr.edge(u, v)];
355 CheapestSelection(const FullGraph &gr, const CostMap &cost,
356 std::vector<Node> &path, std::vector<Node> ¬used)
357 : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
359 Cost select() const {
360 int insert_notused = -1;
361 int best_insert_index = -1;
364 for (unsigned int i=0; i<_notused.size(); ++i) {
366 int best_insert_tmp = 0;
368 costDiff(_path.front(), _path.back(), _notused[i]);
370 for (unsigned int j=1; j<_path.size(); ++j) {
372 costDiff(_path[j-1], _path[j], _notused[i]);
381 if (insert_val > min_val || insert_notused == -1) {
382 insert_notused = min;
383 insert_val = min_val;
384 best_insert_index = best_insert_tmp;
388 _path.insert(_path.begin()+best_insert_index,
389 _notused[insert_notused]);
390 _notused.erase(_notused.begin()+insert_notused);
396 const FullGraph &_gr;
397 const CostMap &_cost;
398 std::vector<Node> &_path;
399 std::vector<Node> &_notused;
402 // Implementation of the random selection rule
403 class RandomSelection {
405 RandomSelection(const FullGraph &, const CostMap &,
406 std::vector<Node> &, std::vector<Node> ¬used)
407 : _notused(notused) {}
409 Node select() const {
410 const int index = rnd[_notused.size()];
411 Node n = _notused[index];
412 _notused.erase(_notused.begin()+index);
416 std::vector<Node> &_notused;
420 // Implementation of the default insertion method
421 class DefaultInsertion {
423 Cost costDiff(Node u, Node v, Node w) const {
425 _cost[_gr.edge(u, w)] +
426 _cost[_gr.edge(v, w)] -
427 _cost[_gr.edge(u, v)];
431 DefaultInsertion(const FullGraph &gr, const CostMap &cost,
432 std::vector<Node> &path, Cost &total_cost) :
433 _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
435 void insert(Node n) const {
438 costDiff(_path.front(), _path.back(), n);
440 for (unsigned int i=1; i<_path.size(); ++i) {
441 Cost tmp = costDiff(_path[i-1], _path[i], n);
448 _path.insert(_path.begin()+min, n);
453 const FullGraph &_gr;
454 const CostMap &_cost;
455 std::vector<Node> &_path;
459 // Implementation of a special insertion method for the cheapest
461 class CheapestInsertion {
462 TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
464 CheapestInsertion(const FullGraph &, const CostMap &,
465 std::vector<Node> &, Cost &total_cost) :
466 _total(total_cost) {}
468 void insert(Cost diff) const {
478 }; // namespace lemon