problemreductions/models/misc/
minimum_decision_tree.rs

1//! Minimum Decision Tree problem implementation.
2//!
3//! Given a set of objects distinguished by binary tests, find a decision tree
4//! that identifies each object with minimum total external path length
5//! (sum of depths of all leaves).
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "MinimumDecisionTree",
15        display_name: "Minimum Decision Tree",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Find decision tree identifying objects with minimum total path length",
21        fields: MinimumDecisionTreeCreateSpec::FIELDS,
22    }
23}
24
25/// Minimum Decision Tree problem.
26///
27/// Given objects distinguished by binary tests, find a decision tree
28/// minimizing the total external path length (sum of leaf depths).
29///
30/// The configuration encodes a flattened complete binary tree of depth
31/// `num_objects - 1`. Each internal node stores either a test index
32/// (0..num_tests-1) or a sentinel value `num_tests` meaning "leaf".
33///
34/// # Example
35///
36/// ```
37/// use problemreductions::models::misc::MinimumDecisionTree;
38/// use problemreductions::{Problem, BruteForce};
39///
40/// let problem = MinimumDecisionTree::new(
41///     vec![
42///         vec![true, true, false, false],   // T0
43///         vec![true, false, false, false],   // T1
44///         vec![false, true, false, true],    // T2
45///     ],
46///     4,
47///     3,
48/// );
49/// let solver = BruteForce::new();
50/// let value = solver.solve(&problem).unwrap();
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53#[serde(try_from = "MinimumDecisionTreeCreateSpec")]
54pub struct MinimumDecisionTree {
55    /// Binary matrix: test_matrix[j][i] = true iff object i passes test j.
56    test_matrix: Vec<Vec<bool>>,
57    /// Number of objects.
58    num_objects: usize,
59    /// Number of tests.
60    num_tests: usize,
61}
62
63#[derive(Debug, Deserialize, crate::CreateSpec)]
64struct MinimumDecisionTreeCreateSpec {
65    /// Binary test matrix as JSON.
66    #[create(codec = "json")]
67    test_matrix: Vec<Vec<bool>>,
68    /// Number of objects.
69    num_objects: usize,
70    /// Number of tests.
71    num_tests: usize,
72}
73
74impl TryFrom<MinimumDecisionTreeCreateSpec> for MinimumDecisionTree {
75    type Error = crate::registry::ConstructionError;
76    fn try_from(spec: MinimumDecisionTreeCreateSpec) -> Result<Self, Self::Error> {
77        Self::try_new(spec.test_matrix, spec.num_objects, spec.num_tests)
78    }
79}
80
81impl MinimumDecisionTree {
82    /// Create a new MinimumDecisionTree problem.
83    ///
84    /// # Panics
85    /// - If num_objects < 2 or num_tests < 1
86    /// - If the flattened tree slot count cannot fit in usize
87    /// - If test_matrix dimensions don't match
88    /// - If tests don't distinguish all object pairs
89    pub fn new(test_matrix: Vec<Vec<bool>>, num_objects: usize, num_tests: usize) -> Self {
90        Self::try_new(test_matrix, num_objects, num_tests).unwrap_or_else(|error| panic!("{error}"))
91    }
92
93    fn try_new(
94        test_matrix: Vec<Vec<bool>>,
95        num_objects: usize,
96        num_tests: usize,
97    ) -> Result<Self, crate::registry::ConstructionError> {
98        if num_objects < 2 {
99            return Err("Need at least 2 objects".into());
100        }
101        if num_objects > usize::BITS as usize {
102            return Err(crate::registry::ConstructionError::IntegerOverflow(
103                "representing the decision-tree witness slots".into(),
104            ));
105        }
106        if num_tests == 0 {
107            return Err("Need at least 1 test".into());
108        }
109        if test_matrix.len() != num_tests {
110            return Err("test_matrix must have num_tests rows".into());
111        }
112        for (j, row) in test_matrix.iter().enumerate() {
113            if row.len() != num_objects {
114                return Err(format!("test_matrix[{j}] must have num_objects columns").into());
115            }
116        }
117        // Check that every pair of objects is distinguished by at least one test
118        for a in 0..num_objects {
119            for b in (a + 1)..num_objects {
120                let distinguished = (0..num_tests).any(|j| test_matrix[j][a] != test_matrix[j][b]);
121                if !distinguished {
122                    return Err(
123                        format!("Objects {a} and {b} are not distinguished by any test").into(),
124                    );
125                }
126            }
127        }
128        Ok(Self {
129            test_matrix,
130            num_objects,
131            num_tests,
132        })
133    }
134
135    /// Get the number of objects.
136    pub fn num_objects(&self) -> usize {
137        self.num_objects
138    }
139
140    /// Get the number of tests.
141    pub fn num_tests(&self) -> usize {
142        self.num_tests
143    }
144
145    /// Get the test matrix.
146    pub fn test_matrix(&self) -> &[Vec<bool>] {
147        &self.test_matrix
148    }
149
150    /// Number of internal node slots in the flattened complete binary tree.
151    fn num_tree_slots(&self) -> usize {
152        (1usize << (self.num_objects - 1)) - 1
153    }
154
155    /// Sentinel value meaning "this node is a leaf".
156    fn leaf_sentinel(&self) -> usize {
157        self.num_tests
158    }
159
160    /// Simulate the decision tree for all objects and return total external path length,
161    /// or None if the tree is invalid (doesn't identify all objects uniquely).
162    fn simulate(&self, config: &[usize]) -> Result<Option<i64>, crate::traits::EvaluationError> {
163        let sentinel = self.leaf_sentinel();
164        let max_slots = self.num_tree_slots();
165        let mut seen_leaves = std::collections::HashSet::new();
166        let mut total_depth = 0_i64;
167
168        for obj in 0..self.num_objects {
169            let mut node = 0usize;
170            let mut depth = 0usize;
171
172            loop {
173                if node >= max_slots || config[node] == sentinel {
174                    // Two objects at same leaf — invalid
175                    if !seen_leaves.insert(node) {
176                        return Ok(None);
177                    }
178                    let depth = i64::try_from(depth).map_err(|_| {
179                        crate::traits::EvaluationError::IntegerOverflow(
180                            "converting decision-tree depth to i64".to_string(),
181                        )
182                    })?;
183                    total_depth = total_depth.checked_add(depth).ok_or_else(|| {
184                        crate::traits::EvaluationError::IntegerOverflow(
185                            "summing decision-tree external path length".to_string(),
186                        )
187                    })?;
188                    break;
189                }
190
191                let test_idx = config[node];
192                debug_assert!(test_idx < self.num_tests);
193
194                let result = self.test_matrix[test_idx][obj];
195                node = if result { 2 * node + 2 } else { 2 * node + 1 };
196                depth += 1;
197
198                if depth > self.num_objects {
199                    return Ok(None);
200                }
201            }
202        }
203
204        Ok(Some(total_depth))
205    }
206}
207
208impl Problem for MinimumDecisionTree {
209    const NAME: &'static str = "MinimumDecisionTree";
210    type Solution = Vec<usize>;
211    type Value = Min<i64>;
212
213    crate::problem_parameters![("num_objects", num_objects), ("num_tests", num_tests),];
214
215    fn evaluate(
216        &self,
217        config: &Self::Solution,
218    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
219        Ok({
220            if config.len() != self.num_tree_slots() {
221                return Err(crate::traits::EvaluationError::InvalidConfiguration(
222                    "decision-tree encoding length does not match the instance".into(),
223                ));
224            }
225            if config.iter().any(|&test| test > self.num_tests) {
226                return Err(crate::traits::EvaluationError::InvalidConfiguration(
227                    "decision-tree encoding contains an out-of-range test".into(),
228                ));
229            }
230            Min(self.simulate(config)?)
231        })
232    }
233
234    fn variant() -> Vec<(&'static str, &'static str)> {
235        crate::variant_params![]
236    }
237}
238
239impl crate::solvers::BruteForceProblem for MinimumDecisionTree {
240    fn dimensions(&self) -> Vec<usize> {
241        // Each internal node can hold test 0..num_tests-1 or sentinel (leaf)
242        vec![self.num_tests + 1; self.num_tree_slots()]
243    }
244}
245
246crate::declare_variants! {
247    default MinimumDecisionTree => "num_tests^num_objects" create MinimumDecisionTreeCreateSpec,
248}
249
250crate::register_brute_force! {
251    MinimumDecisionTree,
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![crate::example_db::specs::ModelExampleSpec {
257        id: "minimum_decision_tree",
258        instance: Box::new(MinimumDecisionTree::new(
259            vec![
260                vec![true, true, false, false],
261                vec![true, false, false, false],
262                vec![false, true, false, true],
263            ],
264            4,
265            3,
266        )),
267        // T0 at root, T2 left, T1 right, rest are leaves (sentinel=3)
268        optimal_config: serde_json::json!(vec![0, 2, 1, 3, 3, 3, 3]),
269        optimal_value: serde_json::json!(8),
270    }]
271}
272
273#[cfg(test)]
274#[path = "../../unit_tests/models/misc/minimum_decision_tree.rs"]
275mod tests;
problemreductions/models/misc/minimum_decision_tree.rs

problemreductions/models/misc/
minimum_decision_tree.rs
