solverforge_solver/heuristic/selector/k_opt/
nearby.rs

1// Nearby k-opt move selector for improved performance.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::Director;
8
9use crate::heuristic::r#move::k_opt_reconnection::{
10    enumerate_reconnections, KOptReconnection, THREE_OPT_RECONNECTIONS,
11};
12use crate::heuristic::r#move::{CutPoint, KOptMove};
13
14use super::super::entity::EntitySelector;
15use super::super::move_selector::{ArenaMoveCursor, MoveSelector};
16use super::config::KOptConfig;
17use super::distance_meter::ListPositionDistanceMeter;
18
19/// A k-opt move selector with nearby selection for improved performance.
20///
21/// Instead of enumerating all O(n^k) cut combinations, uses distance-based
22/// pruning to reduce to O(n * m^(k-1)) where m = max_nearby_size.
23///
24/// # How It Works
25///
26/// 1. First cut: all positions in the route
27/// 2. Second cut: only positions nearby (by element distance) to first cut
28/// 3. Third cut: only positions nearby to second cut
29/// 4. etc.
30///
31/// This dramatically reduces the search space for large routes.
32pub struct NearbyKOptMoveSelector<S, V, D: ListPositionDistanceMeter<S>, ES> {
33    // Selects entities (routes) to apply k-opt to.
34    entity_selector: ES,
35    // Distance meter for nearby selection.
36    distance_meter: D,
37    // Maximum nearby positions to consider.
38    max_nearby: usize,
39    // K-opt configuration.
40    config: KOptConfig,
41    // Reconnection patterns.
42    patterns: Vec<&'static KOptReconnection>,
43    list_len: fn(&S, usize) -> usize,
44    list_get: fn(&S, usize, usize) -> Option<V>,
45    // Remove sublist.
46    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
47    // Insert sublist.
48    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
49    // Variable name.
50    variable_name: &'static str,
51    // Descriptor index.
52    descriptor_index: usize,
53    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
54}
55
56impl<S, V: Debug, D: ListPositionDistanceMeter<S>, ES: Debug> Debug
57    for NearbyKOptMoveSelector<S, V, D, ES>
58{
59    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
60        f.debug_struct("NearbyKOptMoveSelector")
61            .field("entity_selector", &self.entity_selector)
62            .field("max_nearby", &self.max_nearby)
63            .field("config", &self.config)
64            .field("pattern_count", &self.patterns.len())
65            .finish()
66    }
67}
68
69impl<S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES>
70    NearbyKOptMoveSelector<S, V, D, ES>
71{
72    #[allow(clippy::too_many_arguments)]
73    pub fn new(
74        entity_selector: ES,
75        distance_meter: D,
76        max_nearby: usize,
77        config: KOptConfig,
78        list_len: fn(&S, usize) -> usize,
79        list_get: fn(&S, usize, usize) -> Option<V>,
80        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
81        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
82        variable_name: &'static str,
83        descriptor_index: usize,
84    ) -> Self {
85        let patterns: Vec<&'static KOptReconnection> = if config.k == 3 {
86            THREE_OPT_RECONNECTIONS.iter().collect()
87        } else {
88            let generated = enumerate_reconnections(config.k);
89            let leaked: &'static [KOptReconnection] = Box::leak(generated.into_boxed_slice());
90            leaked.iter().collect()
91        };
92
93        Self {
94            entity_selector,
95            distance_meter,
96            max_nearby,
97            config,
98            patterns,
99            list_len,
100            list_get,
101            sublist_remove,
102            sublist_insert,
103            variable_name,
104            descriptor_index,
105            _phantom: PhantomData,
106        }
107    }
108
109    fn nearby_positions(
110        &self,
111        solution: &S,
112        entity_idx: usize,
113        origin: usize,
114        len: usize,
115    ) -> Vec<usize> {
116        let mut positions: Vec<(usize, f64)> = (0..len)
117            .filter(|&p| p != origin)
118            .map(|p| {
119                let dist = self
120                    .distance_meter
121                    .distance(solution, entity_idx, origin, p);
122                (p, dist)
123            })
124            .collect();
125
126        positions.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
127        positions.truncate(self.max_nearby);
128        positions.into_iter().map(|(p, _)| p).collect()
129    }
130}
131
132impl<S, V, DM, ES> MoveSelector<S, KOptMove<S, V>> for NearbyKOptMoveSelector<S, V, DM, ES>
133where
134    S: PlanningSolution,
135    V: Clone + Send + Sync + Debug + 'static,
136    DM: ListPositionDistanceMeter<S> + 'static,
137    ES: EntitySelector<S>,
138{
139    type Cursor<'a>
140        = ArenaMoveCursor<S, KOptMove<S, V>>
141    where
142        Self: 'a;
143
144    fn open_cursor<'a, SD: Director<S>>(&'a self, score_director: &SD) -> Self::Cursor<'a> {
145        let k = self.config.k;
146        let min_seg = self.config.min_segment_len;
147        let patterns = &self.patterns;
148        let list_len_fn = self.list_len;
149        let list_get = self.list_get;
150        let sublist_remove = self.sublist_remove;
151        let sublist_insert = self.sublist_insert;
152        let variable_name = self.variable_name;
153        let descriptor_index = self.descriptor_index;
154        let solution = score_director.working_solution();
155        let moves: Vec<_> = self
156            .entity_selector
157            .iter(score_director)
158            .flat_map(move |entity_ref| {
159                let entity_idx = entity_ref.entity_index;
160                let len = list_len_fn(solution, entity_idx);
161                let cuts_iter = NearbyCutIterator::new(self, solution, entity_idx, k, len, min_seg);
162
163                cuts_iter.flat_map(move |cuts| {
164                    patterns.iter().map(move |&pattern| {
165                        let mut sorted_cuts = cuts.clone();
166                        sorted_cuts.sort_by_key(|c| c.position());
167
168                        KOptMove::new(
169                            &sorted_cuts,
170                            pattern,
171                            list_len_fn,
172                            list_get,
173                            sublist_remove,
174                            sublist_insert,
175                            variable_name,
176                            descriptor_index,
177                        )
178                    })
179                })
180            })
181            .collect();
182        ArenaMoveCursor::from_moves(moves)
183    }
184
185    fn size<SD: Director<S>>(&self, score_director: &SD) -> usize {
186        // Approximate size: n * m^(k-1) * patterns
187        let k = self.config.k;
188        let m = self.max_nearby;
189        let pattern_count = self.patterns.len();
190
191        self.entity_selector
192            .iter(score_director)
193            .map(|entity_ref| {
194                let solution = score_director.working_solution();
195                let len = (self.list_len)(solution, entity_ref.entity_index);
196                if len < (k + 1) * self.config.min_segment_len {
197                    0
198                } else {
199                    // Approximate: first cut has ~len choices, others have ~m choices
200                    len.saturating_sub(k) * m.pow((k - 1) as u32) * pattern_count
201                }
202            })
203            .sum()
204    }
205}
206
207// Iterator for nearby k-cut combinations.
208struct NearbyCutIterator<'a, S, V, D: ListPositionDistanceMeter<S>, ES> {
209    selector: &'a NearbyKOptMoveSelector<S, V, D, ES>,
210    solution: &'a S,
211    entity_idx: usize,
212    k: usize,
213    len: usize,
214    min_seg: usize,
215    // Stack of (position, nearby_iterator_index)
216    stack: Vec<(usize, usize)>,
217    // Nearby positions for each level
218    nearby_cache: Vec<Vec<usize>>,
219    done: bool,
220}
221
222impl<'a, S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES>
223    NearbyCutIterator<'a, S, V, D, ES>
224{
225    fn new(
226        selector: &'a NearbyKOptMoveSelector<S, V, D, ES>,
227        solution: &'a S,
228        entity_idx: usize,
229        k: usize,
230        len: usize,
231        min_seg: usize,
232    ) -> Self {
233        let min_len = (k + 1) * min_seg;
234        if len < min_len {
235            return Self {
236                selector,
237                solution,
238                entity_idx,
239                k,
240                len,
241                min_seg,
242                stack: vec![],
243                nearby_cache: vec![],
244                done: true,
245            };
246        }
247
248        // Start with first valid position
249        let mut iter = Self {
250            selector,
251            solution,
252            entity_idx,
253            k,
254            len,
255            min_seg,
256            stack: vec![(min_seg, 0)],
257            nearby_cache: vec![vec![]],
258            done: false,
259        };
260
261        // Build initial stack to depth k
262        iter.extend_stack();
263        iter
264    }
265
266    fn extend_stack(&mut self) {
267        while self.stack.len() < self.k && !self.done {
268            let (last_pos, _) = *self.stack.last().unwrap();
269
270            // Get nearby positions for next cut
271            let nearby =
272                self.selector
273                    .nearby_positions(self.solution, self.entity_idx, last_pos, self.len);
274
275            // Filter to valid positions (must leave room for remaining cuts)
276            let remaining_cuts = self.k - self.stack.len();
277            let min_pos = last_pos + self.min_seg;
278            let max_pos = self.len - self.min_seg * remaining_cuts;
279
280            let valid: Vec<usize> = nearby
281                .into_iter()
282                .filter(|&p| p >= min_pos && p <= max_pos)
283                .collect();
284
285            if valid.is_empty() {
286                // No valid positions, backtrack
287                if !self.backtrack() {
288                    self.done = true;
289                    return;
290                }
291            } else {
292                self.nearby_cache.push(valid);
293                let next_pos = self.nearby_cache.last().unwrap()[0];
294                self.stack.push((next_pos, 0));
295            }
296        }
297    }
298
299    fn backtrack(&mut self) -> bool {
300        while let Some((popped_pos, _idx)) = self.stack.pop() {
301            self.nearby_cache.pop();
302
303            if let Some((_, last_idx)) = self.stack.last_mut() {
304                let cache_idx = self.nearby_cache.len();
305                if cache_idx > 0 {
306                    let cache = &self.nearby_cache[cache_idx - 1];
307                    let next_idx = *last_idx + 1;
308                    if next_idx < cache.len() {
309                        *last_idx = next_idx;
310                        let (pos, _) = self.stack.last().unwrap();
311                        let new_pos = cache[next_idx];
312                        if new_pos > *pos {
313                            self.stack.pop();
314                            self.stack.push((new_pos, next_idx));
315                            return true;
316                        }
317                    }
318                }
319            } else {
320                // Stack is empty - use the popped position to find next first position
321                let next_first = popped_pos + 1;
322                let max_first = self.len - self.min_seg * self.k;
323                if next_first <= max_first {
324                    self.stack.push((next_first, 0));
325                    self.nearby_cache.push(vec![]);
326                    return true;
327                }
328            }
329        }
330        false
331    }
332
333    fn advance(&mut self) {
334        if self.done || self.stack.is_empty() {
335            self.done = true;
336            return;
337        }
338
339        // Try to advance at current depth
340        if let Some((_, idx)) = self.stack.last_mut() {
341            let cache_idx = self.nearby_cache.len() - 1;
342            let cache = &self.nearby_cache[cache_idx];
343            let next_idx = *idx + 1;
344            if next_idx < cache.len() {
345                *idx = next_idx;
346                let new_pos = cache[next_idx];
347                self.stack.pop();
348                self.stack.push((new_pos, next_idx));
349                return;
350            }
351        }
352
353        // Backtrack and extend
354        if self.backtrack() {
355            self.extend_stack();
356        } else {
357            self.done = true;
358        }
359    }
360}
361
362impl<'a, S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES> Iterator
363    for NearbyCutIterator<'a, S, V, D, ES>
364{
365    type Item = Vec<CutPoint>;
366
367    fn next(&mut self) -> Option<Self::Item> {
368        if self.done || self.stack.len() != self.k {
369            return None;
370        }
371
372        let cuts: Vec<CutPoint> = self
373            .stack
374            .iter()
375            .map(|(pos, _)| CutPoint::new(self.entity_idx, *pos))
376            .collect();
377
378        self.advance();
379
380        Some(cuts)
381    }
382}
solverforge_solver/heuristic/selector/k_opt/nearby.rs

solverforge_solver/heuristic/selector/k_opt/
nearby.rs
