solverforge_solver/phase/localsearch/acceptor/
entity_tabu.rs

1//! Entity tabu acceptor.
2
3use std::fmt::Debug;
4
5use solverforge_core::domain::PlanningSolution;
6
7use super::Acceptor;
8
9/// Entity tabu acceptor - maintains a tabu list based on entity identifiers.
10///
11/// This is a more sophisticated tabu search that tracks which entities
12/// have been recently modified rather than just tracking scores.
13/// It requires entities to have a stable hash/identifier.
14///
15/// # Example
16///
17/// ```
18/// use solverforge_solver::phase::localsearch::EntityTabuAcceptor;
19///
20/// let acceptor = EntityTabuAcceptor::new(7);
21/// assert!(!acceptor.is_entity_tabu(42));
22/// ```
23pub struct EntityTabuAcceptor {
24    /// Maximum number of entity changes to remember.
25    entity_tabu_size: usize,
26    /// List of tabu entity identifiers (as u64 hashes).
27    entity_tabu_list: Vec<u64>,
28    /// Current step's moved entities.
29    current_step_entities: Vec<u64>,
30}
31
32impl Debug for EntityTabuAcceptor {
33    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
34        f.debug_struct("EntityTabuAcceptor")
35            .field("entity_tabu_size", &self.entity_tabu_size)
36            .field("tabu_list_len", &self.entity_tabu_list.len())
37            .finish()
38    }
39}
40
41impl Clone for EntityTabuAcceptor {
42    fn clone(&self) -> Self {
43        Self {
44            entity_tabu_size: self.entity_tabu_size,
45            entity_tabu_list: self.entity_tabu_list.clone(),
46            current_step_entities: self.current_step_entities.clone(),
47        }
48    }
49}
50
51impl EntityTabuAcceptor {
52    /// Creates a new entity tabu acceptor.
53    ///
54    /// # Panics
55    ///
56    /// Panics if `entity_tabu_size` is 0.
57    pub fn new(entity_tabu_size: usize) -> Self {
58        assert!(entity_tabu_size > 0, "entity_tabu_size must be > 0, got 0");
59        Self {
60            entity_tabu_size,
61            entity_tabu_list: Vec::with_capacity(entity_tabu_size),
62            current_step_entities: Vec::new(),
63        }
64    }
65
66    /// Records that an entity was moved in the current step.
67    pub fn record_entity_move(&mut self, entity_id: u64) {
68        self.current_step_entities.push(entity_id);
69    }
70
71    /// Returns true if the given entity is in the tabu list.
72    pub fn is_entity_tabu(&self, entity_id: u64) -> bool {
73        self.entity_tabu_list.contains(&entity_id)
74    }
75}
76
77impl Default for EntityTabuAcceptor {
78    fn default() -> Self {
79        Self::new(7)
80    }
81}
82
83impl<S: PlanningSolution> Acceptor<S> for EntityTabuAcceptor {
84    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
85        // Accept improving moves
86        if move_score > last_step_score {
87            return true;
88        }
89
90        // Accept equal moves for exploration
91        if move_score >= last_step_score {
92            return true;
93        }
94
95        false
96    }
97
98    fn phase_started(&mut self, _initial_score: &S::Score) {
99        self.entity_tabu_list.clear();
100        self.current_step_entities.clear();
101    }
102
103    fn phase_ended(&mut self) {
104        self.entity_tabu_list.clear();
105    }
106
107    fn step_started(&mut self) {
108        self.current_step_entities.clear();
109    }
110
111    fn step_ended(&mut self, _step_score: &S::Score) {
112        // Add current step's entities to tabu list
113        for entity_id in &self.current_step_entities {
114            if self.entity_tabu_list.len() >= self.entity_tabu_size {
115                self.entity_tabu_list.remove(0);
116            }
117            self.entity_tabu_list.push(*entity_id);
118        }
119        self.current_step_entities.clear();
120    }
121}
solverforge_solver/phase/localsearch/acceptor/entity_tabu.rs

solverforge_solver/phase/localsearch/acceptor/
entity_tabu.rs
