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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/insertion_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_INSERTION_TSP_H 2 20 #define LEMON_INSERTION_TSP_H 3 21 22 /// \ingroup tsp 23 /// \file 24 /// \brief Insertion algorithm for symmetric TSP 25 26 #include <vector> 4 27 #include <lemon/full_graph.h> 5 #include <lemon/path.h>6 28 #include <lemon/maps.h> 7 29 #include <lemon/random.h> 8 #include <vector>9 30 10 31 namespace lemon { 11 32 12 namespace insertion_tsp_helper {13 14 template <class L>15 L vectorConvert(const std::vector<FullGraph::Node> &_path) {16 return L(_path.begin(), _path.end());17 };18 19 template <>20 std::vector<FullGraph::Node> vectorConvert(21 const std::vector<FullGraph::Node> &_path) {22 return _path;23 };24 25 };26 33 /// \brief Insertion algorithm for symmetric TSP. 34 /// 35 /// InsertionTsp implements the insertion heuristic for solving 36 /// symmetric \ref tsp "TSP". 37 /// 38 /// This is a basic TSP heuristic that has many variants. 39 /// It starts with a subtour containing a few nodes of the graph and it 40 /// iteratively inserts the other nodes into this subtour according to a 41 /// certain node selection rule. 42 /// 43 /// This implementation provides four different node selection rules, 44 /// from which the most powerful one is used by default. 45 /// For more information, see \ref SelectionRule. 46 /// 47 /// \tparam CM Type of the cost map. 27 48 template <typename CM> 28 class InsertionTsp { 49 class InsertionTsp 50 { 51 public: 52 53 /// Type of the cost map 54 typedef CM CostMap; 55 /// Type of the edge costs 56 typedef typename CM::Value Cost; 57 29 58 private: 59 30 60 GRAPH_TYPEDEFS(FullGraph); 31 61 32 public: 33 typedef CM CostMap; 34 typedef typename CM::Value Cost; 35 36 InsertionTsp(const FullGraph &gr, const CostMap &cost) : 37 _gr(gr), _cost(cost) {} 38 39 enum InsertionMethod { 40 INSERT_NEAREST, 41 INSERT_FARTHEST, 42 INSERT_CHEAPEST, 43 INSERT_RANDOM 44 }; 45 46 Cost run(InsertionMethod method = INSERT_FARTHEST) { 47 switch (method) { 48 case INSERT_NEAREST: 49 start<InitTour<true>, NearestSelection, DefaultInsert>(); 62 const FullGraph &_gr; 63 const CostMap &_cost; 64 std::vector<Node> _notused; 65 std::vector<Node> _path; 66 Cost _sum; 67 68 public: 69 70 /// \brief Constants for specifying the node selection rule. 71 /// 72 /// Enum type containing constants for specifying the node selection 73 /// rule for the \ref run() function. 74 /// 75 /// During the algorithm, nodes are selected for addition to the current 76 /// subtour according to the applied rule. 77 /// In general, the FARTHEST yields the best tours, thus it is the 78 /// default option. RANDOM usually gives somewhat worse results, but 79 /// it is much faster than the others and it is the most robust. 80 /// 81 /// The desired selection rule can be specified as a parameter of the 82 /// \ref run() function. 83 enum SelectionRule { 84 85 /// An unvisited node having minimum distance from the current 86 /// subtour is selected at each step. 87 /// The algorithm runs in O(n<sup>3</sup>) time using this 88 /// selection rule. 89 NEAREST, 90 91 /// An unvisited node having maximum distance from the current 92 /// subtour is selected at each step. 93 /// The algorithm runs in O(n<sup>3</sup>) time using this 94 /// selection rule. 95 FARTHEST, 96 97 /// An unvisited node whose insertion results in the least 98 /// increase of the subtour's total cost is selected at each step. 99 /// The algorithm runs in O(n<sup>3</sup>) time using this 100 /// selection rule. 101 CHEAPEST, 102 103 /// An unvisited node is selected randomly without any evaluation 104 /// at each step. 105 /// The global \ref rnd "random number generator instance" is used. 106 /// You can seed it before executing the algorithm, if you 107 /// would like to. 108 /// The algorithm runs in O(n<sup>2</sup>) time using this 109 /// selection rule. 110 RANDOM 111 }; 112 113 public: 114 115 /// \brief Constructor 116 /// 117 /// Constructor. 118 /// \param gr The \ref FullGraph "full graph" the algorithm runs on. 119 /// \param cost The cost map. 120 InsertionTsp(const FullGraph &gr, const CostMap &cost) 121 : _gr(gr), _cost(cost) {} 122 123 /// \name Execution Control 124 /// @{ 125 126 /// \brief Runs the algorithm. 127 /// 128 /// This function runs the algorithm. 129 /// 130 /// \param rule The node selection rule. For more information, see 131 /// \ref SelectionRule. 132 /// 133 /// \return The total cost of the found tour. 134 Cost run(SelectionRule rule = FARTHEST) { 135 _path.clear(); 136 137 if (_gr.nodeNum() == 0) return _sum = 0; 138 else if (_gr.nodeNum() == 1) { 139 _path.push_back(_gr(0)); 140 return _sum = 0; 141 } 142 143 switch (rule) { 144 case NEAREST: 145 init(true); 146 start<NearestSelection, DefaultInsertion>(); 50 147 break; 51 case INSERT_FARTHEST: 52 start<InitTour<false>, FarthestSelection, DefaultInsert>(); 148 case FARTHEST: 149 init(false); 150 start<FarthestSelection, DefaultInsertion>(); 53 151 break; 54 case INSERT_CHEAPEST: 55 start<InitTour<true>, CheapestSelection, CheapestInsert>(); 152 case CHEAPEST: 153 init(true); 154 start<CheapestSelection, CheapestInsertion>(); 56 155 break; 57 case INSERT_RANDOM: 58 start<InitTour<true>, RandomSelection, DefaultInsert>(); 156 case RANDOM: 157 init(true); 158 start<RandomSelection, DefaultInsertion>(); 59 159 break; 60 160 } 61 return sum; 62 } 63 64 template <typename L> 65 void tourNodes(L &container) { 66 container(insertion_tsp_helper::vectorConvert<L>(nodesPath)); 67 } 68 69 template <template <typename> class L> 70 L<Node> tourNodes() { 71 return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath); 72 } 73 74 const std::vector<Node>& tourNodes() { 75 return nodesPath; 76 } 77 78 Path<FullGraph> tour() { 79 Path<FullGraph> p; 80 if (nodesPath.size()<2) 81 return p; 82 83 for (unsigned int i=0; i<nodesPath.size()1; ++i) 84 p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1])); 85 86 p.addBack(_gr.arc(nodesPath.back(), nodesPath.front())); 87 return p; 88 } 89 90 Cost tourCost() { 91 return sum; 92 } 93 161 return _sum; 162 } 163 164 /// @} 165 166 /// \name Query Functions 167 /// @{ 168 169 /// \brief The total cost of the found tour. 170 /// 171 /// This function returns the total cost of the found tour. 172 /// 173 /// \pre run() must be called before using this function. 174 Cost tourCost() const { 175 return _sum; 176 } 177 178 /// \brief Returns a const reference to the node sequence of the 179 /// found tour. 180 /// 181 /// This function returns a const reference to the internal structure 182 /// that stores the node sequence of the found tour. 183 /// 184 /// \pre run() must be called before using this function. 185 const std::vector<Node>& tourNodes() const { 186 return _path; 187 } 188 189 /// \brief Gives back the node sequence of the found tour. 190 /// 191 /// This function copies the node sequence of the found tour into 192 /// the given standard container. 193 /// 194 /// \pre run() must be called before using this function. 195 template <typename Container> 196 void tourNodes(Container &container) const { 197 container.assign(_path.begin(), _path.end()); 198 } 199 200 /// \brief Gives back the found tour as a path. 201 /// 202 /// This function copies the found tour as a list of arcs/edges into 203 /// the given \ref concept::Path "path structure". 204 /// 205 /// \pre run() must be called before using this function. 206 template <typename Path> 207 void tour(Path &path) const { 208 path.clear(); 209 for (int i = 0; i < int(_path.size())  1; ++i) { 210 path.addBack(_gr.arc(_path[i], _path[i+1])); 211 } 212 if (int(_path.size()) >= 2) { 213 path.addBack(_gr.arc(_path.back(), _path.front())); 214 } 215 } 216 217 /// @} 94 218 95 219 private: 96 220 97 template <bool MIN> 98 class InitTour { 99 public: 100 InitTour(const FullGraph &gr, const CostMap &cost, 101 std::vector<Node> &used, std::vector<Node> ¬used, 102 Cost &fullcost) : 103 _gr(gr), _cost(cost), _used(used), _notused(notused), 104 _fullcost(fullcost) {} 105 106 std::vector<Node> init() const { 107 Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost); 108 std::vector<Node> path; 109 path.push_back(_gr.u(min)); 110 path.push_back(_gr.v(min)); 111 112 _used.clear(); 113 _notused.clear(); 114 for (NodeIt n(_gr); n!=INVALID; ++n) { 115 if (n != _gr.u(min) && n != _gr.v(min)) { 116 _notused.push_back(n); 221 // Initializes the algorithm 222 void init(bool min) { 223 Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost); 224 225 _path.clear(); 226 _path.push_back(_gr.u(min_edge)); 227 _path.push_back(_gr.v(min_edge)); 228 229 _notused.clear(); 230 for (NodeIt n(_gr); n!=INVALID; ++n) { 231 if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) { 232 _notused.push_back(n); 233 } 234 } 235 236 _sum = _cost[min_edge] * 2; 237 } 238 239 // Executes the algorithm 240 template <class SelectionFunctor, class InsertionFunctor> 241 void start() { 242 SelectionFunctor selectNode(_gr, _cost, _path, _notused); 243 InsertionFunctor insertNode(_gr, _cost, _path, _sum); 244 245 for (int i=0; i<_gr.nodeNum()2; ++i) { 246 insertNode.insert(selectNode.select()); 247 } 248 249 _sum = _cost[_gr.edge(_path.back(), _path.front())]; 250 for (int i = 0; i < int(_path.size())1; ++i) { 251 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; 252 } 253 } 254 255 256 // Implementation of the nearest selection rule 257 class NearestSelection { 258 public: 259 NearestSelection(const FullGraph &gr, const CostMap &cost, 260 std::vector<Node> &path, std::vector<Node> ¬used) 261 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} 262 263 Node select() const { 264 Cost insert_val = 0; 265 int insert_node = 1; 266 267 for (unsigned int i=0; i<_notused.size(); ++i) { 268 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; 269 int min_node = 0; 270 271 for (unsigned int j=1; j<_path.size(); ++j) { 272 Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; 273 if (min_val > curr) { 274 min_val = curr; 275 min_node = j; 276 } 277 } 278 279 if (insert_val > min_val  insert_node == 1) { 280 insert_val = min_val; 281 insert_node = i; 117 282 } 118 283 } 119 _used.push_back(_gr.u(min)); 120 _used.push_back(_gr.v(min));121 122 _fullcost = _cost[min]*2; 123 return path;284 285 Node n = _notused[insert_node]; 286 _notused.erase(_notused.begin()+insert_node); 287 288 return n; 124 289 } 125 290 … … 127 292 const FullGraph &_gr; 128 293 const CostMap &_cost; 129 std::vector<Node> &_ used;294 std::vector<Node> &_path; 130 295 std::vector<Node> &_notused; 131 Cost &_fullcost; 132 }; 133 134 class NearestSelection { 135 public: 136 NearestSelection(const FullGraph &gr, const CostMap &cost, 137 std::vector<Node> &used, std::vector<Node> ¬used) : 138 _gr(gr), _cost(cost), _used(used), _notused(notused) {} 139 296 }; 297 298 299 // Implementation of the farthest selection rule 300 class FarthestSelection { 301 public: 302 FarthestSelection(const FullGraph &gr, const CostMap &cost, 303 std::vector<Node> &path, std::vector<Node> ¬used) 304 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} 305 140 306 Node select() const { 141 142 Cost insert_val = 143 std::numeric_limits<Cost>::max(); 307 Cost insert_val = 0; 144 308 int insert_node = 1; 145 309 146 310 for (unsigned int i=0; i<_notused.size(); ++i) { 147 Cost min_val = _cost[_gr.edge(_notused[i], _ used[0])];311 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; 148 312 int min_node = 0; 149 150 for (unsigned int j=1; j<_used.size(); ++j) { 151 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) { 152 min_val = _cost[_gr.edge(_notused[i], _used[j])]; 153 min_node = j; 154 } 155 } 156 157 if (insert_val > min_val) { 158 insert_val = min_val; 159 insert_node = i; 160 } 161 } 162 163 Node n = _notused[insert_node]; 164 _notused.erase(_notused.begin()+insert_node); 165 166 return n; 167 } 168 169 private: 170 const FullGraph &_gr; 171 const CostMap &_cost; 172 std::vector<Node> &_used; 173 std::vector<Node> &_notused; 174 }; 175 176 class FarthestSelection { 177 public: 178 FarthestSelection(const FullGraph &gr, const CostMap &cost, 179 std::vector<Node> &used, std::vector<Node> ¬used) : 180 _gr(gr), _cost(cost), _used(used), _notused(notused) {} 181 182 Node select() const { 183 184 Cost insert_val = 185 std::numeric_limits<Cost>::min(); 186 int insert_node = 1; 187 188 for (unsigned int i=0; i<_notused.size(); ++i) { 189 Cost min_val = _cost[_gr.edge(_notused[i], _used[0])]; 190 int min_node = 0; 191 192 for (unsigned int j=1; j<_used.size(); ++j) { 193 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) { 194 min_val = _cost[_gr.edge(_notused[i], _used[j])]; 313 314 for (unsigned int j=1; j<_path.size(); ++j) { 315 Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; 316 if (min_val > curr) { 317 min_val = curr; 195 318 min_node = j; 196 319 } 197 320 } 198 321 199 322 if (insert_val < min_val  insert_node == 1) { 200 323 insert_val = min_val; … … 202 325 } 203 326 } 204 327 205 328 Node n = _notused[insert_node]; 206 329 _notused.erase(_notused.begin()+insert_node); 207 330 208 331 return n; 209 332 } 210 333 211 334 private: 212 335 const FullGraph &_gr; 213 336 const CostMap &_cost; 214 std::vector<Node> &_ used;337 std::vector<Node> &_path; 215 338 std::vector<Node> &_notused; 216 339 }; 217 340 218 341 342 // Implementation of the cheapest selection rule 219 343 class CheapestSelection { 220 344 private: 221 345 Cost costDiff(Node u, Node v, Node w) const { 222 return 346 return 223 347 _cost[_gr.edge(u, w)] + 224 348 _cost[_gr.edge(v, w)]  … … 228 352 public: 229 353 CheapestSelection(const FullGraph &gr, const CostMap &cost, 230 std::vector<Node> & used, std::vector<Node> ¬used) :231 _gr(gr), _cost(cost), _used(used), _notused(notused) {}232 354 std::vector<Node> &path, std::vector<Node> ¬used) 355 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} 356 233 357 Cost select() const { 234 358 int insert_notused = 1; 235 359 int best_insert_index = 1; 236 Cost insert_val = 237 std::numeric_limits<Cost>::max(); 238 360 Cost insert_val = 0; 361 239 362 for (unsigned int i=0; i<_notused.size(); ++i) { 240 363 int min = i; 241 364 int best_insert_tmp = 0; 242 365 Cost min_val = 243 costDiff(_ used.front(), _used.back(), _notused[i]);244 245 for (unsigned int j=1; j<_ used.size(); ++j) {366 costDiff(_path.front(), _path.back(), _notused[i]); 367 368 for (unsigned int j=1; j<_path.size(); ++j) { 246 369 Cost tmp = 247 costDiff(_ used[j1], _used[j], _notused[i]);370 costDiff(_path[j1], _path[j], _notused[i]); 248 371 249 372 if (min_val > tmp) { … … 254 377 } 255 378 256 if (insert_val > min_val ) {379 if (insert_val > min_val  insert_notused == 1) { 257 380 insert_notused = min; 258 381 insert_val = min_val; … … 261 384 } 262 385 263 _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]); 386 _path.insert(_path.begin()+best_insert_index, 387 _notused[insert_notused]); 264 388 _notused.erase(_notused.begin()+insert_notused); 265 389 266 390 return insert_val; 267 391 } 268 392 269 393 private: 270 394 const FullGraph &_gr; 271 395 const CostMap &_cost; 272 std::vector<Node> &_ used;396 std::vector<Node> &_path; 273 397 std::vector<Node> &_notused; 274 398 }; 275 399 400 // Implementation of the random selection rule 276 401 class RandomSelection { 277 402 public: 278 403 RandomSelection(const FullGraph &, const CostMap &, 279 std::vector<Node> &, std::vector<Node> ¬used) : 280 _notused(notused) { 281 rnd.seedFromTime(); 282 } 283 404 std::vector<Node> &, std::vector<Node> ¬used) 405 : _notused(notused) {} 406 284 407 Node select() const { 285 408 const int index = rnd[_notused.size()]; … … 293 416 294 417 295 class DefaultInsert { 418 // Implementation of the default insertion method 419 class DefaultInsertion { 296 420 private: 297 421 Cost costDiff(Node u, Node v, Node w) const { 298 return 422 return 299 423 _cost[_gr.edge(u, w)] + 300 424 _cost[_gr.edge(v, w)]  301 425 _cost[_gr.edge(u, v)]; 302 426 } 303 304 public: 305 DefaultInsert (const FullGraph &gr, const CostMap &cost,306 std::vector<Node> &path, Cost &fullcost) :307 _gr(gr), _cost(cost), _path(path), _ fullcost(fullcost) {}308 427 428 public: 429 DefaultInsertion(const FullGraph &gr, const CostMap &cost, 430 std::vector<Node> &path, Cost &total_cost) : 431 _gr(gr), _cost(cost), _path(path), _total(total_cost) {} 432 309 433 void insert(Node n) const { 310 434 int min = 0; 311 435 Cost min_val = 312 436 costDiff(_path.front(), _path.back(), n); 313 437 314 438 for (unsigned int i=1; i<_path.size(); ++i) { 315 439 Cost tmp = costDiff(_path[i1], _path[i], n); … … 319 443 } 320 444 } 321 445 322 446 _path.insert(_path.begin()+min, n); 323 _ fullcost+= min_val;324 } 325 447 _total += min_val; 448 } 449 326 450 private: 327 451 const FullGraph &_gr; 328 452 const CostMap &_cost; 329 453 std::vector<Node> &_path; 330 Cost &_fullcost; 331 }; 332 333 class CheapestInsert { 454 Cost &_total; 455 }; 456 457 // Implementation of a special insertion method for the cheapest 458 // selection rule 459 class CheapestInsertion { 334 460 TEMPLATE_GRAPH_TYPEDEFS(FullGraph); 335 461 public: 336 CheapestInsert (const FullGraph &, const CostMap &,337 std::vector<Node> &, Cost &fullcost) :338 _ fullcost(fullcost) {}339 462 CheapestInsertion(const FullGraph &, const CostMap &, 463 std::vector<Node> &, Cost &total_cost) : 464 _total(total_cost) {} 465 340 466 void insert(Cost diff) const { 341 _fullcost += diff; 342 } 343 344 private: 345 Cost &_fullcost; 346 }; 347 348 349 template <class InitFunctor, class SelectionFunctor, class InsertFunctor> 350 void start() { 351 InitFunctor init(_gr, _cost, nodesPath, notused, sum); 352 SelectionFunctor selectNode(_gr, _cost, nodesPath, notused); 353 InsertFunctor insertNode(_gr, _cost, nodesPath, sum); 354 355 nodesPath = init.init(); 356 357 for (int i=0; i<_gr.nodeNum()2; ++i) { 358 insertNode.insert(selectNode.select()); 359 } 360 361 sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ]; 362 for (unsigned int i=0; i<nodesPath.size()1; ++i) 363 sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ]; 364 } 365 366 const FullGraph &_gr; 367 const CostMap &_cost; 368 std::vector<Node> notused; 369 std::vector<Node> nodesPath; 370 Cost sum; 467 _total += diff; 468 } 469 470 private: 471 Cost &_total; 472 }; 473 371 474 }; 372 475 373 476 }; // namespace lemon 374 477
Note: See TracChangeset
for help on using the changeset viewer.