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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/greedy_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_GREEDY_TSP_H 2 20 #define LEMON_GREEDY_TSP_H 3 21 4 #include <lemon/path.h> 22 /// \ingroup tsp 23 /// \file 24 /// \brief Greedy algorithm for symmetric TSP 25 26 #include <vector> 27 #include <algorithm> 5 28 #include <lemon/full_graph.h> 6 29 #include <lemon/unionfind.h> 7 #include <algorithm>8 30 9 31 namespace lemon { 10 32 11 namespace greedy_tsp_helper { 12 13 template <typename CostMap> 14 class KeyComp { 15 typedef typename CostMap::Key Key; 16 const CostMap &cost; 33 /// \brief Greedy algorithm for symmetric TSP. 34 /// 35 /// GreedyTsp implements the greedy heuristic for solving 36 /// symmetric \ref tsp "TSP". 37 /// 38 /// This algorithm is quite similar to the \ref NearestNeighborTsp 39 /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths. 40 /// At each step, the shortest possible edge is added to these paths 41 /// as long as it does not create a cycle of less than n edges and it does 42 /// not increase the degree of any node above two. 43 /// 44 /// This method runs in O(n<sup>2</sup>log(n)) time. 45 /// It quickly finds an effectively short tour for most TSP 46 /// instances, but in special cases, it could yield a really bad 47 /// (or even the worst) solution. 48 /// 49 /// \tparam CM Type of the cost map. 50 template <typename CM> 51 class GreedyTsp 52 { 53 public: 54 55 /// Type of the cost map 56 typedef CM CostMap; 57 /// Type of the edge costs 58 typedef typename CM::Value Cost; 59 60 private: 61 62 GRAPH_TYPEDEFS(FullGraph); 63 64 const FullGraph &_gr; 65 const CostMap &_cost; 66 Cost _sum; 67 std::vector<Node> _path; 17 68 69 private: 70 71 // Functor class to compare edges by their costs 72 class EdgeComp { 73 private: 74 const CostMap &_cost; 75 18 76 public: 19 KeyComp(const CostMap &_cost) : cost(_cost) {} 20 21 bool operator() (const Key &a, const Key &b) const { 22 return cost[a] < cost[b]; 23 } 24 }; 25 26 27 template <class L> 28 L vectorConvert(const std::vector<FullGraph::Node> &_path) { 29 return L(_path.begin(), _path.end()); 30 } 31 32 template <> 33 std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) { 34 return _path; 35 } 36 37 } 38 39 40 template <typename CM> 41 class GreedyTsp { 42 private: 43 GRAPH_TYPEDEFS(FullGraph); 44 77 EdgeComp(const CostMap &cost) : _cost(cost) {} 78 79 bool operator()(const Edge &a, const Edge &b) const { 80 return _cost[a] < _cost[b]; 81 } 82 }; 83 45 84 public: 46 typedef CM CostMap; 47 typedef typename CM::Value Cost; 48 49 GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {} 50 85 86 /// \brief Constructor 87 /// 88 /// Constructor. 89 /// \param gr The \ref FullGraph "full graph" the algorithm runs on. 90 /// \param cost The cost map. 91 GreedyTsp(const FullGraph &gr, const CostMap &cost) 92 : _gr(gr), _cost(cost) {} 93 94 /// \name Execution Control 95 /// @{ 96 97 /// \brief Runs the algorithm. 98 /// 99 /// This function runs the algorithm. 100 /// 101 /// \return The total cost of the found tour. 51 102 Cost run() { 52 typedef UnionFind<FullGraph::NodeMap<int> > Union; 53 _nodes.clear(); 54 55 std::vector<int> path; 56 path.resize(_gr.nodeNum()*2, 1); 57 58 std::vector<typename CostMap::Key> sorted_edges; 103 _path.clear(); 104 105 if (_gr.nodeNum() == 0) return _sum = 0; 106 else if (_gr.nodeNum() == 1) { 107 _path.push_back(_gr(0)); 108 return _sum = 0; 109 } 110 111 std::vector<int> plist; 112 plist.resize(_gr.nodeNum()*2, 1); 113 114 std::vector<Edge> sorted_edges; 59 115 sorted_edges.reserve(_gr.edgeNum()); 60 for (EdgeIt n(_gr); n != INVALID; ++n) 61 sorted_edges.push_back(n); 62 63 std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost)); 64 65 FullGraph::NodeMap<int> nodemap(_gr); 66 Union unionfind(nodemap); 67 116 for (EdgeIt e(_gr); e != INVALID; ++e) 117 sorted_edges.push_back(e); 118 std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost)); 119 120 FullGraph::NodeMap<int> item_int_map(_gr); 121 UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map); 68 122 for (NodeIt n(_gr); n != INVALID; ++n) 69 union find.insert(n);70 123 union_find.insert(n); 124 71 125 FullGraph::NodeMap<int> degree(_gr, 0); 72 126 73 127 int nodesNum = 0, i = 0; 74 75 while ( nodesNum != _gr.nodeNum()1 ) { 76 const Edge &e = sorted_edges[i]; 77 78 const Node u = _gr.u(e), 79 v = _gr.v(e); 80 81 if (degree[u]<=1 && degree[v]<=1) { 82 if (unionfind.join(u, v)) { 128 while (nodesNum != _gr.nodeNum()1) { 129 Edge e = sorted_edges[i++]; 130 Node u = _gr.u(e), 131 v = _gr.v(e); 132 133 if (degree[u] <= 1 && degree[v] <= 1) { 134 if (union_find.join(u, v)) { 135 const int uid = _gr.id(u), 136 vid = _gr.id(v); 137 138 plist[uid*2 + degree[u]] = vid; 139 plist[vid*2 + degree[v]] = uid; 140 83 141 ++degree[u]; 84 142 ++degree[v]; 85 143 ++nodesNum; 86 87 const int uid = _gr.id(u),88 vid = _gr.id(v);89 90 91 path[uid*2 + (path[uid*2]==1 ? 0 : 1)] = vid;92 path[vid*2 + (path[vid*2]==1 ? 0 : 1)] = uid;93 144 } 94 145 } 95 96 ++i; 97 } 98 146 } 99 147 100 148 for (int i=0, n=1; i<_gr.nodeNum()*2; ++i) { 101 if (p ath[i] == 1) {149 if (plist[i] == 1) { 102 150 if (n==1) { 103 151 n = i; 104 152 } else { 105 p ath[n] = i/2;106 p ath[i] = n/2;153 plist[n] = i/2; 154 plist[i] = n/2; 107 155 break; 108 156 } … … 110 158 } 111 159 112 113 for (int i=0, j=0, last=1; i!=_gr.nodeNum(); ++i) { 114 _nodes.push_back(_gr.nodeFromId(j)); 115 116 if (path[2*j] != last) { 117 last = j; 118 j = path[2*j]; 160 for (int i=0, next=0, last=1; i!=_gr.nodeNum(); ++i) { 161 _path.push_back(_gr.nodeFromId(next)); 162 if (plist[2*next] != last) { 163 last = next; 164 next = plist[2*next]; 119 165 } else { 120 last = j;121 j = path[2*j+1];166 last = next; 167 next = plist[2*next+1]; 122 168 } 123 169 } 124 170 125 _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())]; 126 for (unsigned int i=0; i<_nodes.size()1; ++i) 127 _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])]; 171 _sum = _cost[_gr.edge(_path.back(), _path.front())]; 172 for (int i = 0; i < int(_path.size())1; ++i) { 173 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; 174 } 128 175 129 176 return _sum; 130 177 } 131 178 132 133 134 template <typename L> 135 void tourNodes(L &container) { 136 container(greedy_tsp_helper::vectorConvert<L>(_nodes)); 137 } 138 139 template <template <typename> class L> 140 L<Node> tourNodes() { 141 return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes); 142 } 143 144 const std::vector<Node>& tourNodes() { 145 return _nodes; 146 } 147 148 Path<FullGraph> tour() { 149 Path<FullGraph> p; 150 if (_nodes.size()<2) 151 return p; 152 153 for (unsigned int i=0; i<_nodes.size()1; ++i) { 154 p.addBack(_gr.arc(_nodes[i], _nodes[i+1])); 155 } 156 157 p.addBack(_gr.arc(_nodes.back(), _nodes.front())); 158 159 return p; 160 } 161 162 Cost tourCost() { 179 /// @} 180 181 /// \name Query Functions 182 /// @{ 183 184 /// \brief The total cost of the found tour. 185 /// 186 /// This function returns the total cost of the found tour. 187 /// 188 /// \pre run() must be called before using this function. 189 Cost tourCost() const { 163 190 return _sum; 164 191 } 165 166 167 private: 168 const FullGraph &_gr; 169 const CostMap &_cost; 170 Cost _sum; 171 std::vector<Node> _nodes; 192 193 /// \brief Returns a const reference to the node sequence of the 194 /// found tour. 195 /// 196 /// This function returns a const reference to the internal structure 197 /// that stores the node sequence of the found tour. 198 /// 199 /// \pre run() must be called before using this function. 200 const std::vector<Node>& tourNodes() const { 201 return _path; 202 } 203 204 /// \brief Gives back the node sequence of the found tour. 205 /// 206 /// This function copies the node sequence of the found tour into 207 /// the given standard container. 208 /// 209 /// \pre run() must be called before using this function. 210 template <typename Container> 211 void tourNodes(Container &container) const { 212 container.assign(_path.begin(), _path.end()); 213 } 214 215 /// \brief Gives back the found tour as a path. 216 /// 217 /// This function copies the found tour as a list of arcs/edges into 218 /// the given \ref concept::Path "path structure". 219 /// 220 /// \pre run() must be called before using this function. 221 template <typename Path> 222 void tour(Path &path) const { 223 path.clear(); 224 for (int i = 0; i < int(_path.size())  1; ++i) { 225 path.addBack(_gr.arc(_path[i], _path[i+1])); 226 } 227 if (int(_path.size()) >= 2) { 228 path.addBack(_gr.arc(_path.back(), _path.front())); 229 } 230 } 231 232 /// @} 233 172 234 }; 173 235
Note: See TracChangeset
for help on using the changeset viewer.