Struct MinimumDecisionTree 

pub struct MinimumDecisionTree { /* private fields */ }

Minimum Decision Tree problem.

Given objects distinguished by binary tests, find a decision tree minimizing the total external path length (sum of leaf depths).

The configuration encodes a flattened complete binary tree of depth num_objects - 1. Each internal node stores either a test index (0..num_tests-1) or a sentinel value num_tests meaning “leaf”.

Example

use problemreductions::models::misc::MinimumDecisionTree;
use problemreductions::{Problem, Solver, BruteForce};

let problem = MinimumDecisionTree::new(
    vec![
        vec![true, true, false, false],   // T0
        vec![true, false, false, false],   // T1
        vec![false, true, false, true],    // T2
    ],
    4,
    3,
);
let solver = BruteForce::new();
let value = solver.solve(&problem);

Implementations

impl MinimumDecisionTree

pub fn new( test_matrix: Vec<Vec<bool>>, num_objects: usize, num_tests: usize, ) -> Self

Create a new MinimumDecisionTree problem.

Panics

• If num_objects < 2 or num_tests < 1
• If test_matrix dimensions don’t match
• If tests don’t distinguish all object pairs

pub fn num_objects(&self) -> usize

Get the number of objects.

pub fn num_tests(&self) -> usize

Get the number of tests.

pub fn test_matrix(&self) -> &[Vec<bool>]

Get the test matrix.

Trait Implementations

impl Clone for MinimumDecisionTree

fn clone(&self) -> MinimumDecisionTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MinimumDecisionTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumDecisionTree

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumDecisionTree

const NAME: &'static str = "MinimumDecisionTree"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Min<usize>

The evaluation value type.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Min<usize>

Evaluate the problem on a configuration.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl Serialize for MinimumDecisionTree

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for MinimumDecisionTree