Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Constraint Satisfaction Problems (CSPS)

state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test

**CONSTRAINT SATISFACTION PROBLEMS
(CSPS)**

•
Standard search problem:

– state
is a "black box“ – any data structure that supports successor function,
heuristic function, and goal test

•
CSP:

– state is defined by variables *Xi* with values from domain *Di*

– goal
test is a set of constraints specifying allowable combinations of values for
subsets of variables

– Simple example of a formal representation
language

•
Allows useful general-purpose algorithms with more
power than standard search algorithms

__Arc
consistency:__

1.
Arc refers to a directed arc in the constraint
graph.

2.
Arc consistency checking can be applied either as a
preprocessing. step before the process must be applied repeatedly until no more
inconsistency remain.

__Path
consistency:__

Path
consistency means that any pair of adjacent variables can always be extended to
a third neighboring variable, this is also called path consistency

__K-consistency:__

Stronger
forms of propagation can be defined using the notation called K-consistency. A
CSP is K-consistency if for any set of K-1 variables and for any consistent
assignment to those variables, a constant value can always be assigned to any
variable.

*Example:
Map-Coloring*

•
Variables *WA,
NT, Q, NSW, V, SA, T*

•
Domains *Di*
= {red,green,blue}

•
Constraints: adjacent regions must have different
colors

e.g., WA
≠ NT, or (WA,NT) in ,(red,green),(red,blue),(green,red),
(green,blue),(blue,red),(blue,green)}

•
Solutions are complete and consistent assignments, e.g., WA = red, NT = green,Q
= red,NSW= green,V = red,SA = blue,T = green

Constraint
graph

•
Binary CSP: each constraint relates two variables

•
Constraint graph: nodes are variables, arcs are
constraints

*Varieties
of CSPs*

•
Discrete variables

– finite domains:

•
*n *variables,
domain size* d -O(d ^{n}) *complete assignments

•
e.g., Boolean CSPs, incl.~Boolean satisfiability
(NP-complete)

– infinite domains:

•
integers, strings, etc.

•
e.g., job scheduling, variables are start/end days
for each job

•
need a constraint language, e.g., *StartJob1 + 5* *≤* *StartJob3*

•
Continuous variables

– e.g., start/end times for Hubble Space
Telescope observations

– linear constraints solvable in polynomial
time by linear programming

*Varieties
of constraints:*

•
Unary constraints involve a single variable,

– e.g., SA ≠ green

•
Binary constraints involve pairs of variables,

– e.g., SA ≠ WA

– Higher-order constraints involve 3 or more
variables,

– e.g., cryptarithmetic column constraints

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.