equal
deleted
inserted
replaced
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2010 |
5 * Copyright (C) 2003-2013 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
358 { |
358 { |
359 // Compute insertion cost and position for the unused nodes |
359 // Compute insertion cost and position for the unused nodes |
360 for (unsigned int i=0; i<_notused.size(); ++i) { |
360 for (unsigned int i=0; i<_notused.size(); ++i) { |
361 Node u = _notused[i]; |
361 Node u = _notused[i]; |
362 Cost min_cost = costDiff(_tour.back(), _tour.front(), u); |
362 Cost min_cost = costDiff(_tour.back(), _tour.front(), u); |
363 int min_pos = 0; |
363 int min_pos = 0; |
364 for (unsigned int j=1; j<_tour.size(); ++j) { |
364 for (unsigned int j=1; j<_tour.size(); ++j) { |
365 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u); |
365 Cost curr_cost = costDiff(_tour[j-1], _tour[j], u); |
366 if (curr_cost < min_cost) { |
366 if (curr_cost < min_cost) { |
367 min_cost = curr_cost; |
367 min_cost = curr_cost; |
368 min_pos = j; |
368 min_pos = j; |
388 |
388 |
389 // Remove the selected node from the unused vector |
389 // Remove the selected node from the unused vector |
390 Node sn = _notused[min_node]; |
390 Node sn = _notused[min_node]; |
391 _notused[min_node] = _notused.back(); |
391 _notused[min_node] = _notused.back(); |
392 _notused.pop_back(); |
392 _notused.pop_back(); |
393 |
393 |
394 // Insert the selected node into the tour |
394 // Insert the selected node into the tour |
395 const int ipos = _ins_pos[sn]; |
395 const int ipos = _ins_pos[sn]; |
396 _tour.insert(_tour.begin() + ipos, sn); |
396 _tour.insert(_tour.begin() + ipos, sn); |
397 |
397 |
398 // Update the insertion cost and position of the remaining nodes |
398 // Update the insertion cost and position of the remaining nodes |
403 |
403 |
404 int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1; |
404 int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1; |
405 int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1; |
405 int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1; |
406 Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u); |
406 Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u); |
407 Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u); |
407 Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u); |
408 |
408 |
409 if (nc1 <= curr_cost || nc2 <= curr_cost) { |
409 if (nc1 <= curr_cost || nc2 <= curr_cost) { |
410 // A new position is better than the old one |
410 // A new position is better than the old one |
411 if (nc1 <= nc2) { |
411 if (nc1 <= nc2) { |
412 curr_cost = nc1; |
412 curr_cost = nc1; |
413 curr_pos = ipos; |
413 curr_pos = ipos; |
418 } |
418 } |
419 else { |
419 else { |
420 if (curr_pos == ipos) { |
420 if (curr_pos == ipos) { |
421 // The minimum should be found again |
421 // The minimum should be found again |
422 curr_cost = costDiff(_tour.back(), _tour.front(), u); |
422 curr_cost = costDiff(_tour.back(), _tour.front(), u); |
423 curr_pos = 0; |
423 curr_pos = 0; |
424 for (unsigned int j=1; j<_tour.size(); ++j) { |
424 for (unsigned int j=1; j<_tour.size(); ++j) { |
425 Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u); |
425 Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u); |
426 if (tmp_cost < curr_cost) { |
426 if (tmp_cost < curr_cost) { |
427 curr_cost = tmp_cost; |
427 curr_cost = tmp_cost; |
428 curr_pos = j; |
428 curr_pos = j; |
431 } |
431 } |
432 else if (curr_pos > ipos) { |
432 else if (curr_pos > ipos) { |
433 ++curr_pos; |
433 ++curr_pos; |
434 } |
434 } |
435 } |
435 } |
436 |
436 |
437 _ins_cost[u] = curr_cost; |
437 _ins_cost[u] = curr_cost; |
438 _ins_pos[u] = curr_pos; |
438 _ins_pos[u] = curr_pos; |
439 } |
439 } |
440 |
440 |
441 return min_cost; |
441 return min_cost; |