Struct ddo::core::implementation::heuristics::MaxUB

pub struct MaxUB;

This is the default heuristic to set the order in which nodes are popped from the fringe So far, this is not only the default heuristic, but it is also your only choice (this was configurable in the past and could possibly change back in the future).

This ordering optimistically selects the most promising nodes first. That is, it ranks nodes based on the upper bound reachable passing through them (larger is ranked higher) and then on the length of their longest path (again, longer is better).

Note

This ordering considers the worst nodes as being the least elements of the order.

Example

let a = Node {state: 'a', info: NodeInfo{lp_len: 42, lp_arc: None, ub: 300, is_exact: true, is_relaxed: false}};
let b = Node {state: 'b', info: NodeInfo{lp_len:  2, lp_arc: None, ub: 100, is_exact: true, is_relaxed: false}};
let c = Node {state: 'c', info: NodeInfo{lp_len: 24, lp_arc: None, ub: 150, is_exact: true, is_relaxed: false}};
let d = Node {state: 'd', info: NodeInfo{lp_len: 13, lp_arc: None, ub:  60, is_exact: true, is_relaxed: false}};
let e = Node {state: 'e', info: NodeInfo{lp_len: 65, lp_arc: None, ub: 700, is_exact: true, is_relaxed: false}};
let f = Node {state: 'f', info: NodeInfo{lp_len: 19, lp_arc: None, ub: 100, is_exact: true, is_relaxed: false}};

let nodes = vec![a.clone(), b.clone(), c.clone(), d.clone(), e.clone(), f.clone()];
let mut priority_q = BinaryHeap::from_vec_cmp(nodes, MaxUB);

assert_eq!(e, priority_q.pop().unwrap()); // because 700 is the highest upper bound
assert_eq!(a, priority_q.pop().unwrap()); // because 300 is the next highest
assert_eq!(c, priority_q.pop().unwrap()); // idem, because of ub = 150
assert_eq!(f, priority_q.pop().unwrap()); // because ub = 100 but lp_len = 19
assert_eq!(b, priority_q.pop().unwrap()); // because ub = 100 but lp_len = 2
assert_eq!(d, priority_q.pop().unwrap()); // because ub = 13 which is the worst

Trait Implementations

impl Clone for MaxUB

fn clone(&self) -> MaxUB

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Compare<Node<T>, Node<T>> for MaxUB

fn compare(&self, a: &Node<T>, b: &Node<T>) -> Ordering

Compares two values, returning Less, Equal, or Greater if l is less than, equal to, or greater than r, respectively.

fn compares_lt(&self, l: &L, r: &R) -> bool

Checks if l is less than r.

fn compares_le(&self, l: &L, r: &R) -> bool

Checks if l is less than or equal to r.

fn compares_ge(&self, l: &L, r: &R) -> bool

Checks if l is greater than or equal to r.

fn compares_gt(&self, l: &L, r: &R) -> bool

Checks if l is greater than r.

fn compares_eq(&self, l: &L, r: &R) -> bool

Checks if l is equal to r.

fn compares_ne(&self, l: &L, r: &R) -> bool

Checks if l is not equal to r.

fn borrowing(self) -> Borrowing<Self, L, R>

Borrows the comparator's parameters before comparing them.

fn rev(self) -> Rev<Self>

Reverses the ordering of the comparator.

fn swap(self) -> Swap<Self>

Swaps the comparator's parameters, maintaining the underlying ordering.

fn then<D>(self, then: D) -> Then<Self, D> where
    D: Compare<L, R>, 

Lexicographically combines the comparator with another.

impl Debug for MaxUB

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

Formats the value using the given formatter.

impl Default for MaxUB

fn default() -> MaxUB

Returns the "default value" for a type.