Changes in / [1138:c8896bc31271:1137:eb12ad2789fc] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r1136 r1026 123 123 /// the \ref run() function. 124 124 /// 125 /// \ref NetworkSimplex provides five different implementations for126 /// the pivot strategy that significantly affectsthe running time125 /// \ref NetworkSimplex provides five different pivot rule 126 /// implementations that significantly affect the running time 127 127 /// of the algorithm. 128 /// According to experimental tests conducted on various problem 129 /// instances, \ref BLOCK_SEARCH "Block Search" and 130 /// \ref ALTERING_LIST "Altering Candidate List" rules turned out 131 /// to be the most efficient. 132 /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that 133 /// seemed to be slightly more robust, it is used by default. 134 /// However, another pivot rule can easily be selected using the 135 /// \ref run() function with the proper parameter. 128 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 129 /// turend out to be the most efficient and the most robust on various 130 /// test inputs. 131 /// However, another pivot rule can be selected using the \ref run() 132 /// function with the proper parameter. 136 133 enum PivotRule { 137 134 … … 159 156 /// The \e Altering \e Candidate \e List pivot rule. 160 157 /// It is a modified version of the Candidate List method. 161 /// It keeps only a few of thebest eligible arcs from the former158 /// It keeps only the several best eligible arcs from the former 162 159 /// candidate list and extends this list in every iteration. 163 160 ALTERING_LIST … … 542 539 SortFunc(const CostVector &map) : _map(map) {} 543 540 bool operator()(int left, int right) { 544 return _map[left] <_map[right];541 return _map[left] > _map[right]; 545 542 } 546 543 }; … … 560 557 const double BLOCK_SIZE_FACTOR = 1.0; 561 558 const int MIN_BLOCK_SIZE = 10; 562 const double HEAD_LENGTH_FACTOR = 0. 01;559 const double HEAD_LENGTH_FACTOR = 0.1; 563 560 const int MIN_HEAD_LENGTH = 3; 564 561 … … 604 601 } 605 602 for (e = 0; e != _next_arc; ++e) { 606 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);607 if (c < 0) {608 _cand_cost[e] = c;603 _cand_cost[e] = _state[e] * 604 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 605 if (_cand_cost[e] < 0) { 609 606 _candidates[_curr_length++] = e; 610 607 } … … 619 616 search_end: 620 617 621 // Perform partial sort operation on the candidate list 622 int new_length = std::min(_head_length + 1, _curr_length); 623 std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, 624 _candidates.begin() + _curr_length, _sort_func); 625 626 // Select the entering arc and remove it from the list 618 // Make heap of the candidate list (approximating a partial sort) 619 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, 620 _sort_func ); 621 622 // Pop the first element of the heap 627 623 _in_arc = _candidates[0]; 628 624 _next_arc = e; 629 _candidates[0] = _candidates[new_length - 1]; 630 _curr_length = new_length - 1; 625 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 626 _sort_func ); 627 _curr_length = std::min(_head_length, _curr_length - 1); 631 628 return true; 632 629 }
Note: See TracChangeset
for help on using the changeset viewer.