aprender_tsp/solver/
mod.rs

1//! TSP solver implementations.
2//!
3//! Provides multiple metaheuristic backends:
4//! - ACO (Ant Colony Optimization)
5//! - Tabu Search
6//! - Genetic Algorithm
7//! - Hybrid
8
9mod aco;
10mod ga;
11mod hybrid;
12mod tabu;
13
14pub use aco::AcoSolver;
15pub use ga::GaSolver;
16pub use hybrid::HybridSolver;
17pub use tabu::TabuSolver;
18
19use crate::error::TspResult;
20use crate::instance::TspInstance;
21
22/// Budget for optimization
23#[derive(Debug, Clone, Copy)]
24pub enum Budget {
25    /// Maximum number of iterations
26    Iterations(usize),
27    /// Maximum number of tour evaluations
28    Evaluations(usize),
29}
30
31impl Budget {
32    /// Get the limit value
33    pub fn limit(&self) -> usize {
34        match self {
35            Self::Iterations(n) | Self::Evaluations(n) => *n,
36        }
37    }
38}
39
40/// TSP solution
41#[derive(Debug, Clone)]
42pub struct TspSolution {
43    /// Tour as city indices
44    pub tour: Vec<usize>,
45    /// Total tour length
46    pub length: f64,
47    /// Number of evaluations used
48    pub evaluations: usize,
49    /// Convergence history (best length per iteration)
50    pub history: Vec<f64>,
51}
52
53impl TspSolution {
54    /// Create a new solution
55    pub fn new(tour: Vec<usize>, length: f64) -> Self {
56        Self {
57            tour,
58            length,
59            evaluations: 0,
60            history: vec![length],
61        }
62    }
63
64    /// Check if this solution is better than another
65    pub fn is_better_than(&self, other: &Self) -> bool {
66        self.length < other.length
67    }
68}
69
70/// Trait for TSP solvers
71pub trait TspSolver: Send + Sync {
72    /// Solve a TSP instance
73    fn solve(&mut self, instance: &TspInstance, budget: Budget) -> TspResult<TspSolution>;
74
75    /// Get algorithm name
76    fn name(&self) -> &'static str;
77
78    /// Reset solver state
79    fn reset(&mut self);
80}
81
82/// Algorithm type for model persistence
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84pub enum TspAlgorithm {
85    /// Ant Colony Optimization
86    Aco,
87    /// Tabu Search
88    Tabu,
89    /// Genetic Algorithm
90    Ga,
91    /// Hybrid (GA + Tabu + ACO)
92    Hybrid,
93}
94
95impl TspAlgorithm {
96    /// Get string name
97    pub fn as_str(&self) -> &'static str {
98        match self {
99            Self::Aco => "aco",
100            Self::Tabu => "tabu",
101            Self::Ga => "ga",
102            Self::Hybrid => "hybrid",
103        }
104    }
105
106    /// Parse from string
107    pub fn parse(s: &str) -> Option<Self> {
108        match s.to_lowercase().as_str() {
109            "aco" | "ant" | "antcolony" => Some(Self::Aco),
110            "tabu" | "tabusearch" => Some(Self::Tabu),
111            "ga" | "genetic" => Some(Self::Ga),
112            "hybrid" | "auto" => Some(Self::Hybrid),
113            _ => None,
114        }
115    }
116}
117
118/// Solution quality tier
119#[derive(Debug, Clone, Copy, PartialEq, Eq)]
120pub enum SolutionTier {
121    /// Within 0.1% of optimal
122    Optimal,
123    /// Within 1% of optimal
124    Excellent,
125    /// Within 2% of optimal
126    Good,
127    /// Within 5% of optimal
128    Acceptable,
129    /// More than 5% from optimal
130    Poor,
131}
132
133impl SolutionTier {
134    /// Classify solution quality based on gap percentage
135    pub fn from_gap(gap_percent: f64) -> Self {
136        if gap_percent < 0.1 {
137            Self::Optimal
138        } else if gap_percent < 1.0 {
139            Self::Excellent
140        } else if gap_percent < 2.0 {
141            Self::Good
142        } else if gap_percent < 5.0 {
143            Self::Acceptable
144        } else {
145            Self::Poor
146        }
147    }
148
149    /// Get string representation
150    pub fn as_str(&self) -> &'static str {
151        match self {
152            Self::Optimal => "Optimal",
153            Self::Excellent => "Excellent",
154            Self::Good => "Good",
155            Self::Acceptable => "Acceptable",
156            Self::Poor => "Poor",
157        }
158    }
159}
160
161/// Calculate gap from optimal (or best known)
162pub fn optimality_gap(solution_length: f64, optimal_length: f64) -> f64 {
163    ((solution_length - optimal_length) / optimal_length) * 100.0
164}
165
166#[cfg(test)]
167mod tests {
168    use super::*;
169
170    #[test]
171    fn test_solution_new() {
172        let solution = TspSolution::new(vec![0, 1, 2], 10.5);
173        assert_eq!(solution.tour, vec![0, 1, 2]);
174        assert!((solution.length - 10.5).abs() < 1e-10);
175        assert_eq!(solution.evaluations, 0);
176        assert_eq!(solution.history.len(), 1);
177    }
178
179    #[test]
180    fn test_solution_comparison() {
181        let better = TspSolution::new(vec![0, 1, 2], 10.0);
182        let worse = TspSolution::new(vec![0, 2, 1], 15.0);
183
184        assert!(better.is_better_than(&worse));
185        assert!(!worse.is_better_than(&better));
186    }
187
188    #[test]
189    fn test_algorithm_parsing() {
190        assert_eq!(TspAlgorithm::parse("aco"), Some(TspAlgorithm::Aco));
191        assert_eq!(TspAlgorithm::parse("ACO"), Some(TspAlgorithm::Aco));
192        assert_eq!(TspAlgorithm::parse("tabu"), Some(TspAlgorithm::Tabu));
193        assert_eq!(TspAlgorithm::parse("ga"), Some(TspAlgorithm::Ga));
194        assert_eq!(TspAlgorithm::parse("hybrid"), Some(TspAlgorithm::Hybrid));
195        assert_eq!(TspAlgorithm::parse("auto"), Some(TspAlgorithm::Hybrid));
196        assert_eq!(TspAlgorithm::parse("unknown"), None);
197    }
198
199    #[test]
200    fn test_algorithm_as_str() {
201        assert_eq!(TspAlgorithm::Aco.as_str(), "aco");
202        assert_eq!(TspAlgorithm::Tabu.as_str(), "tabu");
203        assert_eq!(TspAlgorithm::Ga.as_str(), "ga");
204        assert_eq!(TspAlgorithm::Hybrid.as_str(), "hybrid");
205    }
206
207    #[test]
208    fn test_solution_tier_from_gap() {
209        assert_eq!(SolutionTier::from_gap(0.05), SolutionTier::Optimal);
210        assert_eq!(SolutionTier::from_gap(0.5), SolutionTier::Excellent);
211        assert_eq!(SolutionTier::from_gap(1.5), SolutionTier::Good);
212        assert_eq!(SolutionTier::from_gap(3.0), SolutionTier::Acceptable);
213        assert_eq!(SolutionTier::from_gap(10.0), SolutionTier::Poor);
214    }
215
216    #[test]
217    fn test_optimality_gap() {
218        let gap = optimality_gap(102.0, 100.0);
219        assert!((gap - 2.0).abs() < 1e-10);
220
221        let gap = optimality_gap(100.0, 100.0);
222        assert!((gap - 0.0).abs() < 1e-10);
223    }
224
225    #[test]
226    fn test_budget_limit() {
227        assert_eq!(Budget::Iterations(100).limit(), 100);
228        assert_eq!(Budget::Evaluations(500).limit(), 500);
229    }
230}
aprender_tsp/solver/mod.rs

aprender_tsp/solver/
mod.rs
