COIN-OR::LEMON - Graph Library

source: lemon/lemon/nearest_neighbor_tsp.h @ 1202:ef200e268af2

Last change on this file since 1202:ef200e268af2 was 1202:ef200e268af2, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Unifications and improvements in TSP algorithms (#386)

File size: 6.3 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 <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 short tour for most TSP instances, but in special
48  /// cases, it could yield a really bad (or even the worst) solution.
49  ///
50  /// \tparam CM Type of the cost map.
51  template <typename CM>
52  class NearestNeighborTsp
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
61    private:
62
63      GRAPH_TYPEDEFS(FullGraph);
64
65      const FullGraph &_gr;
66      const CostMap &_cost;
67      Cost _sum;
68      std::vector<Node> _path;
69
70    public:
71
72      /// \brief Constructor
73      ///
74      /// Constructor.
75      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
76      /// \param cost The cost map.
77      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
78        : _gr(gr), _cost(cost) {}
79
80      /// \name Execution Control
81      /// @{
82
83      /// \brief Runs the algorithm.
84      ///
85      /// This function runs the algorithm.
86      ///
87      /// \return The total cost of the found tour.
88      Cost run() {
89        _path.clear();
90        if (_gr.nodeNum() == 0) {
91          return _sum = 0;
92        }
93        else if (_gr.nodeNum() == 1) {
94          _path.push_back(_gr(0));
95          return _sum = 0;
96        }
97
98        std::deque<Node> path_dq;
99        Edge min_edge1 = INVALID,
100             min_edge2 = INVALID;
101
102        min_edge1 = mapMin(_gr, _cost);
103        Node n1 = _gr.u(min_edge1),
104             n2 = _gr.v(min_edge1);
105        path_dq.push_back(n1);
106        path_dq.push_back(n2);
107
108        FullGraph::NodeMap<bool> used(_gr, false);
109        used[n1] = true;
110        used[n2] = true;
111
112        min_edge1 = INVALID;
113        while (int(path_dq.size()) != _gr.nodeNum()) {
114          if (min_edge1 == INVALID) {
115            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
116              if (!used[_gr.runningNode(e)] &&
117                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
118                min_edge1 = e;
119              }
120            }
121          }
122
123          if (min_edge2 == INVALID) {
124            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
125              if (!used[_gr.runningNode(e)] &&
126                  (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
127                min_edge2 = e;
128              }
129            }
130          }
131
132          if (_cost[min_edge1] < _cost[min_edge2]) {
133            n1 = _gr.oppositeNode(n1, min_edge1);
134            path_dq.push_front(n1);
135
136            used[n1] = true;
137            min_edge1 = INVALID;
138
139            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
140              min_edge2 = INVALID;
141          } else {
142            n2 = _gr.oppositeNode(n2, min_edge2);
143            path_dq.push_back(n2);
144
145            used[n2] = true;
146            min_edge2 = INVALID;
147
148            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
149              min_edge1 = INVALID;
150          }
151        }
152
153        n1 = path_dq.back();
154        n2 = path_dq.front();
155        _path.push_back(n2);
156        _sum = _cost[_gr.edge(n1, n2)];
157        for (int i = 1; i < int(path_dq.size()); ++i) {
158          n1 = n2;
159          n2 = path_dq[i];
160          _path.push_back(n2);
161          _sum += _cost[_gr.edge(n1, n2)];
162        }
163
164        return _sum;
165      }
166
167      /// @}
168
169      /// \name Query Functions
170      /// @{
171
172      /// \brief The total cost of the found tour.
173      ///
174      /// This function returns the total cost of the found tour.
175      ///
176      /// \pre run() must be called before using this function.
177      Cost tourCost() const {
178        return _sum;
179      }
180
181      /// \brief Returns a const reference to the node sequence of the
182      /// found tour.
183      ///
184      /// This function returns a const reference to a vector
185      /// that stores the node sequence of the found tour.
186      ///
187      /// \pre run() must be called before using this function.
188      const std::vector<Node>& tourNodes() const {
189        return _path;
190      }
191
192      /// \brief Gives back the node sequence of the found tour.
193      ///
194      /// This function copies the node sequence of the found tour into
195      /// the given standard container.
196      ///
197      /// \pre run() must be called before using this function.
198      template <typename Container>
199      void tourNodes(Container &container) const {
200        container.assign(_path.begin(), _path.end());
201      }
202
203      /// \brief Gives back the found tour as a path.
204      ///
205      /// This function copies the found tour as a list of arcs/edges into
206      /// the given \ref concept::Path "path structure".
207      ///
208      /// \pre run() must be called before using this function.
209      template <typename Path>
210      void tour(Path &path) const {
211        path.clear();
212        for (int i = 0; i < int(_path.size()) - 1; ++i) {
213          path.addBack(_gr.arc(_path[i], _path[i+1]));
214        }
215        if (int(_path.size()) >= 2) {
216          path.addBack(_gr.arc(_path.back(), _path.front()));
217        }
218      }
219
220      /// @}
221
222  };
223
224}; // namespace lemon
225
226#endif
Note: See TracBrowser for help on using the repository browser.