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_NEAREST_NEIGHBOUR_TSP_H
20 #define LEMON_NEAREST_NEIGHBOUR_TSP_H
24 /// \brief Nearest neighbor algorithm for symmetric TSP
29 #include <lemon/full_graph.h>
30 #include <lemon/maps.h>
36 /// \brief Nearest neighbor algorithm for symmetric TSP.
38 /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
39 /// symmetric \ref tsp "TSP".
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.
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.
50 /// \tparam CM Type of the cost map.
51 template <typename CM>
52 class NearestNeighborTsp
56 /// Type of the cost map
58 /// Type of the edge costs
59 typedef typename CM::Value Cost;
63 GRAPH_TYPEDEFS(FullGraph);
68 std::vector<Node> _path;
72 /// \brief 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) {}
80 /// \name Execution Control
83 /// \brief Runs the algorithm.
85 /// This function runs the algorithm.
87 /// \return The total cost of the found tour.
90 if (_gr.nodeNum() == 0) {
93 else if (_gr.nodeNum() == 1) {
94 _path.push_back(_gr(0));
98 std::deque<Node> path_dq;
99 Edge min_edge1 = INVALID,
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);
108 FullGraph::NodeMap<bool> used(_gr, false);
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)) {
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)) {
132 if (_cost[min_edge1] < _cost[min_edge2]) {
133 n1 = _gr.oppositeNode(n1, min_edge1);
134 path_dq.push_front(n1);
139 if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
142 n2 = _gr.oppositeNode(n2, min_edge2);
143 path_dq.push_back(n2);
148 if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
154 n2 = path_dq.front();
156 _sum = _cost[_gr.edge(n1, n2)];
157 for (int i = 1; i < int(path_dq.size()); ++i) {
161 _sum += _cost[_gr.edge(n1, n2)];
169 /// \name Query Functions
172 /// \brief The total cost of the found tour.
174 /// This function returns the total cost of the found tour.
176 /// \pre run() must be called before using this function.
177 Cost tourCost() const {
181 /// \brief Returns a const reference to the node sequence of the
184 /// This function returns a const reference to a vector
185 /// that stores the node sequence of the found tour.
187 /// \pre run() must be called before using this function.
188 const std::vector<Node>& tourNodes() const {
192 /// \brief Gives back the node sequence of the found tour.
194 /// This function copies the node sequence of the found tour into
195 /// the given standard container.
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());
203 /// \brief Gives back the found tour as a path.
205 /// This function copies the found tour as a list of arcs/edges into
206 /// the given \ref concept::Path "path structure".
208 /// \pre run() must be called before using this function.
209 template <typename Path>
210 void tour(Path &path) const {
212 for (int i = 0; i < int(_path.size()) - 1; ++i) {
213 path.addBack(_gr.arc(_path[i], _path[i+1]));
215 if (int(_path.size()) >= 2) {
216 path.addBack(_gr.arc(_path.back(), _path.front()));
224 }; // namespace lemon