COIN-OR::LEMON - Graph Library

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

Last change on this file since 1337:4add05447ca0 was 1294:15e233f588da, checked in by Alpar Juttner <alpar@…>, 10 years ago

Fix invalid map query in NearestNeighborTsp? (#476)

File size: 6.7 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_NEAREST_NEIGHBOUR_TSP_H
20#define LEMON_NEAREST_NEIGHBOUR_TSP_H
21
22/// \ingroup tsp
23/// \file
24/// \brief Nearest neighbor algorithm for symmetric TSP
25
26#include <deque>
27#include <vector>
28#include <limits>
29#include <lemon/full_graph.h>
30#include <lemon/maps.h>
31
32namespace lemon {
33
34  /// \ingroup tsp
35  ///
36  /// \brief Nearest neighbor algorithm for symmetric TSP.
37  ///
38  /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
39  /// symmetric \ref tsp "TSP".
40  ///
41  /// This is probably the simplest TSP heuristic.
42  /// It starts with a minimum cost edge and at each step, it connects the
43  /// nearest unvisited node to the current path.
44  /// Finally, it connects the two end points of the path to form a tour.
45  ///
46  /// This method runs in O(n<sup>2</sup>) time.
47  /// It quickly finds a relatively short tour for most TSP instances,
48  /// but it could also yield a really bad (or even the worst) solution
49  /// in special cases.
50  ///
51  /// \tparam CM Type of the cost map.
52  template <typename CM>
53  class NearestNeighborTsp
54  {
55    public:
56
57      /// Type of the cost map
58      typedef CM CostMap;
59      /// Type of the edge costs
60      typedef typename CM::Value Cost;
61
62    private:
63
64      GRAPH_TYPEDEFS(FullGraph);
65
66      const FullGraph &_gr;
67      const CostMap &_cost;
68      Cost _sum;
69      std::vector<Node> _path;
70
71    public:
72
73      /// \brief Constructor
74      ///
75      /// Constructor.
76      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
77      /// \param cost The cost map.
78      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
79        : _gr(gr), _cost(cost) {}
80
81      /// \name Execution Control
82      /// @{
83
84      /// \brief Runs the algorithm.
85      ///
86      /// This function runs the algorithm.
87      ///
88      /// \return The total cost of the found tour.
89      Cost run() {
90        _path.clear();
91        if (_gr.nodeNum() == 0) {
92          return _sum = 0;
93        }
94        else if (_gr.nodeNum() == 1) {
95          _path.push_back(_gr(0));
96          return _sum = 0;
97        }
98
99        std::deque<Node> path_dq;
100        Edge min_edge1 = INVALID,
101             min_edge2 = INVALID;
102
103        min_edge1 = mapMin(_gr, _cost);
104        Node n1 = _gr.u(min_edge1),
105             n2 = _gr.v(min_edge1);
106        path_dq.push_back(n1);
107        path_dq.push_back(n2);
108
109        FullGraph::NodeMap<bool> used(_gr, false);
110        used[n1] = true;
111        used[n2] = true;
112
113        min_edge1 = INVALID;
114        while (int(path_dq.size()) != _gr.nodeNum()) {
115          if (min_edge1 == INVALID) {
116            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
117              if (!used[_gr.runningNode(e)] &&
118                  (min_edge1 == INVALID || _cost[e] < _cost[min_edge1])) {
119                min_edge1 = e;
120              }
121            }
122          }
123
124          if (min_edge2 == INVALID) {
125            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
126              if (!used[_gr.runningNode(e)] &&
127                  (min_edge2 == INVALID||_cost[e] < _cost[min_edge2])) {
128                min_edge2 = e;
129              }
130            }
131          }
132
133          if (_cost[min_edge1] < _cost[min_edge2]) {
134            n1 = _gr.oppositeNode(n1, min_edge1);
135            path_dq.push_front(n1);
136
137            used[n1] = true;
138            min_edge1 = INVALID;
139
140            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
141              min_edge2 = INVALID;
142          } else {
143            n2 = _gr.oppositeNode(n2, min_edge2);
144            path_dq.push_back(n2);
145
146            used[n2] = true;
147            min_edge2 = INVALID;
148
149            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
150              min_edge1 = INVALID;
151          }
152        }
153
154        n1 = path_dq.back();
155        n2 = path_dq.front();
156        _path.push_back(n2);
157        _sum = _cost[_gr.edge(n1, n2)];
158        for (int i = 1; i < int(path_dq.size()); ++i) {
159          n1 = n2;
160          n2 = path_dq[i];
161          _path.push_back(n2);
162          _sum += _cost[_gr.edge(n1, n2)];
163        }
164
165        return _sum;
166      }
167
168      /// @}
169
170      /// \name Query Functions
171      /// @{
172
173      /// \brief The total cost of the found tour.
174      ///
175      /// This function returns the total cost of the found tour.
176      ///
177      /// \pre run() must be called before using this function.
178      Cost tourCost() const {
179        return _sum;
180      }
181
182      /// \brief Returns a const reference to the node sequence of the
183      /// found tour.
184      ///
185      /// This function returns a const reference to a vector
186      /// that stores the node sequence of the found tour.
187      ///
188      /// \pre run() must be called before using this function.
189      const std::vector<Node>& tourNodes() const {
190        return _path;
191      }
192
193      /// \brief Gives back the node sequence of the found tour.
194      ///
195      /// This function copies the node sequence of the found tour into
196      /// an STL container through the given output iterator. The
197      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
198      /// For example,
199      /// \code
200      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
201      /// tsp.tourNodes(nodes.begin());
202      /// \endcode
203      /// or
204      /// \code
205      /// std::list<FullGraph::Node> nodes;
206      /// tsp.tourNodes(std::back_inserter(nodes));
207      /// \endcode
208      ///
209      /// \pre run() must be called before using this function.
210      template <typename Iterator>
211      void tourNodes(Iterator out) const {
212        std::copy(_path.begin(), _path.end(), out);
213      }
214
215      /// \brief Gives back the found tour as a path.
216      ///
217      /// This function copies the found tour as a list of arcs/edges into
218      /// the given \ref lemon::concepts::Path "path structure".
219      ///
220      /// \pre run() must be called before using this function.
221      template <typename Path>
222      void tour(Path &path) const {
223        path.clear();
224        for (int i = 0; i < int(_path.size()) - 1; ++i) {
225          path.addBack(_gr.arc(_path[i], _path[i+1]));
226        }
227        if (int(_path.size()) >= 2) {
228          path.addBack(_gr.arc(_path.back(), _path.front()));
229        }
230      }
231
232      /// @}
233
234  };
235
236}; // namespace lemon
237
238#endif
Note: See TracBrowser for help on using the repository browser.