pcp/search/
mod.rs

1// Copyright 2015 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//     http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! The search explores a tree where nodes are a couple of variables and constraints store, called a *space*.
16
17//! The tree is constructed during the search and backtracking occurs when a node is failed (it does not lead to a solution). The exploration of the tree can be customized by different heuristics combined with *search combinators* implemented with `SearchTreeVisitor`.
18
19pub mod space;
20pub mod recomputation;
21pub mod branching;
22pub mod search_tree_visitor;
23pub mod propagation;
24pub mod engine;
25pub mod monitor;
26pub mod statistics;
27pub mod branch_and_bound;
28pub mod debugger;
29pub mod stop_node;
30
31pub use search::space::*;
32pub use search::search_tree_visitor::*;
33
34use propagation::CStoreFD;
35use variable::VStoreSet;
36use search::engine::one_solution::*;
37use search::branching::*;
38use search::propagation::*;
39use gcollections::VectorStack;
40
41pub type VStore = VStoreSet;
42type CStore = CStoreFD<VStore>;
43pub type FDSpace = Space<VStore, CStore, NoRecomputation<VStore, CStore>>;
44
45pub fn one_solution_engine() -> Box<dyn SearchTreeVisitor<FDSpace>> {
46  let search =
47    OneSolution::<_, VectorStack<_>, FDSpace>::new(
48    Propagation::new(
49    Brancher::new(FirstSmallestVar, MiddleVal, BinarySplit)));
50  Box::new(search)
51}
52
53#[cfg(test)]
54mod test {
55  pub use super::*;
56  use propagators::cmp::*;
57  use propagators::distinct::*;
58  use term::*;
59  use gcollections::ops::*;
60  use interval::interval_set::*;
61  use concept::*;
62
63  pub fn nqueens(n: usize, space: &mut FDSpace) {
64    let mut queens: Vec<Var<VStore>> = vec![];
65    // 2 queens can't share the same line.
66    for _ in 0..n {
67      queens.push(Box::new(space.vstore.alloc((1, n as i32).to_interval_set())));
68    }
69    for i in 0..n-1 {
70      for j in i + 1..n {
71        // 2 queens can't share the same diagonal.
72        let q1 = (i + 1) as i32;
73        let q2 = (j + 1) as i32;
74        // Xi + i != Xj + j
75        space.cstore.alloc(Box::new(XNeqY::new(queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), q2 - q1)))));
76        // Xi - i != Xj - j
77        space.cstore.alloc(Box::new(XNeqY::new(queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), -q2 + q1)))));
78      }
79    }
80    // 2 queens can't share the same column.
81    space.cstore.alloc(Box::new(Distinct::new(queens)));
82  }
83}
pcp/search/mod.rs

pcp/search/
mod.rs
