- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Nondeterministic control for hybrid search implemented in Scala into Scampi Solver
Mon, 2012-02-13, 21:01
Nondeterministic control for hybrid search where introduced in a paper
by Pascal Van Hentenryck and Laurent Michel (Constraints Journal,
2006).
This kind of search is the most elegant one never invented to solve
constraint programming problems.
We were able to implement it in Scampi (Constraint Programming Solver
in Scala) thanks to the continuations available in Scala.
Here is a small example:
val cp = CPSolver()
val v = Array.tabulate(3)(i => new ReversibleBool(cp))
cp.exploration {
cp.branch { v(0).setValue(true) }
{ v(0).setValue(false)}
cp.branch { v(1).setValue(true) }
{ v(1).setValue(false)}
cp.branch { v(2).setValue(true) }
{ v(2).setValue(false)}
println(v.mkString(","))
nb += 1
}
println(nb)
Will make a DFS exploration and output
true,true,true
true,true,false
true,false,true
true,false,false
false,true,true
false,true,false
false,false,true
false,false,false
nb:8
If you are interested to see more about it, have a look here:
https://bitbucket.org/pschaus/scampi/wiki/search