dypdl_heuristic_search/search_algorithm/
search.rs

1use super::data_structure::{SuccessorGenerator, TransitionWithId};
2use dypdl::{variable_type::Numeric, Model, Transition, TransitionInterface};
3use std::error::Error;
4use std::{ops::Deref, rc::Rc};
5
6/// Input of a heuristic search solver.
7#[derive(Debug, PartialEq, Clone)]
8pub struct SearchInput<'a, N, V = Transition, D = Rc<TransitionWithId<V>>, R = Rc<dypdl::Model>>
9where
10    V: TransitionInterface,
11    D: Deref<Target = TransitionWithId<V>> + Clone,
12    R: Deref<Target = Model>,
13{
14    /// Root node.
15    pub node: Option<N>,
16    /// Successor generator.
17    pub generator: SuccessorGenerator<V, D, R>,
18    /// Suffix of the solution.
19    pub solution_suffix: &'a [TransitionWithId<V>],
20}
21
22/// Common parameters for heuristic search solvers.
23#[derive(Debug, PartialEq, Clone, Copy, Default)]
24pub struct Parameters<T> {
25    /// Primal bound.
26    pub primal_bound: Option<T>,
27    /// Time limit.
28    pub time_limit: Option<f64>,
29    /// Returns all feasible solutions found.
30    pub get_all_solutions: bool,
31    /// Initial capacity of a data structure saving all states.
32    pub initial_registry_capacity: Option<usize>,
33    /// Suppress log output or not.
34    pub quiet: bool,
35}
36
37/// Information about a solution.
38#[derive(Debug, Default, PartialEq, Clone)]
39pub struct Solution<T: Numeric, V = Transition> {
40    /// Solution cost.
41    /// `None` if the model is infeasible.
42    pub cost: Option<T>,
43    /// Best dual bound.
44    pub best_bound: Option<T>,
45    /// Solved to optimality or not.
46    pub is_optimal: bool,
47    /// Infeasible model or not.
48    pub is_infeasible: bool,
49    /// Transitions corresponding to the solution.
50    pub transitions: Vec<V>,
51    /// Number of expanded nodes.
52    pub expanded: usize,
53    /// Number of generated nodes.
54    pub generated: usize,
55    /// Elapsed time in seconds.
56    pub time: f64,
57    /// Whether to exceed the time limit
58    pub time_out: bool,
59}
60
61impl<T: Numeric, V> Solution<T, V> {
62    /// Returns whether the solution would never be improved.
63    pub fn is_terminated(&self) -> bool {
64        self.is_optimal || self.is_infeasible || self.time_out
65    }
66}
67
68/// Trait representing an anytime search algorithm.
69pub trait Search<T: Numeric> {
70    /// Searches for the best solution.
71    ///
72    /// # Errors
73    /// If an error occurs during the search.
74    fn search(&mut self) -> Result<Solution<T>, Box<dyn Error>> {
75        loop {
76            let (solution, terminated) = self.search_next()?;
77
78            if terminated {
79                return Ok(solution);
80            }
81        }
82    }
83
84    /// Searches for the next solution.
85    ///
86    /// # Errors
87    /// If an error occurs during the search.
88    fn search_next(&mut self) -> Result<(Solution<T>, bool), Box<dyn Error>>;
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94    use dypdl::Integer;
95
96    struct MockSearch {
97        counter: Integer,
98    }
99
100    impl Search<Integer> for MockSearch {
101        fn search_next(&mut self) -> Result<(Solution<Integer>, bool), Box<dyn Error>> {
102            if self.counter > 0 {
103                self.counter -= 1;
104                Ok((
105                    Solution {
106                        cost: Some(self.counter),
107                        ..Default::default()
108                    },
109                    false,
110                ))
111            } else {
112                Ok((
113                    Solution {
114                        cost: Some(0),
115                        ..Default::default()
116                    },
117                    true,
118                ))
119            }
120        }
121    }
122
123    #[test]
124    fn solution_is_terminated_optimal() {
125        let solution: Solution<Integer> = Solution {
126            is_optimal: true,
127            ..Default::default()
128        };
129        assert!(solution.is_terminated());
130    }
131
132    #[test]
133    fn solution_is_terminated_infeasible() {
134        let solution: Solution<Integer> = Solution {
135            is_infeasible: true,
136            ..Default::default()
137        };
138        assert!(solution.is_terminated());
139    }
140
141    #[test]
142    fn solution_is_terminated_time_out() {
143        let solution: Solution<Integer> = Solution {
144            time_out: true,
145            ..Default::default()
146        };
147        assert!(solution.is_terminated());
148    }
149
150    #[test]
151    fn solution_is_not_terminated() {
152        let solution: Solution<Integer> = Solution {
153            is_optimal: false,
154            is_infeasible: false,
155            time_out: false,
156            ..Default::default()
157        };
158        assert!(!solution.is_terminated());
159    }
160
161    #[test]
162    fn search() {
163        let mut solver = MockSearch { counter: 3 };
164        let solution = solver.search();
165        assert!(solution.is_ok());
166        assert_eq!(
167            solution.unwrap(),
168            Solution {
169                cost: Some(0),
170                ..Default::default()
171            }
172        );
173    }
174}
dypdl_heuristic_search/search_algorithm/search.rs

dypdl_heuristic_search/search_algorithm/
search.rs
