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

solverforge_solver/phase/localsearch/forager/
improving.rs
