solverforge_solver/phase/construction/
forager.rs

1//! Foragers for construction heuristic move selection
2//!
3//! Foragers determine which move to select from the candidates
4//! generated for each entity placement.
5//!
6//! # Zero-Erasure Design
7//!
8//! Foragers return indices into the placement's move Vec, not cloned moves.
9//! The caller takes ownership via the index.
10
11use std::fmt::Debug;
12use std::marker::PhantomData;
13
14use solverforge_core::domain::PlanningSolution;
15use solverforge_core::score::Score;
16use solverforge_scoring::{RecordingScoreDirector, ScoreDirector};
17
18use crate::heuristic::r#move::Move;
19
20use super::Placement;
21
22/// Trait for selecting a move during construction.
23///
24/// Foragers evaluate candidate moves and pick one based on their strategy.
25/// Returns the index of the selected move, not a cloned move.
26///
27/// # Type Parameters
28/// * `S` - The planning solution type
29/// * `M` - The move type
30pub trait ConstructionForager<S, M>: Send + Debug
31where
32    S: PlanningSolution,
33    M: Move<S>,
34{
35    /// Picks a move index from the placement's candidates.
36    ///
37    /// Returns None if no suitable move is found.
38    fn pick_move_index<D: ScoreDirector<S>>(
39        &self,
40        placement: &Placement<S, M>,
41        score_director: &mut D,
42    ) -> Option<usize>;
43}
44
45/// First Fit forager - picks the first feasible move.
46///
47/// This is the fastest forager but may not produce optimal results.
48/// It simply takes the first move that can be executed.
49pub struct FirstFitForager<S, M> {
50    _phantom: PhantomData<fn() -> (S, M)>,
51}
52
53impl<S, M> Clone for FirstFitForager<S, M> {
54    fn clone(&self) -> Self {
55        *self
56    }
57}
58
59impl<S, M> Copy for FirstFitForager<S, M> {}
60
61impl<S, M> Default for FirstFitForager<S, M> {
62    fn default() -> Self {
63        Self::new()
64    }
65}
66
67impl<S, M> Debug for FirstFitForager<S, M> {
68    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
69        f.debug_struct("FirstFitForager").finish()
70    }
71}
72
73impl<S, M> FirstFitForager<S, M> {
74    /// Creates a new First Fit forager.
75    pub fn new() -> Self {
76        Self {
77            _phantom: PhantomData,
78        }
79    }
80}
81
82impl<S, M> ConstructionForager<S, M> for FirstFitForager<S, M>
83where
84    S: PlanningSolution,
85    M: Move<S>,
86{
87    fn pick_move_index<D: ScoreDirector<S>>(
88        &self,
89        placement: &Placement<S, M>,
90        score_director: &mut D,
91    ) -> Option<usize> {
92        for (idx, m) in placement.moves.iter().enumerate() {
93            if m.is_doable(score_director) {
94                return Some(idx);
95            }
96        }
97        None
98    }
99}
100
101/// Best Fit forager - evaluates all moves and picks the best.
102///
103/// This forager evaluates each candidate move by executing it,
104/// calculating the score, and undoing it. The move with the best
105/// score is selected.
106pub struct BestFitForager<S, M> {
107    _phantom: PhantomData<fn() -> (S, M)>,
108}
109
110impl<S, M> Clone for BestFitForager<S, M> {
111    fn clone(&self) -> Self {
112        *self
113    }
114}
115
116impl<S, M> Copy for BestFitForager<S, M> {}
117
118impl<S, M> Default for BestFitForager<S, M> {
119    fn default() -> Self {
120        Self::new()
121    }
122}
123
124impl<S, M> Debug for BestFitForager<S, M> {
125    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
126        f.debug_struct("BestFitForager").finish()
127    }
128}
129
130impl<S, M> BestFitForager<S, M> {
131    /// Creates a new Best Fit forager.
132    pub fn new() -> Self {
133        Self {
134            _phantom: PhantomData,
135        }
136    }
137}
138
139impl<S, M> ConstructionForager<S, M> for BestFitForager<S, M>
140where
141    S: PlanningSolution,
142    M: Move<S>,
143{
144    fn pick_move_index<D: ScoreDirector<S>>(
145        &self,
146        placement: &Placement<S, M>,
147        score_director: &mut D,
148    ) -> Option<usize> {
149        let mut best_idx: Option<usize> = None;
150        let mut best_score: Option<S::Score> = None;
151
152        for (idx, m) in placement.moves.iter().enumerate() {
153            if !m.is_doable(score_director) {
154                continue;
155            }
156
157            // Use RecordingScoreDirector for automatic undo
158            let score = {
159                let mut recording = RecordingScoreDirector::new(score_director);
160
161                // Execute move
162                m.do_move(&mut recording);
163
164                // Evaluate
165                let score = recording.calculate_score();
166
167                // Undo move
168                recording.undo_changes();
169
170                score
171            };
172
173            // Check if this is the best so far
174            let is_better = match &best_score {
175                None => true,
176                Some(best) => score > *best,
177            };
178
179            if is_better {
180                best_idx = Some(idx);
181                best_score = Some(score);
182            }
183        }
184
185        best_idx
186    }
187}
188
189/// First Feasible forager - picks the first move that results in a feasible score.
190///
191/// This forager evaluates moves until it finds one that produces a feasible
192/// (non-negative hard score) solution.
193pub struct FirstFeasibleForager<S, M> {
194    _phantom: PhantomData<fn() -> (S, M)>,
195}
196
197impl<S, M> Clone for FirstFeasibleForager<S, M> {
198    fn clone(&self) -> Self {
199        *self
200    }
201}
202
203impl<S, M> Copy for FirstFeasibleForager<S, M> {}
204
205impl<S, M> Default for FirstFeasibleForager<S, M> {
206    fn default() -> Self {
207        Self::new()
208    }
209}
210
211impl<S, M> Debug for FirstFeasibleForager<S, M> {
212    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
213        f.debug_struct("FirstFeasibleForager").finish()
214    }
215}
216
217impl<S, M> FirstFeasibleForager<S, M> {
218    /// Creates a new First Feasible forager.
219    pub fn new() -> Self {
220        Self {
221            _phantom: PhantomData,
222        }
223    }
224}
225
226impl<S, M> ConstructionForager<S, M> for FirstFeasibleForager<S, M>
227where
228    S: PlanningSolution,
229    M: Move<S>,
230{
231    fn pick_move_index<D: ScoreDirector<S>>(
232        &self,
233        placement: &Placement<S, M>,
234        score_director: &mut D,
235    ) -> Option<usize> {
236        let mut fallback_idx: Option<usize> = None;
237        let mut fallback_score: Option<S::Score> = None;
238
239        for (idx, m) in placement.moves.iter().enumerate() {
240            if !m.is_doable(score_director) {
241                continue;
242            }
243
244            // Use RecordingScoreDirector for automatic undo
245            let score = {
246                let mut recording = RecordingScoreDirector::new(score_director);
247
248                // Execute move
249                m.do_move(&mut recording);
250
251                // Evaluate
252                let score = recording.calculate_score();
253
254                // If feasible, return this move index immediately
255                if score.is_feasible() {
256                    recording.undo_changes();
257                    return Some(idx);
258                }
259
260                // Undo move
261                recording.undo_changes();
262
263                score
264            };
265
266            // Track best infeasible as fallback
267            let is_better = match &fallback_score {
268                None => true,
269                Some(best) => score > *best,
270            };
271
272            if is_better {
273                fallback_idx = Some(idx);
274                fallback_score = Some(score);
275            }
276        }
277
278        // No feasible move found, return best infeasible
279        fallback_idx
280    }
281}
282
283/// Weakest Fit forager - picks the move with the lowest strength value.
284///
285/// This forager evaluates each candidate move using a strength function
286/// and selects the move with the minimum strength. This is useful for
287/// assigning the "weakest" or least constraining values first.
288pub struct WeakestFitForager<S, M> {
289    /// Function to evaluate strength of a move.
290    strength_fn: fn(&M) -> i64,
291    _phantom: PhantomData<fn() -> S>,
292}
293
294impl<S, M> Clone for WeakestFitForager<S, M> {
295    fn clone(&self) -> Self {
296        *self
297    }
298}
299
300impl<S, M> Copy for WeakestFitForager<S, M> {}
301
302impl<S, M> Debug for WeakestFitForager<S, M> {
303    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
304        f.debug_struct("WeakestFitForager").finish()
305    }
306}
307
308impl<S, M> WeakestFitForager<S, M> {
309    /// Creates a new Weakest Fit forager with the given strength function.
310    ///
311    /// The strength function evaluates how "strong" a move is. The forager
312    /// picks the move with the minimum strength value.
313    pub fn new(strength_fn: fn(&M) -> i64) -> Self {
314        Self {
315            strength_fn,
316            _phantom: PhantomData,
317        }
318    }
319}
320
321impl<S, M> ConstructionForager<S, M> for WeakestFitForager<S, M>
322where
323    S: PlanningSolution,
324    M: Move<S>,
325{
326    fn pick_move_index<D: ScoreDirector<S>>(
327        &self,
328        placement: &Placement<S, M>,
329        score_director: &mut D,
330    ) -> Option<usize> {
331        let mut best_idx: Option<usize> = None;
332        let mut min_strength: Option<i64> = None;
333
334        for (idx, m) in placement.moves.iter().enumerate() {
335            if !m.is_doable(score_director) {
336                continue;
337            }
338
339            let strength = (self.strength_fn)(m);
340
341            let is_weaker = match min_strength {
342                None => true,
343                Some(best) => strength < best,
344            };
345
346            if is_weaker {
347                best_idx = Some(idx);
348                min_strength = Some(strength);
349            }
350        }
351
352        best_idx
353    }
354}
355
356/// Strongest Fit forager - picks the move with the highest strength value.
357///
358/// This forager evaluates each candidate move using a strength function
359/// and selects the move with the maximum strength. This is useful for
360/// assigning the "strongest" or most constraining values first.
361pub struct StrongestFitForager<S, M> {
362    /// Function to evaluate strength of a move.
363    strength_fn: fn(&M) -> i64,
364    _phantom: PhantomData<fn() -> S>,
365}
366
367impl<S, M> Clone for StrongestFitForager<S, M> {
368    fn clone(&self) -> Self {
369        *self
370    }
371}
372
373impl<S, M> Copy for StrongestFitForager<S, M> {}
374
375impl<S, M> Debug for StrongestFitForager<S, M> {
376    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
377        f.debug_struct("StrongestFitForager").finish()
378    }
379}
380
381impl<S, M> StrongestFitForager<S, M> {
382    /// Creates a new Strongest Fit forager with the given strength function.
383    ///
384    /// The strength function evaluates how "strong" a move is. The forager
385    /// picks the move with the maximum strength value.
386    pub fn new(strength_fn: fn(&M) -> i64) -> Self {
387        Self {
388            strength_fn,
389            _phantom: PhantomData,
390        }
391    }
392}
393
394impl<S, M> ConstructionForager<S, M> for StrongestFitForager<S, M>
395where
396    S: PlanningSolution,
397    M: Move<S>,
398{
399    fn pick_move_index<D: ScoreDirector<S>>(
400        &self,
401        placement: &Placement<S, M>,
402        score_director: &mut D,
403    ) -> Option<usize> {
404        let mut best_idx: Option<usize> = None;
405        let mut max_strength: Option<i64> = None;
406
407        for (idx, m) in placement.moves.iter().enumerate() {
408            if !m.is_doable(score_director) {
409                continue;
410            }
411
412            let strength = (self.strength_fn)(m);
413
414            let is_stronger = match max_strength {
415                None => true,
416                Some(best) => strength > best,
417            };
418
419            if is_stronger {
420                best_idx = Some(idx);
421                max_strength = Some(strength);
422            }
423        }
424
425        best_idx
426    }
427}
428
429#[cfg(test)]
430#[path = "forager_tests.rs"]
431mod tests;
solverforge_solver/phase/construction/forager.rs

solverforge_solver/phase/construction/
forager.rs
