Struct Tree 

pub struct Tree<S>
where
    S: ModifiableState,
{
    state: S,
    latest: usize,
    nodes: Vec<Node<S>>,
    cur_node: usize,
}

Fields

state: S

latest: usize

nodes: Vec<Node<S>>

cur_node: usize

Implementations

impl<S> Tree<S>

where S: ModifiableState,

pub fn new(state: S, init_op: S::Operation) -> Self

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 276)

pub fn beam_search<S>(
    state: S,
    init_op: S::Operation,
    beam_weidth: usize,
    minimize: bool,
) -> Option<(S::Score, Vec<S::Operation>)>
where
    S: ModifiableState,
{
    let mut tree = Tree::new(state, init_op);
    let mut cands = vec![];
    let mut set = HashSet::<S::Hash>::default();
    loop {
        tree.dfs(&mut cands, &set, true);
        if let Some(res) = tree.take_best(&cands, minimize) {
            return Some(res);
        }
        if cands.is_empty() {
            return None;
        }
        set.extend(cands.iter().map(|cand| cand.hash.clone()));
        tree.update(&mut cands, beam_weidth, minimize);
    }
}

fn add_node( &mut self, op: S::Operation, parent: usize, score: S::Score, hash: S::Hash, )

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 189)

    fn update(&mut self, cands: &mut Vec<Candidate<S>>, beam_weidth: usize, minimize: bool) {
        if cands.len() > beam_weidth {
            if minimize {
                cands.select_nth_unstable_by_key(beam_weidth, |s| s.score.clone());
            } else {
                cands.select_nth_unstable_by_key(beam_weidth, |s| Reverse(s.score.clone()));
            }
            cands.truncate(beam_weidth);
        }
        let len = self.nodes.len();
        for Candidate {
            parent,
            op,
            score,
            hash,
            ..
        } in cands.drain(..)
        {
            self.add_node(op, parent, score, hash);
        }
        for i in self.latest..len {
            if self.nodes[i].child == !0 {
                self.remove_node(i);
            }
        }
        self.latest = len;
    }

fn remove_node(&mut self, idx: usize)

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 193)

    fn update(&mut self, cands: &mut Vec<Candidate<S>>, beam_weidth: usize, minimize: bool) {
        if cands.len() > beam_weidth {
            if minimize {
                cands.select_nth_unstable_by_key(beam_weidth, |s| s.score.clone());
            } else {
                cands.select_nth_unstable_by_key(beam_weidth, |s| Reverse(s.score.clone()));
            }
            cands.truncate(beam_weidth);
        }
        let len = self.nodes.len();
        for Candidate {
            parent,
            op,
            score,
            hash,
            ..
        } in cands.drain(..)
        {
            self.add_node(op, parent, score, hash);
        }
        for i in self.latest..len {
            if self.nodes[i].child == !0 {
                self.remove_node(i);
            }
        }
        self.latest = len;
    }

pub fn operations(&self, idx: usize) -> Vec<S::Operation>

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 258)

    pub fn take_best(
        &self,
        cands: &[Candidate<S>],
        minimize: bool,
    ) -> Option<(S::Score, Vec<S::Operation>)> {
        let cands = cands.iter().filter(|cand| cand.accept);
        if let Some(Candidate {
            op, parent, score, ..
        }) = if minimize {
            cands.min_by_key(|cand| cand.score.clone())
        } else {
            cands.max_by_key(|cand| cand.score.clone())
        } {
            let mut ret = self.operations(*parent);
            ret.push(op.clone());
            Some((score.clone(), ret))
        } else {
            None
        }
    }

fn update( &mut self, cands: &mut Vec<Candidate<S>>, beam_weidth: usize, minimize: bool, )

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 288)

pub fn beam_search<S>(
    state: S,
    init_op: S::Operation,
    beam_weidth: usize,
    minimize: bool,
) -> Option<(S::Score, Vec<S::Operation>)>
where
    S: ModifiableState,
{
    let mut tree = Tree::new(state, init_op);
    let mut cands = vec![];
    let mut set = HashSet::<S::Hash>::default();
    loop {
        tree.dfs(&mut cands, &set, true);
        if let Some(res) = tree.take_best(&cands, minimize) {
            return Some(res);
        }
        if cands.is_empty() {
            return None;
        }
        set.extend(cands.iter().map(|cand| cand.hash.clone()));
        tree.update(&mut cands, beam_weidth, minimize);
    }
}

