Please enable JavaScript.
Coggle requires JavaScript to display documents.
Constraint Satisfaction, Constraint satisfaction problem (CSP), Inference,…
Constraint Satisfaction
you just want the goal
assignments to variables
sometimes all paths have the same depth
constraint stisfaction is specialized search for such problems
Constraint satisfaction problem (CSP)
Informal description
formal representation language for states
problem solving for subet of search problems
useful, general purpose algorithms with more power than standard search algorithms
assume / given
finite set of variables
each with a domain of possible values
constraints that restrict values variables can have at the same time
solution
assigns a value to each variable in the domain that all the constraints are satisfied
often natural representation for problems, easy to formulate, fast to prune
formal definition
CSP
<X, D, C>
X = set of variables
D = associated domains of possible values
C = set of constraints
Constraint (scope, rel)
scope = the variables that you are talking about
rel = the relations that you can talking about
Carteasian product
Arity of a constraint is |scope|
unary onstraint
arity = 1
binary constraint
arity = 2
Constraint graph
Binary CSP
only has one unary and binary constraints
any non-binary CSP can be converted into a binary CSP
the graph or constraint network
represents a binary CSP
one node for each bariable
one edge between two nodes iff constraints between them
Assignments
search assigns values to variables of sum subset from their respective domains
partial assignment
complete assignment
consistent assignment
violates no constraints
solution = consistent, complete assignment
Constraints
constraint type
disjunctive constraints
includes a logical or
resource constraints
reference implicit source
arithmetic constraints
with respect to constants
x1 < 3
Temporal constraints
with respect to time
do one before the other
global constraints
apply to any nnumber of variables, often easier to write and have special , more efficent enforcement algorithms
Soft contraints
constraint optimization problems
Properties of constarints
represents explicitly as set of permissible or forbidden tuples,
implicitly as function of scope
partical information
non directional
declaritive
all you gotta do is specify
additive
can be satisfied in any orde
rar
rarely independent
possible problems
Domain fininte and discrete
but even boolean CSPs are NP-complete
Domain infinite
requires implicit representation
for constraints as linear explressions
if constrains are non linear and x is integer variables
p is undecidable
domain are continuous
operations research (real-world) problem
if domains are continuous and constraints is linear equalities or inequalities
COP (constrained optimization problem) = CSP with preference constraints
there are more ways
random stuff
back tracking solves any CSP
in reality search space is too large
there are ways to speed search up
THERES A LIST TO WRITE DOWN
Inference
arc consistency
AC-3 most popular arc consistency
you can have path consistency where you go down more edges
this leads to k-consistensy where you go up to any number
solution
facored representation
constraint propagation
reduces domains of assigned bariables to be consistent
Factored states bring power to CSP search
forward something
Backtracking
Issues
linear space
exponential time
trashing
you keep trying the same failure
can be inefficent
sodoku
purely generate and test is inefficent
apply constraints during search
naive tree searching on CSP
all the solutions are on the same depth
the path is irrelevant
harder games drive better algorithms