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

solverforge_solver/heuristic/selector/k_opt/
nearby.rs