pub fn dfs( &mut self, cands: &mut Vec<Candidate<S>>, set: &HashSet<S::Hash>, single: bool, )

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 228)

    pub fn dfs(&mut self, cands: &mut Vec<Candidate<S>>, set: &HashSet<S::Hash>, single: bool) {
        let node = &self.nodes[self.cur_node];
        if node.child == !0 {
            assert!(node.score == self.state.score());
            assert!(node.hash == self.state.hash());

            for op in self.state.candidates() {
                if let Some((score, hash, accept)) =
                    self.state
                        .soft_update(op.clone(), node.score.clone(), node.hash.clone())
                    && !set.contains(&hash)
                {
                    cands.push(Candidate {
                        parent: self.cur_node,
                        op,
                        score,
                        hash,
                        accept,
                    });
                };
            }
        } else {
            let node = self.cur_node;
            let mut child = self.nodes[node].child;
            let next_single = single & (self.nodes[child].next == !0);

            loop {
                self.cur_node = child;
                self.state.update(self.nodes[child].op.clone());
                self.dfs(cands, set, next_single);

                if !next_single {
                    self.state.revert(self.nodes[child].op.clone());
                }
                child = self.nodes[child].next;
                if child == !0 {
                    break;
                }
            }

            if !next_single {
                self.cur_node = node;
            }
        }
    }

    pub fn take_best(
        &self,
        cands: &[Candidate<S>],
        minimize: bool,
    ) -> Option<(S::Score, Vec<S::Operation>)> {
        let cands = cands.iter().filter(|cand| cand.accept);
        if let Some(Candidate {
            op, parent, score, ..
        }) = if minimize {
            cands.min_by_key(|cand| cand.score.clone())
        } else {
            cands.max_by_key(|cand| cand.score.clone())
        } {
            let mut ret = self.operations(*parent);
            ret.push(op.clone());
            Some((score.clone(), ret))
        } else {
            None
        }
    }
}

pub fn beam_search<S>(
    state: S,
    init_op: S::Operation,
    beam_weidth: usize,
    minimize: bool,
) -> Option<(S::Score, Vec<S::Operation>)>
where
    S: ModifiableState,
{
    let mut tree = Tree::new(state, init_op);
    let mut cands = vec![];
    let mut set = HashSet::<S::Hash>::default();
    loop {
        tree.dfs(&mut cands, &set, true);
        if let Some(res) = tree.take_best(&cands, minimize) {
            return Some(res);
        }
        if cands.is_empty() {
            return None;
        }
        set.extend(cands.iter().map(|cand| cand.hash.clone()));
        tree.update(&mut cands, beam_weidth, minimize);
    }
}

pub fn take_best( &self, cands: &[Candidate<S>], minimize: bool, ) -> Option<(S::Score, Vec<S::Operation>)>

Examples found in repository

crates/competitive/src/heuristic/beam_search.rs (line 281)

pub fn beam_search<S>(
    state: S,
    init_op: S::Operation,
    beam_weidth: usize,
    minimize: bool,
) -> Option<(S::Score, Vec<S::Operation>)>
where
    S: ModifiableState,
{
    let mut tree = Tree::new(state, init_op);
    let mut cands = vec![];
    let mut set = HashSet::<S::Hash>::default();
    loop {
        tree.dfs(&mut cands, &set, true);
        if let Some(res) = tree.take_best(&cands, minimize) {
            return Some(res);
        }
        if cands.is_empty() {
            return None;
        }
        set.extend(cands.iter().map(|cand| cand.hash.clone()));
        tree.update(&mut cands, beam_weidth, minimize);
    }
}

Trait Implementations

impl<S> Debug for Tree<S>

where S: ModifiableState + Debug,

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

Formats the value using the given formatter.