sim_lib_discrete_search/
problem.rs

1//! Problem and interruption traits.
2
3/// Outcome of applying a choice or propagating a state.
4#[derive(Clone, Debug, PartialEq, Eq)]
5pub enum SearchStep<State> {
6    /// Continue with the supplied state.
7    Continue(State),
8    /// Drop this prefix without treating the whole problem as impossible.
9    Pruned {
10        /// Deterministic reason recorded only in tests or diagnostics.
11        reason: String,
12    },
13    /// Reject this state as locally infeasible.
14    Infeasible {
15        /// Deterministic reason recorded only in tests or diagnostics.
16        reason: String,
17    },
18}
19
20impl<State> SearchStep<State> {
21    /// Build a pruned step with a stable reason.
22    pub fn pruned(reason: impl Into<String>) -> Self {
23        Self::Pruned {
24            reason: reason.into(),
25        }
26    }
27
28    /// Build an infeasible step with a stable reason.
29    pub fn infeasible(reason: impl Into<String>) -> Self {
30        Self::Infeasible {
31            reason: reason.into(),
32        }
33    }
34}
35
36/// Interrupt source checked by the search loop between bounded operations.
37pub trait SearchInterrupt {
38    /// Return true when the caller wants the run to stop with a cancellation
39    /// receipt.
40    fn is_cancelled(&self) -> bool;
41}
42
43/// Interrupt source that never cancels.
44#[derive(Clone, Copy, Debug, Default)]
45pub struct NeverInterrupt;
46
47impl SearchInterrupt for NeverInterrupt {
48    fn is_cancelled(&self) -> bool {
49        false
50    }
51}
52
53/// Generic state-space problem consumed by [`crate::solve`].
54pub trait SearchProblem {
55    /// State carried by the frontier.
56    type State: Clone;
57    /// Deterministic choice type; choices are sorted before they are explored.
58    type Choice: Clone + Ord;
59    /// Finished output emitted by the search.
60    type Output: Clone + std::fmt::Debug;
61
62    /// Return the initial search state.
63    fn initial_state(&self) -> Self::State;
64
65    /// Append possible choices for `state` to `out`.
66    fn expand(&self, state: &Self::State, out: &mut Vec<Self::Choice>);
67
68    /// Apply one choice to a state, or prune that prefix.
69    fn apply(&self, state: &Self::State, choice: &Self::Choice) -> SearchStep<Self::State>;
70
71    /// Propagate generic CSP constraints after a state is produced.
72    fn propagate(&self, state: Self::State) -> SearchStep<Self::State> {
73        SearchStep::Continue(state)
74    }
75
76    /// Return a finished output if this state is terminal.
77    fn finish(&self, state: &Self::State) -> Option<Self::Output>;
78
79    /// Deterministic priority score for best-first and A-star search.
80    fn score_state(&self, _state: &Self::State) -> i64 {
81        0
82    }
83
84    /// Deterministic optimistic remaining estimate for A-star and beam search.
85    fn estimate_remaining(&self, _state: &Self::State) -> i64 {
86        0
87    }
88
89    /// Lower-bound score used by branch-and-bound minimization.
90    fn bound(&self, _state: &Self::State) -> Option<i64> {
91        None
92    }
93
94    /// Score for a finished output used by branch-and-bound minimization.
95    fn output_score(&self, _output: &Self::Output) -> Option<i64> {
96        None
97    }
98}
sim_lib_discrete_search/problem.rs

sim_lib_discrete_search/
problem.rs
