branch_and_bound

Function solve

Source 
pub fn solve<Node: Subproblem>(
    initial: Node,
    method: TraverseMethod<Node>,
) -> Option<Node>
Expand description

Solve a problem with branch-and-bound / backtracking, using one of the default strategies.

Walks the subproblem tree (initial is the root) according to the method specified by method.

solve should be preferred for simple scenareous (i.e., a single initial node, one of the default search strategy implementations). For more advanced use cases, use solve_with_container.

Examples found in repository?
examples/knapsack.rs (line 56)
55fn solve(problem: KnapsackSubproblem) -> Option<KnapsackSubproblem> {
56    branch_and_bound::solve(problem, branch_and_bound::TraverseMethod::BestFirst)
57}
More examples
Hide additional examples
examples/dpll.rs (line 97)
89fn solve(parsed: &CnfSat) -> Option<Vec<i8>> {
90    let problem = Node {
91        clauses: Rc::new(parsed.clauses.clone()),
92        vars_left: Rc::new(parsed.vars_by_frequency.clone()),
93        vars_left_idx: 0,
94        assignments: vec![0; 1 + parsed.vars_cnt as usize],
95    };
96
97    branch_and_bound::solve(problem, branch_and_bound::TraverseMethod::DepthFirst)
98        .map(|n| n.assignments)
99}
examples/explicit-graph.rs (line 90)
86fn main() {
87    println!("Trying depth-first search");
88    println!(
89        "Max node: {:#?}",
90        bb::solve(graph(), bb::TraverseMethod::DepthFirst)
91    );
92
93    println!("Trying breadth-first search");
94    println!(
95        "Max node: {:#?}",
96        bb::solve(graph(), bb::TraverseMethod::BreadthFirst)
97    );
98
99    println!("Now trying best-first search");
100    println!(
101        "Max node: {:#?}",
102        bb::solve(graph(), bb::TraverseMethod::BestFirst)
103    );
104
105    println!("Trying custom-order (should be same as best-first!)");
106    println!(
107        "Max node: {:#?}",
108        bb::solve(
109            graph(),
110            bb::TraverseMethod::Custom {
111                cmp: Box::new(|n1, n2| n1.bound.cmp(&n2.bound)),
112                cmp_superceeds_bound: true
113            }
114        )
115    );
116
117    println!("Trying custom-order, worst-first search");
118    println!(
119        "Max node: {:#?}",
120        bb::solve(
121            graph(),
122            bb::TraverseMethod::Custom {
123                cmp: Box::new(|n1, n2| n2.bound.cmp(&n1.bound)),
124                cmp_superceeds_bound: false
125            }
126        )
127    );
128}