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::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    accepted_moves: Vec<(CandidateId, S::Score)>,
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() -> Self {
32        Self {
33            best_score: S::Score::zero(),
34            accepted_moves: Vec::new(),
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()
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            accepted_moves: Vec::new(),
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) {
81        self.best_score = best_score;
82        self.accepted_moves.clear();
83        self.found_best_improving = false;
84    }
85
86    fn add_move_index(&mut self, index: CandidateId, score: S::Score) {
87        if score > self.best_score {
88            self.accepted_moves.clear();
89            self.accepted_moves.push((index, score));
90            self.found_best_improving = true;
91        } else if !self.found_best_improving {
92            self.accepted_moves.push((index, score));
93        }
94    }
95
96    fn is_quit_early(&self) -> bool {
97        self.found_best_improving
98    }
99
100    fn pick_move_index(&mut self) -> Option<(CandidateId, S::Score)> {
101        if self.accepted_moves.is_empty() {
102            return None;
103        }
104        if self.found_best_improving {
105            return self.accepted_moves.pop();
106        }
107
108        let mut best_idx = 0;
109        let mut best_score = self.accepted_moves[0].1;
110        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
111            if score > best_score {
112                best_idx = i;
113                best_score = score;
114            }
115        }
116        Some(self.accepted_moves.swap_remove(best_idx))
117    }
118}
119
120/// A forager that picks the first accepted move that improves on the last step's score.
121///
122/// Once a move with a score strictly better than the previous step is found, the
123/// forager quits immediately and selects that move. If no such move exists, it falls
124/// back to the best among all accepted moves.
125pub struct FirstLastStepScoreImprovingForager<S>
126where
127    S: PlanningSolution,
128{
129    last_step_score: S::Score,
130    accepted_moves: Vec<(CandidateId, S::Score)>,
131    found_last_step_improving: bool,
132    accepted_count_limit: Option<usize>,
133    _phantom: PhantomData<fn() -> S>,
134}
135
136impl<S> FirstLastStepScoreImprovingForager<S>
137where
138    S: PlanningSolution,
139{
140    pub fn new() -> Self {
141        Self {
142            last_step_score: S::Score::zero(),
143            accepted_moves: Vec::new(),
144            found_last_step_improving: false,
145            accepted_count_limit: None,
146            _phantom: PhantomData,
147        }
148    }
149
150    pub(crate) fn with_accepted_count_limit(mut self, accepted_count_limit: usize) -> Self {
151        assert!(
152            accepted_count_limit > 0,
153            "FirstLastStepScoreImprovingForager: accepted_count_limit must be > 0, got 0"
154        );
155        self.accepted_count_limit = Some(accepted_count_limit);
156        self
157    }
158}
159
160impl<S> Default for FirstLastStepScoreImprovingForager<S>
161where
162    S: PlanningSolution,
163{
164    fn default() -> Self {
165        Self::new()
166    }
167}
168
169impl<S> Debug for FirstLastStepScoreImprovingForager<S>
170where
171    S: PlanningSolution,
172{
173    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
174        f.debug_struct("FirstLastStepScoreImprovingForager")
175            .field("found_last_step_improving", &self.found_last_step_improving)
176            .field("accepted_count_limit", &self.accepted_count_limit)
177            .finish()
178    }
179}
180
181impl<S> Clone for FirstLastStepScoreImprovingForager<S>
182where
183    S: PlanningSolution,
184{
185    fn clone(&self) -> Self {
186        Self {
187            last_step_score: self.last_step_score,
188            accepted_moves: Vec::new(),
189            found_last_step_improving: false,
190            accepted_count_limit: self.accepted_count_limit,
191            _phantom: PhantomData,
192        }
193    }
194}
195
196impl<S, M> LocalSearchForager<S, M> for FirstLastStepScoreImprovingForager<S>
197where
198    S: PlanningSolution,
199    M: Move<S>,
200{
201    fn step_started(&mut self, _best_score: S::Score, last_step_score: S::Score) {
202        self.last_step_score = last_step_score;
203        self.accepted_moves.clear();
204        self.found_last_step_improving = false;
205    }
206
207    fn add_move_index(&mut self, index: CandidateId, score: S::Score) {
208        if self.found_last_step_improving
209            || self
210                .accepted_count_limit
211                .is_some_and(|limit| self.accepted_moves.len() >= limit)
212        {
213            return;
214        }
215        if score > self.last_step_score {
216            self.accepted_moves.clear();
217            self.accepted_moves.push((index, score));
218            self.found_last_step_improving = true;
219        } else if !self.found_last_step_improving {
220            self.accepted_moves.push((index, score));
221        }
222    }
223
224    fn is_quit_early(&self) -> bool {
225        self.found_last_step_improving
226            || self
227                .accepted_count_limit
228                .is_some_and(|limit| self.accepted_moves.len() >= limit)
229    }
230
231    fn accepted_count_limit(&self) -> Option<usize> {
232        self.accepted_count_limit
233    }
234
235    fn pick_move_index(&mut self) -> Option<(CandidateId, S::Score)> {
236        if self.accepted_moves.is_empty() {
237            return None;
238        }
239        if self.found_last_step_improving {
240            return self.accepted_moves.pop();
241        }
242
243        let mut best_idx = 0;
244        let mut best_score = self.accepted_moves[0].1;
245        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
246            if score > best_score {
247                best_idx = i;
248                best_score = score;
249            }
250        }
251        Some(self.accepted_moves.swap_remove(best_idx))
252    }
253}
solverforge_solver/phase/localsearch/forager/improving.rs

solverforge_solver/phase/localsearch/forager/
improving.rs
