solverforge_solver/phase/exhaustive/
node.rs

1/* Exhaustive search node representation.
2
3Each node represents a partial solution state in the search tree.
4*/
5
6use std::marker::PhantomData;
7
8use crate::heuristic::Move;
9use solverforge_core::domain::PlanningSolution;
10
11/* A node in the exhaustive search tree.
12
13Each node represents a partial solution state, containing:
14- The depth in the search tree (number of variables assigned)
15- The score at this node
16- An optimistic bound (best possible score from this node)
17- The move sequence to reach this node from the root
18*/
19#[derive(Debug, Clone)]
20pub struct ExhaustiveSearchNode<S: PlanningSolution> {
21    // Depth in the search tree (0 = root, number of assignments made).
22    depth: usize,
23
24    // The score at this node after applying all moves.
25    score: S::Score,
26
27    // Optimistic bound: best possible score achievable from this node.
28    // Used for pruning branches that cannot improve on the best solution.
29    optimistic_bound: Option<S::Score>,
30
31    // Index of the entity being assigned at this node.
32    entity_index: Option<usize>,
33
34    // Index of the value assigned at this node.
35    value_index: Option<usize>,
36
37    // Parent node index in the node list (None for root).
38    parent_index: Option<usize>,
39
40    // Whether this node has been expanded.
41    expanded: bool,
42}
43
44impl<S: PlanningSolution> ExhaustiveSearchNode<S> {
45    pub fn root(score: S::Score) -> Self {
46        Self {
47            depth: 0,
48            score,
49            optimistic_bound: None,
50            entity_index: None,
51            value_index: None,
52            parent_index: None,
53            expanded: false,
54        }
55    }
56
57    pub fn child(
58        parent_index: usize,
59        depth: usize,
60        score: S::Score,
61        entity_index: usize,
62        value_index: usize,
63    ) -> Self {
64        Self {
65            depth,
66            score,
67            optimistic_bound: None,
68            entity_index: Some(entity_index),
69            value_index: Some(value_index),
70            parent_index: Some(parent_index),
71            expanded: false,
72        }
73    }
74
75    #[inline]
76    pub fn depth(&self) -> usize {
77        self.depth
78    }
79
80    #[inline]
81    pub fn score(&self) -> &S::Score {
82        &self.score
83    }
84
85    pub fn set_score(&mut self, score: S::Score) {
86        self.score = score;
87    }
88
89    #[inline]
90    pub fn optimistic_bound(&self) -> Option<&S::Score> {
91        self.optimistic_bound.as_ref()
92    }
93
94    pub fn set_optimistic_bound(&mut self, bound: S::Score) {
95        self.optimistic_bound = Some(bound);
96    }
97
98    #[inline]
99    pub fn entity_index(&self) -> Option<usize> {
100        self.entity_index
101    }
102
103    #[inline]
104    pub fn value_index(&self) -> Option<usize> {
105        self.value_index
106    }
107
108    #[inline]
109    pub fn parent_index(&self) -> Option<usize> {
110        self.parent_index
111    }
112
113    // Returns whether this node has been expanded.
114    #[inline]
115    pub fn is_expanded(&self) -> bool {
116        self.expanded
117    }
118
119    /// Marks this node as expanded.
120    pub fn mark_expanded(&mut self) {
121        self.expanded = true;
122    }
123
124    pub fn is_leaf(&self, total_entities: usize) -> bool {
125        self.depth >= total_entities
126    }
127
128    pub fn can_prune(&self, best_score: &S::Score) -> bool {
129        match &self.optimistic_bound {
130            Some(bound) => bound <= best_score,
131            None => false,
132        }
133    }
134}
135
136/* Tracks the move sequence to reconstruct a solution path.
137
138# Type Parameters
139* `S` - The planning solution type
140* `M` - The move type
141*/
142#[derive(Debug, Clone)]
143pub struct MoveSequence<S, M>
144where
145    S: PlanningSolution,
146    M: Move<S>,
147{
148    // The sequence of moves from root to current node.
149    moves: Vec<M>,
150    _phantom: PhantomData<fn() -> S>,
151}
152
153impl<S, M> MoveSequence<S, M>
154where
155    S: PlanningSolution,
156    M: Move<S>,
157{
158    pub fn new() -> Self {
159        Self {
160            moves: Vec::new(),
161            _phantom: PhantomData,
162        }
163    }
164
165    pub fn with_capacity(capacity: usize) -> Self {
166        Self {
167            moves: Vec::with_capacity(capacity),
168            _phantom: PhantomData,
169        }
170    }
171
172    pub fn push(&mut self, m: M) {
173        self.moves.push(m);
174    }
175
176    /// Removes and returns the last move.
177    pub fn pop(&mut self) -> Option<M> {
178        self.moves.pop()
179    }
180
181    pub fn len(&self) -> usize {
182        self.moves.len()
183    }
184
185    pub fn is_empty(&self) -> bool {
186        self.moves.is_empty()
187    }
188
189    /// Returns an iterator over the moves.
190    pub fn iter(&self) -> impl Iterator<Item = &M> {
191        self.moves.iter()
192    }
193
194    /// Clears all moves from the sequence.
195    pub fn clear(&mut self) {
196        self.moves.clear();
197    }
198}
199
200impl<S, M> Default for MoveSequence<S, M>
201where
202    S: PlanningSolution,
203    M: Move<S>,
204{
205    fn default() -> Self {
206        Self::new()
207    }
208}
209
210#[cfg(test)]
211#[path = "node_tests.rs"]
212mod tests;
solverforge_solver/phase/exhaustive/node.rs

solverforge_solver/phase/exhaustive/
node.rs
