solverforge_solver/phase/localsearch/acceptor/
step_counting.rs

1// Step Counting Hill Climbing acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8
9/// Step Counting Hill Climbing acceptor - allows limited non-improving moves.
10///
11/// This acceptor combines hill climbing with a step limit that resets whenever
12/// an improving move is made. It accepts:
13/// 1. Any improving move (resets the step counter)
14/// 2. Non-improving moves if step count since last improvement is below threshold
15///
16/// This enables exploration while still requiring eventual improvement.
17///
18/// # Example
19///
20/// ```
21/// use solverforge_solver::phase::localsearch::StepCountingHillClimbingAcceptor;
22/// use solverforge_core::score::SoftScore;
23/// use solverforge_core::domain::PlanningSolution;
24///
25/// #[derive(Clone)]
26/// struct MySolution;
27/// impl PlanningSolution for MySolution {
28///     type Score = SoftScore;
29///     fn score(&self) -> Option<Self::Score> { None }
30///     fn set_score(&mut self, _: Option<Self::Score>) {}
31/// }
32///
33/// // Allow up to 100 non-improving steps before requiring improvement
34/// let acceptor = StepCountingHillClimbingAcceptor::<MySolution>::new(100);
35/// ```
36pub struct StepCountingHillClimbingAcceptor<S: PlanningSolution> {
37    // Maximum steps allowed without improvement.
38    step_count_limit: u64,
39    // Current steps since last improvement.
40    steps_since_improvement: u64,
41    // Best score seen so far.
42    best_score: Option<S::Score>,
43}
44
45impl<S: PlanningSolution> Debug for StepCountingHillClimbingAcceptor<S> {
46    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
47        f.debug_struct("StepCountingHillClimbingAcceptor")
48            .field("step_count_limit", &self.step_count_limit)
49            .field("steps_since_improvement", &self.steps_since_improvement)
50            .finish()
51    }
52}
53
54impl<S: PlanningSolution> Clone for StepCountingHillClimbingAcceptor<S> {
55    fn clone(&self) -> Self {
56        Self {
57            step_count_limit: self.step_count_limit,
58            steps_since_improvement: self.steps_since_improvement,
59            best_score: self.best_score,
60        }
61    }
62}
63
64impl<S: PlanningSolution> StepCountingHillClimbingAcceptor<S> {
65    /// Creates a new Step Counting Hill Climbing acceptor.
66    ///
67    /// # Arguments
68    /// * `step_count_limit` - Maximum steps allowed without finding improvement
69    pub fn new(step_count_limit: u64) -> Self {
70        Self {
71            step_count_limit,
72            steps_since_improvement: 0,
73            best_score: None,
74        }
75    }
76}
77
78impl<S: PlanningSolution> Default for StepCountingHillClimbingAcceptor<S> {
79    fn default() -> Self {
80        Self::new(100)
81    }
82}
83
84impl<S: PlanningSolution> Acceptor<S> for StepCountingHillClimbingAcceptor<S> {
85    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
86        // Always accept improving moves
87        if move_score > last_step_score {
88            return true;
89        }
90
91        // Accept non-improving moves if within step count limit
92        self.steps_since_improvement < self.step_count_limit
93    }
94
95    fn phase_started(&mut self, initial_score: &S::Score) {
96        self.best_score = Some(*initial_score);
97        self.steps_since_improvement = 0;
98    }
99
100    fn step_ended(&mut self, step_score: &S::Score) {
101        // Check if this step improved on the best score
102        let improved = match &self.best_score {
103            Some(best) => step_score > best,
104            None => true,
105        };
106
107        if improved {
108            self.best_score = Some(*step_score);
109            self.steps_since_improvement = 0;
110        } else {
111            self.steps_since_improvement += 1;
112        }
113    }
114
115    fn phase_ended(&mut self) {
116        self.best_score = None;
117        self.steps_since_improvement = 0;
118    }
119}
120
121#[cfg(test)]
122#[path = "step_counting_tests.rs"]
123mod tests;
solverforge_solver/phase/localsearch/acceptor/step_counting.rs

solverforge_solver/phase/localsearch/acceptor/
step_counting.rs
