Trait vrp_core::utils::SelectionSamplingSearch

source · 
pub trait SelectionSamplingSearch: Iterator {
    // Provided method
    fn sample_search<'a, T, R, FM, FI, FC>(
        self,
        sample_size: usize,
        random: Arc<dyn Random + Send + Sync>,
        map_fn: FM,
        index_fn: FI,
        compare_fn: FC
    ) -> Option<R>
       where Self: Sized + Clone + Iterator<Item = T> + 'a,
             T: 'a,
             R: 'a,
             FM: FnMut(T) -> R,
             FI: Fn(&T) -> usize,
             FC: Fn(&R, &R) -> bool { ... }
}
Expand description

Provides way to search with help of selection sampling algorithm on iterator where elements have ordered index values.

The general idea is to sample values from the sequence uniformly, find the best from them and check adjusted range, formed by these sampled values. The general motivation is that in many domains values are not distributed randomly and this approach can quickly explore promising regions and start exploiting them, significantly reducing total amount of probes.

For example:

  • let’s assume we have the following sequence: 48, 8, 45, 11, 21, 54, 15, 26, 23, 37, 58, 27, 31, 11, 60, sampling size is 4 and we want to find a maximum value.
  • at first iteration, let’s assume it samples the following values from range [0, 14):
    • 1 sample: 26 at 7
    • 2 sample: 23 at 8
    • 3 sample: 27 at 10
    • 4 sample: 11 at 13
  • the highest value is 27, so previous and next sampled indices (8, 13) give a next range to sample:
    • 5 sample: 37 at 9
    • 6 sample: 58 at 11
    • 7 sample: 31 at 12
  • here we found a better maximum (58), so we update current best and continue with further shrinking the search range
  • we repeat the process till trivial range is reached

Provided Methods§

Searches using selection sampling algorithm.

Implementors§