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::ScoreDirector;
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::typed_move_selector::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    /// Get list length for an entity.
44    list_len: fn(&S, usize) -> usize,
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    /// Creates a new nearby k-opt move selector.
73    #[allow(clippy::too_many_arguments)]
74    pub fn new(
75        entity_selector: ES,
76        distance_meter: D,
77        max_nearby: usize,
78        config: KOptConfig,
79        list_len: fn(&S, usize) -> usize,
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            sublist_remove,
101            sublist_insert,
102            variable_name,
103            descriptor_index,
104            _phantom: PhantomData,
105        }
106    }
107
108    /// Finds the m nearest positions to a given position.
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    fn iter_moves<'a, SD: ScoreDirector<S>>(
140        &'a self,
141        score_director: &'a SD,
142    ) -> impl Iterator<Item = KOptMove<S, V>> + 'a {
143        let k = self.config.k;
144        let min_seg = self.config.min_segment_len;
145        let patterns = &self.patterns;
146        let list_len_fn = self.list_len;
147        let sublist_remove = self.sublist_remove;
148        let sublist_insert = self.sublist_insert;
149        let variable_name = self.variable_name;
150        let descriptor_index = self.descriptor_index;
151
152        self.entity_selector
153            .iter(score_director)
154            .flat_map(move |entity_ref| {
155                let entity_idx = entity_ref.entity_index;
156                let solution = score_director.working_solution();
157                let len = list_len_fn(solution, entity_idx);
158
159                // Generate nearby cut combinations
160                let cuts_iter = NearbyCutIterator::new(self, solution, entity_idx, k, len, min_seg);
161
162                cuts_iter.flat_map(move |cuts| {
163                    patterns.iter().map(move |&pattern| {
164                        // Validate cuts are sorted for intra-route
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                            sublist_remove,
173                            sublist_insert,
174                            variable_name,
175                            descriptor_index,
176                        )
177                    })
178                })
179            })
180    }
181
182    fn size<SD: ScoreDirector<S>>(&self, score_director: &SD) -> usize {
183        // Approximate size: n * m^(k-1) * patterns
184        let k = self.config.k;
185        let m = self.max_nearby;
186        let pattern_count = self.patterns.len();
187
188        self.entity_selector
189            .iter(score_director)
190            .map(|entity_ref| {
191                let solution = score_director.working_solution();
192                let len = (self.list_len)(solution, entity_ref.entity_index);
193                if len < (k + 1) * self.config.min_segment_len {
194                    0
195                } else {
196                    // Approximate: first cut has ~len choices, others have ~m choices
197                    len.saturating_sub(k) * m.pow((k - 1) as u32) * pattern_count
198                }
199            })
200            .sum()
201    }
202}
203
204/// Iterator for nearby k-cut combinations.
205struct NearbyCutIterator<'a, S, V, D: ListPositionDistanceMeter<S>, ES> {
206    selector: &'a NearbyKOptMoveSelector<S, V, D, ES>,
207    solution: &'a S,
208    entity_idx: usize,
209    k: usize,
210    len: usize,
211    min_seg: usize,
212    /// Stack of (position, nearby_iterator_index)
213    stack: Vec<(usize, usize)>,
214    /// Nearby positions for each level
215    nearby_cache: Vec<Vec<usize>>,
216    done: bool,
217}
218
219impl<'a, S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES>
220    NearbyCutIterator<'a, S, V, D, ES>
221{
222    fn new(
223        selector: &'a NearbyKOptMoveSelector<S, V, D, ES>,
224        solution: &'a S,
225        entity_idx: usize,
226        k: usize,
227        len: usize,
228        min_seg: usize,
229    ) -> Self {
230        let min_len = (k + 1) * min_seg;
231        if len < min_len {
232            return Self {
233                selector,
234                solution,
235                entity_idx,
236                k,
237                len,
238                min_seg,
239                stack: vec![],
240                nearby_cache: vec![],
241                done: true,
242            };
243        }
244
245        // Start with first valid position
246        let mut iter = Self {
247            selector,
248            solution,
249            entity_idx,
250            k,
251            len,
252            min_seg,
253            stack: vec![(min_seg, 0)],
254            nearby_cache: vec![vec![]],
255            done: false,
256        };
257
258        // Build initial stack to depth k
259        iter.extend_stack();
260        iter
261    }
262
263    fn extend_stack(&mut self) {
264        while self.stack.len() < self.k && !self.done {
265            let (last_pos, _) = *self.stack.last().unwrap();
266
267            // Get nearby positions for next cut
268            let nearby =
269                self.selector
270                    .nearby_positions(self.solution, self.entity_idx, last_pos, self.len);
271
272            // Filter to valid positions (must leave room for remaining cuts)
273            let remaining_cuts = self.k - self.stack.len();
274            let min_pos = last_pos + self.min_seg;
275            let max_pos = self.len - self.min_seg * remaining_cuts;
276
277            let valid: Vec<usize> = nearby
278                .into_iter()
279                .filter(|&p| p >= min_pos && p <= max_pos)
280                .collect();
281
282            if valid.is_empty() {
283                // No valid positions, backtrack
284                if !self.backtrack() {
285                    self.done = true;
286                    return;
287                }
288            } else {
289                self.nearby_cache.push(valid);
290                let next_pos = self.nearby_cache.last().unwrap()[0];
291                self.stack.push((next_pos, 0));
292            }
293        }
294    }
295
296    fn backtrack(&mut self) -> bool {
297        while let Some((popped_pos, _idx)) = self.stack.pop() {
298            self.nearby_cache.pop();
299
300            if let Some((_, last_idx)) = self.stack.last_mut() {
301                let cache_idx = self.nearby_cache.len();
302                if cache_idx > 0 {
303                    let cache = &self.nearby_cache[cache_idx - 1];
304                    let next_idx = *last_idx + 1;
305                    if next_idx < cache.len() {
306                        *last_idx = next_idx;
307                        let (pos, _) = self.stack.last().unwrap();
308                        let new_pos = cache[next_idx];
309                        if new_pos > *pos {
310                            self.stack.pop();
311                            self.stack.push((new_pos, next_idx));
312                            return true;
313                        }
314                    }
315                }
316            } else {
317                // Stack is empty - use the popped position to find next first position
318                let next_first = popped_pos + 1;
319                let max_first = self.len - self.min_seg * self.k;
320                if next_first <= max_first {
321                    self.stack.push((next_first, 0));
322                    self.nearby_cache.push(vec![]);
323                    return true;
324                }
325            }
326        }
327        false
328    }
329
330    fn advance(&mut self) {
331        if self.done || self.stack.is_empty() {
332            self.done = true;
333            return;
334        }
335
336        // Try to advance at current depth
337        if let Some((_, idx)) = self.stack.last_mut() {
338            let cache_idx = self.nearby_cache.len() - 1;
339            let cache = &self.nearby_cache[cache_idx];
340            let next_idx = *idx + 1;
341            if next_idx < cache.len() {
342                *idx = next_idx;
343                let new_pos = cache[next_idx];
344                self.stack.pop();
345                self.stack.push((new_pos, next_idx));
346                return;
347            }
348        }
349
350        // Backtrack and extend
351        if self.backtrack() {
352            self.extend_stack();
353        } else {
354            self.done = true;
355        }
356    }
357}
358
359impl<'a, S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES> Iterator
360    for NearbyCutIterator<'a, S, V, D, ES>
361{
362    type Item = Vec<CutPoint>;
363
364    fn next(&mut self) -> Option<Self::Item> {
365        if self.done || self.stack.len() != self.k {
366            return None;
367        }
368
369        let cuts: Vec<CutPoint> = self
370            .stack
371            .iter()
372            .map(|(pos, _)| CutPoint::new(self.entity_idx, *pos))
373            .collect();
374
375        self.advance();
376
377        Some(cuts)
378    }
379}
solverforge_solver/heuristic/selector/k_opt/nearby.rs

solverforge_solver/heuristic/selector/k_opt/
nearby.rs
