dogs/
search_algorithm.rs

1use std::time::SystemTime;
2use std::cell::RefCell;
3use std::rc::Rc;
4
5use serde_json::json;
6
7use crate::search_manager::SearchManager;
8
9/**
10 * Stopping criterion trait
11 * Can be time limit, number of iterations, or else
12 */
13pub trait StoppingCriterion:Clone {
14    /**
15    true iff the search should finish.
16    */
17    fn is_finished(&self) -> bool;
18}
19
20/**
21stopping criterion that never stops
22*/
23#[derive(Debug, Clone, Default)]
24pub struct NeverStoppingCriterion {}
25
26impl StoppingCriterion for NeverStoppingCriterion {
27    fn is_finished(&self) -> bool { false }
28}
29
30/**
31 * stops the search after a given amount of time searching
32 */
33#[derive(Debug, Clone)]
34pub struct TimeStoppingCriterion {
35    /// starting time 
36    t_start: SystemTime,
37    /// maximum time after the beginning
38    t_max: f32,
39}
40
41impl TimeStoppingCriterion {
42    /** stops after t_max time
43    t_max: number of seconds the algorithm is allowed to run.
44    */
45    pub fn new(t_max:f32) -> Self {
46        Self {
47            t_start: SystemTime::now(),
48            t_max,
49        }
50    }
51}
52
53
54impl StoppingCriterion for TimeStoppingCriterion {
55    fn is_finished(&self) -> bool {
56        self.t_start.elapsed().unwrap().as_secs_f32() >= self.t_max
57    }
58}
59
60/**
61 * A search algorithm has a "run" method that runs until a stopping_criterion is reached
62 */
63pub trait SearchAlgorithm<N, B> {
64    /**
65     * runs until the stopping_criterion is reached
66     */
67    fn run<SC:StoppingCriterion>(&mut self, stopping_criterion:SC);
68
69    /**
70        Gets the search manager of the algorithm.
71        It allows to get the best found solution and its value, etc.
72    */
73    fn get_manager(&mut self) -> &mut SearchManager<N,B>;
74
75    /**
76     * returns true if the optimal value is found (thus we can stop the search). False by default
77     */
78    fn is_optimal(&self) -> bool { false }
79
80    /**
81    provides various statistics of events that occured during the search.
82    */
83    fn json_statistics(&self, json:&mut serde_json::Value) { json["is_optimal"] = json!(self.is_optimal()) }
84}
85
86/**
87 indicates that the algorithm can be created using an integer parameter d
88 (for instance beam search, MBA*, etc.)
89 useful for iterative beam search, iterative MBA*, etc.
90 */
91pub trait BuildableWithInteger<Space> {
92    /**
93    constructor taking an integer as a parameter.
94    */
95    fn create_with_integer(s:Rc<RefCell<Space>>, d:usize) -> Self;
96}
dogs/search_algorithm.rs

dogs/
search_algorithm.rs
