solverforge_solver/heuristic/selector/k_opt/
mod.rs

1//! K-opt move selector for tour optimization.
2//!
3//! Generates k-opt moves by enumerating all valid cut point combinations
4//! within selected entities and applying reconnection patterns.
5//!
6//! # Complexity
7//!
8//! For a route of length n and k-opt:
9//! - Full enumeration: O(n^k) cut combinations × reconnection patterns
10//! - Use `NearbyKOptMoveSelector` to reduce to O(n × m^(k-1)) with nearby selection
11//!
12//! # Example
13//!
14//! ```
15//! use solverforge_solver::heuristic::selector::k_opt::{KOptMoveSelector, KOptConfig};
16//! use solverforge_solver::heuristic::selector::entity::FromSolutionEntitySelector;
17//! use solverforge_core::domain::PlanningSolution;
18//! use solverforge_core::score::SimpleScore;
19//!
20//! #[derive(Clone, Debug)]
21//! struct Tour { cities: Vec<i32>, score: Option<SimpleScore> }
22//!
23//! impl PlanningSolution for Tour {
24//!     type Score = SimpleScore;
25//!     fn score(&self) -> Option<Self::Score> { self.score }
26//!     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
27//! }
28//!
29//! fn list_len(s: &Tour, _: usize) -> usize { s.cities.len() }
30//! fn sublist_remove(s: &mut Tour, _: usize, start: usize, end: usize) -> Vec<i32> {
31//!     s.cities.drain(start..end).collect()
32//! }
33//! fn sublist_insert(s: &mut Tour, _: usize, pos: usize, items: Vec<i32>) {
34//!     for (i, item) in items.into_iter().enumerate() {
35//!         s.cities.insert(pos + i, item);
36//!     }
37//! }
38//!
39//! let config = KOptConfig::new(3); // 3-opt
40//!
41//! let selector = KOptMoveSelector::<Tour, i32, _>::new(
42//!     FromSolutionEntitySelector::new(0),
43//!     config,
44//!     list_len,
45//!     sublist_remove,
46//!     sublist_insert,
47//!     "cities",
48//!     0,
49//! );
50//! ```
51
52mod config;
53mod distance_meter;
54mod iterators;
55mod nearby;
56mod selector;
57#[cfg(test)]
58mod tests;
59
60pub use config::KOptConfig;
61pub use distance_meter::{DefaultDistanceMeter, ListPositionDistanceMeter};
62pub use iterators::{binomial, count_cut_combinations, CutCombinationIterator};
63pub use nearby::NearbyKOptMoveSelector;
64pub use selector::KOptMoveSelector;
solverforge_solver/heuristic/selector/k_opt/mod.rs

solverforge_solver/heuristic/selector/k_opt/
mod.rs
