solverforge-solver 0.8.6

Solver engine for SolverForge
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

// Entity tabu acceptor.

use std::fmt::Debug;

use solverforge_core::domain::PlanningSolution;

use super::Acceptor;

/// Entity tabu acceptor - maintains a tabu list based on entity identifiers.
///
/// This is a more sophisticated tabu search that tracks which entities
/// have been recently modified rather than just tracking scores.
/// It requires entities to have a stable hash/identifier.
///
/// # Example
///
/// ```
/// use solverforge_solver::phase::localsearch::EntityTabuAcceptor;
///
/// let acceptor = EntityTabuAcceptor::new(7);
/// assert!(!acceptor.is_entity_tabu(42));
/// ```
pub struct EntityTabuAcceptor {
    // Maximum number of entity changes to remember.
    entity_tabu_size: usize,
    // List of tabu entity identifiers (as u64 hashes).
    entity_tabu_list: Vec<u64>,
    // Current step's moved entities.
    current_step_entities: Vec<u64>,
}

impl Debug for EntityTabuAcceptor {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("EntityTabuAcceptor")
            .field("entity_tabu_size", &self.entity_tabu_size)
            .field("tabu_list_len", &self.entity_tabu_list.len())
            .finish()
    }
}

impl Clone for EntityTabuAcceptor {
    fn clone(&self) -> Self {
        Self {
            entity_tabu_size: self.entity_tabu_size,
            entity_tabu_list: self.entity_tabu_list.clone(),
            current_step_entities: self.current_step_entities.clone(),
        }
    }
}

impl EntityTabuAcceptor {
    /// Creates a new entity tabu acceptor.
    ///
    /// # Panics
    ///
    /// Panics if `entity_tabu_size` is 0.
    pub fn new(entity_tabu_size: usize) -> Self {
        assert!(entity_tabu_size > 0, "entity_tabu_size must be > 0, got 0");
        Self {
            entity_tabu_size,
            entity_tabu_list: Vec::with_capacity(entity_tabu_size),
            current_step_entities: Vec::new(),
        }
    }

    /// Records that an entity was moved in the current step.
    pub fn record_entity_move(&mut self, entity_id: u64) {
        self.current_step_entities.push(entity_id);
    }

    pub fn is_entity_tabu(&self, entity_id: u64) -> bool {
        self.entity_tabu_list.contains(&entity_id)
    }
}

impl Default for EntityTabuAcceptor {
    fn default() -> Self {
        Self::new(7)
    }
}

impl<S: PlanningSolution> Acceptor<S> for EntityTabuAcceptor {
    fn is_accepted(&mut self, last_step_score: &S::Score, move_score: &S::Score) -> bool {
        // Accept improving moves
        if move_score > last_step_score {
            return true;
        }

        // Accept equal moves for exploration
        if move_score >= last_step_score {
            return true;
        }

        false
    }

    fn phase_started(&mut self, _initial_score: &S::Score) {
        self.entity_tabu_list.clear();
        self.current_step_entities.clear();
    }

    fn phase_ended(&mut self) {
        self.entity_tabu_list.clear();
    }

    fn step_started(&mut self) {
        self.current_step_entities.clear();
    }

    fn step_ended(&mut self, _step_score: &S::Score) {
        // Add current step's entities to tabu list
        for entity_id in &self.current_step_entities {
            if self.entity_tabu_list.len() >= self.entity_tabu_size {
                self.entity_tabu_list.remove(0);
            }
            self.entity_tabu_list.push(*entity_id);
        }
        self.current_step_entities.clear();
    }
}