Changeset 1201:9a51db038228 in lemon for lemon/nearest_neighbor_tsp.h
 Timestamp:
 01/08/11 22:51:16 (9 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/nearest_neighbor_tsp.h
r1199 r1201 1 /* * mode: C++; indenttabsmode: nil; * 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 20032010 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 1 19 #ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H 2 20 #define LEMON_NEAREST_NEIGHBOUR_TSP_H 3 21 22 /// \ingroup tsp 23 /// \file 24 /// \brief Nearest neighbor algorithm for symmetric TSP 25 4 26 #include <deque> 27 #include <limits> 5 28 #include <lemon/full_graph.h> 6 #include <lemon/path.h>7 29 #include <lemon/maps.h> 8 30 9 31 namespace lemon { 10 11 namespace nn_helper { 12 template <class L> 13 L dequeConvert(const std::deque<FullGraph::Node> &_path) { 14 return L(_path.begin(), _path.end()); 15 } 16 17 template <> 18 std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) { 19 return _path; 20 } 21 } 22 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. 23 49 template <typename CM> 24 class NearestNeighborTsp { 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 25 59 private: 60 26 61 GRAPH_TYPEDEFS(FullGraph); 27 62 63 const FullGraph &_gr; 64 const CostMap &_cost; 65 Cost _sum; 66 std::deque<Node> _path; 67 28 68 public: 29 typedef CM CostMap; 30 typedef typename CM::Value Cost; 31 32 NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {} 33 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. 34 86 Cost run() { 35 87 _path.clear(); 36 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 37 95 Edge min_edge1 = INVALID, 38 96 min_edge2 = INVALID; 39 97 40 98 min_edge1 = mapMin(_gr, _cost); 41 42 FullGraph::NodeMap<bool> used(_gr, false); 43 44 Node n1 = _gr.u(min_edge1), 99 Node n1 = _gr.u(min_edge1), 45 100 n2 = _gr.v(min_edge1); 46 47 101 _path.push_back(n1); 48 102 _path.push_back(n2); 49 103 104 FullGraph::NodeMap<bool> used(_gr, false); 50 105 used[n1] = true; 51 106 used[n2] = true; 52 107 53 108 min_edge1 = INVALID; 54 55 109 while (int(_path.size()) != _gr.nodeNum()) { 56 110 if (min_edge1 == INVALID) { 57 for (IncEdgeIt e(_gr, n1); e !=INVALID; ++e) {58 if (!used[_gr.runningNode(e)] ) {59 if (min_edge1==INVALID  _cost[min_edge1] > _cost[e])60 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; 61 115 } 62 116 } … … 64 118 65 119 if (min_edge2 == INVALID) { 66 for (IncEdgeIt e(_gr, n2); e !=INVALID; ++e) {67 if (!used[_gr.runningNode(e)] ) {68 if (min_edge2==INVALID  _cost[min_edge2] > _cost[e])69 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; 70 124 } 71 125 } 72 126 } 73 127 74 if ( _cost[min_edge1] < _cost[min_edge2]) {75 n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);128 if (_cost[min_edge1] < _cost[min_edge2]) { 129 n1 = _gr.oppositeNode(n1, min_edge1); 76 130 _path.push_front(n1); 77 131 … … 79 133 min_edge1 = INVALID; 80 134 81 if (_gr.u(min_edge2) ==n1  _gr.v(min_edge2)==n1)135 if (_gr.u(min_edge2) == n1  _gr.v(min_edge2) == n1) 82 136 min_edge2 = INVALID; 83 137 } else { 84 n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);138 n2 = _gr.oppositeNode(n2, min_edge2); 85 139 _path.push_back(n2); 86 140 … … 88 142 min_edge2 = INVALID; 89 143 90 if (_gr.u(min_edge1) ==n2  _gr.v(min_edge1)==n2)144 if (_gr.u(min_edge1) == n2  _gr.v(min_edge1) == n2) 91 145 min_edge1 = INVALID; 92 146 } 93 147 } 94 148 95 _sum = _cost[ _gr.edge(_path.back(), _path.front()) ]; 96 for (unsigned int i=0; i<_path.size()1; ++i) 97 _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ]; 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 } 98 153 99 154 return _sum; 100 155 } 101 156 102 103 template <typename L> 104 void tourNodes(L &container) { 105 container(nn_helper::dequeConvert<L>(_path)); 106 } 107 108 template <template <typename> class L> 109 L<Node> tourNodes() { 110 return nn_helper::dequeConvert<L<Node> >(_path); 111 } 112 113 const std::deque<Node>& tourNodes() { 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 { 114 179 return _path; 115 180 } 116 117 Path<FullGraph> tour() { 118 Path<FullGraph> p; 119 if (_path.size()<2) 120 return p; 121 122 for (unsigned int i=0; i<_path.size()1; ++i) { 123 p.addBack(_gr.arc(_path[i], _path[i+1])); 124 } 125 p.addBack(_gr.arc(_path.back(), _path.front())); 126 127 return p; 128 } 129 130 Cost tourCost() { 131 return _sum; 132 } 133 134 135 private: 136 const FullGraph &_gr; 137 const CostMap &_cost; 138 Cost _sum; 139 std::deque<Node> _path; 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 140 212 }; 141 213 142 143 214 }; // namespace lemon 144 215
Note: See TracChangeset
for help on using the changeset viewer.