dogs 1.3.0

Discrete Optimization Global Search framework. Implements various search algorithms that can be found in combinatorial optimization or heuristic search.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

use std::cmp::{Ord, PartialOrd};
use std::marker::PhantomData;
use std::cell::RefCell;
use std::rc::Rc;

use crate::search_manager::SearchManager;
use crate::search_space::{SearchSpace, GuidedSpace, PartialNeighborGeneration};
use crate::search_algorithm::{SearchAlgorithm, StoppingCriterion};

/**
implements a partial expansion greedy algorithm
*/
#[derive(Debug)]
pub struct PEGreedy<N, B, G, Tree> {
    /// search manager
    pub manager: SearchManager<N, B>,
    tree: Rc<RefCell<Tree>>,
    g: PhantomData<G>,
}

impl<N:Clone, B:PartialOrd+Copy, G, Tree> PEGreedy<N, B, G, Tree> {
    /** builds the partial expansion greedy using the search space */
    pub fn new(tree: Rc<RefCell<Tree>>) -> Self {
        Self {
            manager: SearchManager::default(),
            tree,
            g: PhantomData,
        }
    }
}

impl<'a, N, B, G:Ord+Clone, Tree> SearchAlgorithm<N, B> for PEGreedy<N, B, G, Tree>
where
    N: Clone,
    B: PartialOrd+Copy,
    Tree: SearchSpace<N,B> + GuidedSpace<N,G> + PartialNeighborGeneration<N>,
{

    fn run<SC:StoppingCriterion>(&mut self, stopping_criterion:SC)
    where SC:StoppingCriterion,  {
        let mut space = self.tree.borrow_mut();
        let mut n = space.initial();
        while !stopping_criterion.is_finished() {
            // check if goal
            let is_goal = space.goal(&n);
            if is_goal {
                // compare with best
                let v = space.bound(&n);
                if self.manager.is_better(v) {
                    let n2 = space.handle_new_best(n);
                    self.manager.update_best(n2.clone(), space.bound(&n2));
                }
                break;
            }
            // if not, explore children until a feasible children is found
            let tmp;
            match space.next_neighbor(&mut n) {
                None => { break; },  // stop if no more children
                Some(c) => { tmp = c; }
            }
            n = tmp;
        }
        space.stop_search("".to_string());
    }


    fn get_manager(&mut self) -> &mut SearchManager<N, B> { &mut self.manager }

    /**
     * returns true if the optimal value is found (thus we can stop the search).
     * For this greedy, we set it to always false (it is not destined to prove optimality)
     */
    fn is_optimal(&self) -> bool { false }
}