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

Artificial Intelligence : Constraint Satisfaction Problems (CSPS) |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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