COMP 424 – Artificial Intelligence Solving Constraint Satisfaction Problems
Instructors: Jackie CK Cheung and Readings: R&N Ch 6 (3rd or 4th ed)
Preview: Inference to Solve Sudoku
Copyright By PowCoder代写 加微信 powcoder
• We don’t need to try values one cell at a time
Constraint satisfaction problems (CSPs)
• A CSP is defined by:
• Set of variables Vi, that can take values from domain Di
• Set of constraints specifying what combinations of values are allowed (for subsets of variables, eg. pairs of variables)
• Constraints can be represented:
• Implicitly, as a function, testing for the satisfaction of the constraint.
E.g. C1C2
• Explicitly, as a list of allowable values. E.g. (C1=R, C2=G), (C1=G, C2=R),
(C1=B, C2=R), …
• A CSP solution is an assignment of values to variables such that all the constraints are true.
• We typically want to find any solution or find that there is no solution.
Backtracking search
At each step, pick a remaining unassigned variable at each level of search tree, then pick a value for that variable
• This way, b=|Di|
Algorithm:
• Select an unassigned variable, X.
• For each value={x1,…, xn} in the domain of that variable
• If the value satisfies the constraints, let X = xi and exit the loop.
• If an assignment was found, move to the next variable.
• If no assignment, go back to preceding variable and try different
• This is the basic uninformed algorithm for CSPs. • Can solve n-queens for n ≈ 25.
How to Solve CSPs?
General strategies:
• Constructive methods (e.g., backtracking search)
• Local search
• Inference
• Prune the domains of the variables by using the constraints that those variables are involved in
Recall Example
• Colour a map so that no adjacent territories have the same colour.
Data Structure: Constraint graph
• Nodes are variables, arcs show constraints
• Graph structure can be exploited to accelerate solution
E.g. Map colouring:
Using constraint graph
• Perform inference using constraint graph in order to reduce search space
• Idea: Pre-process the graph before running a search algorithm to remove obvious inconsistencies
• E.g., Two variables: A, B
dom(A) = dom(B) = {1, 2, 3}
Constraint: A < B
Inference step: A cannot be 3 and B cannot be 1
Arc Consistency
• A variable is arc consistent if every value in its domain satisfies that variable’s binary constraints (i.e., those with one other variable).
• A variable is generalized arc consistent if every value in its domain satisfies that variable’s n-ary constraints (with n-1 other variables).
• A network is arc consistent if all of its variables are simultaneously arc consistent.
Example: consistency constraints
A CSP with variables A, B, C, each with domain {1, 2, 3, 4}:
ACS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com