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
28 #include <lemon/full_graph.h>
29 #include <lemon/maps.h>
33 /// \brief Nearest neighbor algorithm for symmetric TSP.
35 /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
36 /// symmetric \ref tsp "TSP".
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.
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.
48 /// \tparam CM Type of the cost map.
49 template <typename CM>
50 class NearestNeighborTsp
54 /// Type of the cost map
56 /// Type of the edge costs
57 typedef typename CM::Value Cost;
61 GRAPH_TYPEDEFS(FullGraph);
66 std::deque<Node> _path;
70 /// \brief 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) {}
78 /// \name Execution Control
81 /// \brief Runs the algorithm.
83 /// This function runs the algorithm.
85 /// \return The total cost of the found tour.
89 if (_gr.nodeNum() == 0) return _sum = 0;
90 else if (_gr.nodeNum() == 1) {
91 _path.push_back(_gr(0));
95 Edge min_edge1 = INVALID,
98 min_edge1 = mapMin(_gr, _cost);
99 Node n1 = _gr.u(min_edge1),
100 n2 = _gr.v(min_edge1);
104 FullGraph::NodeMap<bool> used(_gr, false);
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)) {
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)) {
128 if (_cost[min_edge1] < _cost[min_edge2]) {
129 n1 = _gr.oppositeNode(n1, min_edge1);
130 _path.push_front(n1);
135 if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
138 n2 = _gr.oppositeNode(n2, min_edge2);
144 if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
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])];
159 /// \name Query Functions
162 /// \brief The total cost of the found tour.
164 /// This function returns the total cost of the found tour.
166 /// \pre run() must be called before using this function.
167 Cost tourCost() const {
171 /// \brief Returns a const reference to the node sequence of the
174 /// This function returns a const reference to the internal structure
175 /// that stores the node sequence of the found tour.
177 /// \pre run() must be called before using this function.
178 const std::deque<Node>& tourNodes() const {
182 /// \brief Gives back the node sequence of the found tour.
184 /// This function copies the node sequence of the found tour into
185 /// the given standard container.
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());
193 /// \brief Gives back the found tour as a path.
195 /// This function copies the found tour as a list of arcs/edges into
196 /// the given \ref concept::Path "path structure".
198 /// \pre run() must be called before using this function.
199 template <typename Path>
200 void tour(Path &path) const {
202 for (int i = 0; i < int(_path.size()) - 1; ++i) {
203 path.addBack(_gr.arc(_path[i], _path[i+1]));
205 if (int(_path.size()) >= 2) {
206 path.addBack(_gr.arc(_path.back(), _path.front()));
214 }; // namespace lemon