Module | AI::CSP |
In: |
ai/csp.rb
ai/csp/backtracking.rb ai/csp/constraint.rb ai/csp/int.rb ai/csp/problem.rb ai/csp/variable.rb |
A Library for modeling and solving constraint satisfaction problems (CSPs).
A constraint satisfaction problem is defined in terms of a set of variables with domains (possible values for each of those variables) and constraints on those variables. Solving a CSP involves assigning values to each of the variables, such that all of the constraints are filled.
It turns out that this is a very natural way to model many problems with scheduling problems being the canonical example. Note that CSPs have been shown to be NP-complete, which means that solving one in polynomial time (as a function of the number of variables and the size of the domains) is infeasible in the general case. However with specialized constraint propagation specific instances can often be made tractable.
v1 = Variable.new(:v1, %w(red green blue yellow fuchsia)) v2 = Variable.new(:age, (18...50))
problem = Problem.new(variables) problem.add_constraint(:v1, :v2) {|a,b| a != b}
# solver that will use propagation and fail first DVO solver = Backtracking.new(true, FAIL_FIRST) solver.each_solution(problem) {|solution| # do something with solution, which is just the # original CSP with variables assigned values }
require 'ai/csp' include AI::CSP v1 = Variable.new(:v1, (0...10)) v2 = Variable.new(:v2, (0...15)) v3 = Variable.new(:v3, (0...15)) problem = Problem.new([v1, v2, v3]) # add user defined constraint problem.add_constraint(:v1,:v2,:v3) { |a,b,c| a+b == c } # add specialized constraint problem.add_constraint(AllDifferent.new(v1,v2)) solver = Backtracking.new solver.each_solution(problem) { |solution| puts solution }
Several slightly more realistic examples can be found in the examples directory.
Jonathan Sillito, sillito@gmail.com
Version | = | VERSION = '0.0.1' | ||
UNSET | = | nil | Value or a variable that is not instantiated | |
STATIC | = | 0 | Static variable ordering | |
FAIL_FIRST | = | 1 | Dynamic variable ordering: pick variable with smallest domain |