Changeset 1036:dff32ce3db71 in lemon-main for lemon/insertion_tsp.h
- Timestamp:
- 01/09/11 15:06:55 (13 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/insertion_tsp.h
r1034 r1036 25 25 26 26 #include <vector> 27 #include <functional> 27 28 #include <lemon/full_graph.h> 28 29 #include <lemon/maps.h> … … 38 39 /// symmetric \ref tsp "TSP". 39 40 /// 40 /// This is a basic TSP heuristic that has many variants. 41 /// This is a fast and effective tour construction method that has 42 /// many variants. 41 43 /// It starts with a subtour containing a few nodes of the graph and it 42 44 /// iteratively inserts the other nodes into this subtour according to a 43 45 /// certain node selection rule. 44 46 /// 45 /// This implementation provides four different node selection rules, 46 /// from which the most powerful one is used by default. 47 /// This method is among the fastest TSP algorithms, and it typically 48 /// provides quite good solutions (usually much better than 49 /// \ref NearestNeighborTsp and \ref GreedyTsp). 50 /// 51 /// InsertionTsp implements four different node selection rules, 52 /// from which the most effective one (\e farthest \e node \e selection) 53 /// is used by default. 54 /// With this choice, the algorithm runs in O(n<sup>2</sup>) time. 47 55 /// For more information, see \ref SelectionRule. 48 56 /// … … 65 73 const CostMap &_cost; 66 74 std::vector<Node> _notused; 67 std::vector<Node> _ path;75 std::vector<Node> _tour; 68 76 Cost _sum; 69 77 … … 77 85 /// During the algorithm, nodes are selected for addition to the current 78 86 /// subtour according to the applied rule. 79 /// In general, the FARTHEST method yields the best tours, thus it is the 80 /// default option. The RANDOM rule usually gives somewhat worse results, 81 /// but it is much faster than the others and it is the most robust. 87 /// The FARTHEST method is one of the fastest selection rules, and 88 /// it is typically the most effective, thus it is the default 89 /// option. The RANDOM rule usually gives slightly worse results, 90 /// but it is more robust. 82 91 /// 83 92 /// The desired selection rule can be specified as a parameter of the … … 87 96 /// An unvisited node having minimum distance from the current 88 97 /// subtour is selected at each step. 89 /// The algorithm runs in O(n<sup> 3</sup>) time using this98 /// The algorithm runs in O(n<sup>2</sup>) time using this 90 99 /// selection rule. 91 100 NEAREST, … … 93 102 /// An unvisited node having maximum distance from the current 94 103 /// subtour is selected at each step. 95 /// The algorithm runs in O(n<sup> 3</sup>) time using this104 /// The algorithm runs in O(n<sup>2</sup>) time using this 96 105 /// selection rule. 97 106 FARTHEST, … … 100 109 /// increase of the subtour's total cost is selected at each step. 101 110 /// The algorithm runs in O(n<sup>3</sup>) time using this 102 /// selection rule. 111 /// selection rule, but in most cases, it is almost as fast as 112 /// with other rules. 103 113 CHEAPEST, 104 114 … … 135 145 /// \return The total cost of the found tour. 136 146 Cost run(SelectionRule rule = FARTHEST) { 137 _ path.clear();147 _tour.clear(); 138 148 139 149 if (_gr.nodeNum() == 0) return _sum = 0; 140 150 else if (_gr.nodeNum() == 1) { 141 _ path.push_back(_gr(0));151 _tour.push_back(_gr(0)); 142 152 return _sum = 0; 143 153 } … … 146 156 case NEAREST: 147 157 init(true); 148 start<NearestSelection, DefaultInsertion>(); 158 start<ComparingSelection<std::less<Cost> >, 159 DefaultInsertion>(); 149 160 break; 150 161 case FARTHEST: 151 162 init(false); 152 start<FarthestSelection, DefaultInsertion>(); 163 start<ComparingSelection<std::greater<Cost> >, 164 DefaultInsertion>(); 153 165 break; 154 166 case CHEAPEST: … … 186 198 /// \pre run() must be called before using this function. 187 199 const std::vector<Node>& tourNodes() const { 188 return _ path;200 return _tour; 189 201 } 190 202 … … 197 209 template <typename Container> 198 210 void tourNodes(Container &container) const { 199 container.assign(_ path.begin(), _path.end());211 container.assign(_tour.begin(), _tour.end()); 200 212 } 201 213 … … 209 221 void tour(Path &path) const { 210 222 path.clear(); 211 for (int i = 0; i < int(_ path.size()) - 1; ++i) {212 path.addBack(_gr.arc(_ path[i], _path[i+1]));213 } 214 if (int(_ path.size()) >= 2) {215 path.addBack(_gr.arc(_ path.back(), _path.front()));223 for (int i = 0; i < int(_tour.size()) - 1; ++i) { 224 path.addBack(_gr.arc(_tour[i], _tour[i+1])); 225 } 226 if (int(_tour.size()) >= 2) { 227 path.addBack(_gr.arc(_tour.back(), _tour.front())); 216 228 } 217 229 } … … 225 237 Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost); 226 238 227 _ path.clear();228 _ path.push_back(_gr.u(min_edge));229 _ path.push_back(_gr.v(min_edge));239 _tour.clear(); 240 _tour.push_back(_gr.u(min_edge)); 241 _tour.push_back(_gr.v(min_edge)); 230 242 231 243 _notused.clear(); … … 242 254 template <class SelectionFunctor, class InsertionFunctor> 243 255 void start() { 244 SelectionFunctor selectNode(_gr, _cost, _ path, _notused);245 InsertionFunctor insertNode(_gr, _cost, _ path, _sum);256 SelectionFunctor selectNode(_gr, _cost, _tour, _notused); 257 InsertionFunctor insertNode(_gr, _cost, _tour, _sum); 246 258 247 259 for (int i=0; i<_gr.nodeNum()-2; ++i) { … … 249 261 } 250 262 251 _sum = _cost[_gr.edge(_path.back(), _path.front())]; 252 for (int i = 0; i < int(_path.size())-1; ++i) { 253 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; 254 } 255 } 256 257 258 // Implementation of the nearest selection rule 259 class NearestSelection { 263 _sum = _cost[_gr.edge(_tour.back(), _tour.front())]; 264 for (int i = 0; i < int(_tour.size())-1; ++i) { 265 _sum += _cost[_gr.edge(_tour[i], _tour[i+1])]; 266 } 267 } 268 269 270 // Implementation of the nearest and farthest selection rule 271 template <typename Comparator> 272 class ComparingSelection { 260 273 public: 261 NearestSelection(const FullGraph &gr, const CostMap &cost, 262 std::vector<Node> &path, std::vector<Node> ¬used) 263 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} 264 265 Node select() const { 266 Cost insert_val = 0; 267 int insert_node = -1; 268 274 ComparingSelection(const FullGraph &gr, const CostMap &cost, 275 std::vector<Node> &tour, std::vector<Node> ¬used) 276 : _gr(gr), _cost(cost), _tour(tour), _notused(notused), 277 _dist(gr, 0), _compare() 278 { 279 // Compute initial distances for the unused nodes 269 280 for (unsigned int i=0; i<_notused.size(); ++i) { 270 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])]; 271 int min_node = 0; 272 273 for (unsigned int j=1; j<_path.size(); ++j) { 274 Cost curr = _cost[_gr.edge(_notused[i], _path[j])]; 275 if (min_val > curr) { 276 min_val = curr; 277 min_node = j; 281 Node u = _notused[i]; 282 Cost min_dist = _cost[_gr.edge(u, _tour[0])]; 283 for (unsigned int j=1; j<_tour.size(); ++j) { 284 Cost curr = _cost[_gr.edge(u, _tour[j])]; 285 if (curr < min_dist) { 286 min_dist = curr; 278 287 } 279 288 } 280 281 if (insert_val > min_val || insert_node == -1) { 282 insert_val = min_val; 283 insert_node = i; 284 } 285 } 286 287 Node n = _notused[insert_node]; 288 _notused.erase(_notused.begin()+insert_node); 289 290 return n; 289 _dist[u] = min_dist; 290 } 291 } 292 293 Node select() { 294 295 // Select an used node with minimum distance 296 Cost ins_dist = 0; 297 int ins_node = -1; 298 for (unsigned int i=0; i<_notused.size(); ++i) { 299 Cost curr = _dist[_notused[i]]; 300 if (_compare(curr, ins_dist) || ins_node == -1) { 301 ins_dist = curr; 302 ins_node = i; 303 } 304 } 305 306 // Remove the selected node from the unused vector 307 Node sn = _notused[ins_node]; 308 _notused[ins_node] = _notused.back(); 309 _notused.pop_back(); 310 311 // Update the distances of the remaining nodes 312 for (unsigned int i=0; i<_notused.size(); ++i) { 313 Node u = _notused[i]; 314 Cost nc = _cost[_gr.edge(sn, u)]; 315 if (nc < _dist[u]) { 316 _dist[u] = nc; 317 } 318 } 319 320 return sn; 291 321 } 292 322 … … 294 324 const FullGraph &_gr; 295 325 const CostMap &_cost; 296 std::vector<Node> &_ path;326 std::vector<Node> &_tour; 297 327 std::vector<Node> &_notused; 328 FullGraph::NodeMap<Cost> _dist; 329 Comparator _compare; 298 330 }; 299 300 301 // Implementation of the farthest selection rule302 class FarthestSelection {303 public:304 FarthestSelection(const FullGraph &gr, const CostMap &cost,305 std::vector<Node> &path, std::vector<Node> ¬used)306 : _gr(gr), _cost(cost), _path(path), _notused(notused) {}307 308 Node select() const {309 Cost insert_val = 0;310 int insert_node = -1;311 312 for (unsigned int i=0; i<_notused.size(); ++i) {313 Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];314 int min_node = 0;315 316 for (unsigned int j=1; j<_path.size(); ++j) {317 Cost curr = _cost[_gr.edge(_notused[i], _path[j])];318 if (min_val > curr) {319 min_val = curr;320 min_node = j;321 }322 }323 324 if (insert_val < min_val || insert_node == -1) {325 insert_val = min_val;326 insert_node = i;327 }328 }329 330 Node n = _notused[insert_node];331 _notused.erase(_notused.begin()+insert_node);332 333 return n;334 }335 336 private:337 const FullGraph &_gr;338 const CostMap &_cost;339 std::vector<Node> &_path;340 std::vector<Node> &_notused;341 };342 343 331 344 332 // Implementation of the cheapest selection rule … … 354 342 public: 355 343 CheapestSelection(const FullGraph &gr, const CostMap &cost, 356 std::vector<Node> &path, std::vector<Node> ¬used) 357 : _gr(gr), _cost(cost), _path(path), _notused(notused) {} 358 359 Cost select() const { 360 int insert_notused = -1; 361 int best_insert_index = -1; 362 Cost insert_val = 0; 363 344 std::vector<Node> &tour, std::vector<Node> ¬used) 345 : _gr(gr), _cost(cost), _tour(tour), _notused(notused), 346 _ins_cost(gr, 0), _ins_pos(gr, -1) 347 { 348 // Compute insertion cost and position for the unused nodes 364 349 for (unsigned int i=0; i<_notused.size(); ++i) { 365 int min = i; 366 int best_insert_tmp = 0; 367 Cost min_val = 368 costDiff(_path.front(), _path.back(), _notused[i]); 369 370 for (unsigned int j=1; j<_path.size(); ++j) { 371 Cost tmp = 372 costDiff(_path[j-1], _path[j], _notused[i]); 373 374 if (min_val > tmp) { 375 min = i; 376 min_val = tmp; 377 best_insert_tmp = j; 350 Node u = _notused[i]; 351 Cost min_cost = costDiff(_tour.back(), _tour.front(), u); 352 int min_pos = 0; 353 for (unsigned int j=1; j<_tour.size(); ++j) { 354 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u); 355 if (curr_cost < min_cost) { 356 min_cost = curr_cost; 357 min_pos = j; 378 358 } 379 359 } 380 381 if (insert_val > min_val || insert_notused == -1) { 382 insert_notused = min; 383 insert_val = min_val; 384 best_insert_index = best_insert_tmp; 385 } 386 } 387 388 _path.insert(_path.begin()+best_insert_index, 389 _notused[insert_notused]); 390 _notused.erase(_notused.begin()+insert_notused); 391 392 return insert_val; 360 _ins_cost[u] = min_cost; 361 _ins_pos[u] = min_pos; 362 } 363 } 364 365 Cost select() { 366 367 // Select an used node with minimum insertion cost 368 Cost min_cost = 0; 369 int min_node = -1; 370 for (unsigned int i=0; i<_notused.size(); ++i) { 371 Cost curr_cost = _ins_cost[_notused[i]]; 372 if (curr_cost < min_cost || min_node == -1) { 373 min_cost = curr_cost; 374 min_node = i; 375 } 376 } 377 378 // Remove the selected node from the unused vector 379 Node sn = _notused[min_node]; 380 _notused[min_node] = _notused.back(); 381 _notused.pop_back(); 382 383 // Insert the selected node into the tour 384 const int ipos = _ins_pos[sn]; 385 _tour.insert(_tour.begin() + ipos, sn); 386 387 // Update the insertion cost and position of the remaining nodes 388 for (unsigned int i=0; i<_notused.size(); ++i) { 389 Node u = _notused[i]; 390 Cost curr_cost = _ins_cost[u]; 391 int curr_pos = _ins_pos[u]; 392 393 int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1; 394 int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1; 395 Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u); 396 Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u); 397 398 if (nc1 <= curr_cost || nc2 <= curr_cost) { 399 // A new position is better than the old one 400 if (nc1 <= nc2) { 401 curr_cost = nc1; 402 curr_pos = ipos; 403 } else { 404 curr_cost = nc2; 405 curr_pos = ipos_next; 406 } 407 } 408 else { 409 if (curr_pos == ipos) { 410 // The minimum should be found again 411 curr_cost = costDiff(_tour.back(), _tour.front(), u); 412 curr_pos = 0; 413 for (unsigned int j=1; j<_tour.size(); ++j) { 414 Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u); 415 if (tmp_cost < curr_cost) { 416 curr_cost = tmp_cost; 417 curr_pos = j; 418 } 419 } 420 } 421 else if (curr_pos > ipos) { 422 ++curr_pos; 423 } 424 } 425 426 _ins_cost[u] = curr_cost; 427 _ins_pos[u] = curr_pos; 428 } 429 430 return min_cost; 393 431 } 394 432 … … 396 434 const FullGraph &_gr; 397 435 const CostMap &_cost; 398 std::vector<Node> &_ path;436 std::vector<Node> &_tour; 399 437 std::vector<Node> &_notused; 438 FullGraph::NodeMap<Cost> _ins_cost; 439 FullGraph::NodeMap<int> _ins_pos; 400 440 }; 401 441 … … 410 450 const int index = rnd[_notused.size()]; 411 451 Node n = _notused[index]; 412 _notused.erase(_notused.begin()+index); 452 _notused[index] = _notused.back(); 453 _notused.pop_back(); 413 454 return n; 414 455 } 456 415 457 private: 416 458 std::vector<Node> &_notused; … … 430 472 public: 431 473 DefaultInsertion(const FullGraph &gr, const CostMap &cost, 432 std::vector<Node> & path, Cost &total_cost) :433 _gr(gr), _cost(cost), _ path(path), _total(total_cost) {}474 std::vector<Node> &tour, Cost &total_cost) : 475 _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {} 434 476 435 477 void insert(Node n) const { 436 478 int min = 0; 437 479 Cost min_val = 438 costDiff(_ path.front(), _path.back(), n);439 440 for (unsigned int i=1; i<_ path.size(); ++i) {441 Cost tmp = costDiff(_ path[i-1], _path[i], n);480 costDiff(_tour.front(), _tour.back(), n); 481 482 for (unsigned int i=1; i<_tour.size(); ++i) { 483 Cost tmp = costDiff(_tour[i-1], _tour[i], n); 442 484 if (tmp < min_val) { 443 485 min = i; … … 446 488 } 447 489 448 _ path.insert(_path.begin()+min, n);490 _tour.insert(_tour.begin()+min, n); 449 491 _total += min_val; 450 492 } … … 453 495 const FullGraph &_gr; 454 496 const CostMap &_cost; 455 std::vector<Node> &_ path;497 std::vector<Node> &_tour; 456 498 Cost &_total; 457 499 };
Note: See TracChangeset
for help on using the changeset viewer.