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    _phantom: PhantomData<fn() -> S>,
133}
134
135impl<S> FirstLastStepScoreImprovingForager<S>
136where
137    S: PlanningSolution,
138{
139    pub fn new() -> Self {
140        Self {
141            last_step_score: S::Score::zero(),
142            accepted_moves: Vec::new(),
143            found_last_step_improving: false,
144            _phantom: PhantomData,
145        }
146    }
147}
148
149impl<S> Default for FirstLastStepScoreImprovingForager<S>
150where
151    S: PlanningSolution,
152{
153    fn default() -> Self {
154        Self::new()
155    }
156}
157
158impl<S> Debug for FirstLastStepScoreImprovingForager<S>
159where
160    S: PlanningSolution,
161{
162    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
163        f.debug_struct("FirstLastStepScoreImprovingForager")
164            .field("found_last_step_improving", &self.found_last_step_improving)
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_moves: Vec::new(),
177            found_last_step_improving: false,
178            _phantom: PhantomData,
179        }
180    }
181}
182
183impl<S, M> LocalSearchForager<S, M> for FirstLastStepScoreImprovingForager<S>
184where
185    S: PlanningSolution,
186    M: Move<S>,
187{
188    fn step_started(&mut self, _best_score: S::Score, last_step_score: S::Score) {
189        self.last_step_score = last_step_score;
190        self.accepted_moves.clear();
191        self.found_last_step_improving = false;
192    }
193
194    fn add_move_index(&mut self, index: CandidateId, score: S::Score) {
195        if score > self.last_step_score {
196            self.accepted_moves.clear();
197            self.accepted_moves.push((index, score));
198            self.found_last_step_improving = true;
199        } else if !self.found_last_step_improving {
200            self.accepted_moves.push((index, score));
201        }
202    }
203
204    fn is_quit_early(&self) -> bool {
205        self.found_last_step_improving
206    }
207
208    fn pick_move_index(&mut self) -> Option<(CandidateId, S::Score)> {
209        if self.accepted_moves.is_empty() {
210            return None;
211        }
212        if self.found_last_step_improving {
213            return self.accepted_moves.pop();
214        }
215
216        let mut best_idx = 0;
217        let mut best_score = self.accepted_moves[0].1;
218        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
219            if score > best_score {
220                best_idx = i;
221                best_score = score;
222            }
223        }
224        Some(self.accepted_moves.swap_remove(best_idx))
225    }
226}
solverforge_solver/phase/localsearch/forager/improving.rs

solverforge_solver/phase/localsearch/forager/
improving.rs
