COIN-OR::LEMON - Graph Library

source: lemon/lemon/nearest_neighbor_tsp.h @ 1201:9a51db038228

Last change on this file since 1201:9a51db038228 was 1201:9a51db038228, checked in by Peter Kovacs <kpeter@…>, 13 years ago

Document and greatly improve TSP algorithms (#386)

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