solverforge_solver/phase/localsearch/forager/
improving.rs

1use std::fmt::Debug;
2use std::marker::PhantomData;
3
4use solverforge_core::domain::PlanningSolution;
5use solverforge_core::score::Score;
6
7use crate::heuristic::r#move::Move;
8use crate::heuristic::selector::move_selector::CandidateId;
9
10use super::{BestCandidate, ForagerDecision, LocalSearchForager};
11
12/// A forager that picks the first accepted move that improves on the best score ever seen.
13///
14/// Once a move with a score strictly better than the all-time best is found, the
15/// forager quits immediately and selects that move. If no such move exists, it falls
16/// back to the best among all accepted moves.
17pub struct FirstBestScoreImprovingForager<S>
18where
19    S: PlanningSolution,
20{
21    best_score: S::Score,
22    best_move: BestCandidate<S>,
23    found_best_improving: bool,
24    _phantom: PhantomData<fn() -> S>,
25}
26
27impl<S> FirstBestScoreImprovingForager<S>
28where
29    S: PlanningSolution,
30{
31    pub fn new(random_ties: bool) -> Self {
32        Self {
33            best_score: S::Score::zero(),
34            best_move: BestCandidate::new(random_ties),
35            found_best_improving: false,
36            _phantom: PhantomData,
37        }
38    }
39}
40
41impl<S> Default for FirstBestScoreImprovingForager<S>
42where
43    S: PlanningSolution,
44{
45    fn default() -> Self {
46        Self::new(true)
47    }
48}
49
50impl<S> Debug for FirstBestScoreImprovingForager<S>
51where
52    S: PlanningSolution,
53{
54    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
55        f.debug_struct("FirstBestScoreImprovingForager")
56            .field("found_best_improving", &self.found_best_improving)
57            .finish()
58    }
59}
60
61impl<S> Clone for FirstBestScoreImprovingForager<S>
62where
63    S: PlanningSolution,
64{
65    fn clone(&self) -> Self {
66        Self {
67            best_score: self.best_score,
68            best_move: BestCandidate::new(self.best_move.random_ties()),
69            found_best_improving: false,
70            _phantom: PhantomData,
71        }
72    }
73}
74
75impl<S, M> LocalSearchForager<S, M> for FirstBestScoreImprovingForager<S>
76where
77    S: PlanningSolution,
78    M: Move<S>,
79{
80    fn step_started(&mut self, best_score: S::Score, _last_step_score: S::Score, step_seed: u64) {
81        self.best_score = best_score;
82        self.best_move.reset(step_seed);
83        self.found_best_improving = false;
84    }
85
86    fn add_move_index(&mut self, index: CandidateId, score: S::Score) -> ForagerDecision {
87        if score > self.best_score {
88            self.found_best_improving = true;
89            return self.best_move.replace(index, score);
90        }
91        if self.found_best_improving {
92            return ForagerDecision::Release;
93        }
94        self.best_move.consider(index, score)
95    }
96
97    fn is_quit_early(&self) -> bool {
98        self.found_best_improving
99    }
100
101    fn pick_move_index(&mut self) -> Option<(CandidateId, S::Score)> {
102        self.best_move.take()
103    }
104}
105
106/// A forager that picks the first accepted move that improves on the last step's score.
107///
108/// Once a move with a score strictly better than the previous step is found, the
109/// forager quits immediately and selects that move. If no such move exists, it falls
110/// back to the best among all accepted moves.
111pub struct FirstLastStepScoreImprovingForager<S>
112where
113    S: PlanningSolution,
114{
115    last_step_score: S::Score,
116    accepted_count: usize,
117    best_move: BestCandidate<S>,
118    found_last_step_improving: bool,
119    accepted_count_limit: Option<usize>,
120    _phantom: PhantomData<fn() -> S>,
121}
122
123impl<S> FirstLastStepScoreImprovingForager<S>
124where
125    S: PlanningSolution,
126{
127    pub fn new(random_ties: bool) -> Self {
128        Self {
129            last_step_score: S::Score::zero(),
130            accepted_count: 0,
131            best_move: BestCandidate::new(random_ties),
132            found_last_step_improving: false,
133            accepted_count_limit: None,
134            _phantom: PhantomData,
135        }
136    }
137
138    pub(crate) fn with_accepted_count_limit(mut self, accepted_count_limit: usize) -> Self {
139        assert!(
140            accepted_count_limit > 0,
141            "FirstLastStepScoreImprovingForager: accepted_count_limit must be > 0, got 0"
142        );
143        self.accepted_count_limit = Some(accepted_count_limit);
144        self
145    }
146}
147
148impl<S> Default for FirstLastStepScoreImprovingForager<S>
149where
150    S: PlanningSolution,
151{
152    fn default() -> Self {
153        Self::new(true)
154    }
155}
156
157impl<S> Debug for FirstLastStepScoreImprovingForager<S>
158where
159    S: PlanningSolution,
160{
161    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
162        f.debug_struct("FirstLastStepScoreImprovingForager")
163            .field("found_last_step_improving", &self.found_last_step_improving)
164            .field("accepted_count_limit", &self.accepted_count_limit)
165            .finish()
166    }
167}
168
169impl<S> Clone for FirstLastStepScoreImprovingForager<S>
170where
171    S: PlanningSolution,
172{
173    fn clone(&self) -> Self {
174        Self {
175            last_step_score: self.last_step_score,
176            accepted_count: 0,
177            best_move: BestCandidate::new(self.best_move.random_ties()),
178            found_last_step_improving: false,
179            accepted_count_limit: self.accepted_count_limit,
180            _phantom: PhantomData,
181        }
182    }
183}
184
185impl<S, M> LocalSearchForager<S, M> for FirstLastStepScoreImprovingForager<S>
186where
187    S: PlanningSolution,
188    M: Move<S>,
189{
190    fn step_started(&mut self, _best_score: S::Score, last_step_score: S::Score, step_seed: u64) {
191        self.last_step_score = last_step_score;
192        self.accepted_count = 0;
193        self.best_move.reset(step_seed);
194        self.found_last_step_improving = false;
195    }
196
197    fn add_move_index(&mut self, index: CandidateId, score: S::Score) -> ForagerDecision {
198        if self.found_last_step_improving
199            || self
200                .accepted_count_limit
201                .is_some_and(|limit| self.accepted_count >= limit)
202        {
203            return ForagerDecision::Release;
204        }
205        self.accepted_count += 1;
206        if score > self.last_step_score {
207            self.found_last_step_improving = true;
208            return self.best_move.replace(index, score);
209        }
210        self.best_move.consider(index, score)
211    }
212
213    fn is_quit_early(&self) -> bool {
214        self.found_last_step_improving
215            || self
216                .accepted_count_limit
217                .is_some_and(|limit| self.accepted_count >= limit)
218    }
219
220    fn accepted_count_limit(&self) -> Option<usize> {
221        self.accepted_count_limit
222    }
223
224    fn pick_move_index(&mut self) -> Option<(CandidateId, S::Score)> {
225        self.best_move.take()
226    }
227}
solverforge_solver/phase/localsearch/forager/improving.rs

solverforge_solver/phase/localsearch/forager/
improving.rs
