Transcript +MORE

Constraint Satisfaction
R & N Chapter 5
Constraint Satisfaction – Early Use
From http://www-2.cs.cmu.edu/~awm/731/constraint07-2x2.pdf
The Waltz Algorithm
More on Waltz Algorithm
The constraints come from the fact that a line must have the
same label at both ends.
Crossword Puzzles
Latin Squares
Using only the numbers 1, 2, 3, and 4, arrange four sets of
these numbers into a four-by-four array so that no column or
row contains the same two numbers. The result is known as a
Latin square.
Here are two examples of Latin squares of order 4:
1
2
3
4
1
2
3
4
2
1
4
3
3
4
1
2
3
4
1
2
4
3
2
1
4
3
2
1
2
1
4
3
http://www.sciencenews.org/20000506/mathtrek.asp
Satisfiability
(P  Q  S) 
(A   Q  B) 
(P   B  C) 
( A  B  C) 
(Q  A  C)
Example applications:
Real Examples
Scheduling
What else?
Algorithms for CSPs
•Branching
State space: usually incremental formulation
•Straight line
State space: usually complete-state formulation
Cryptarithmetic
SEND
+MORE
MONEY
PEAS description:
State space when formulated as a CSP: variables, domain,
constraints
•Incremental state space formulation:
•Complete state formulation:
Cryptarithmetic
Representing the constraints:
As formulas:
As a graph:
Using special constraints: Alldiff
SEND
+MORE
MONEY
Cryptarithmetic – Best First Search
M=1
M=2
SEND
+MORE
MONEY
Cryptarithmetic – Best First Search
M=1
M=2
M=1
S=2
O =3 …
SEND
+MORE
MONEY
Cryptarithmetic – Branching Algorithms
•Backtracking
•Minimum remaining values
•Degree heuristic
•Least-constraining value
M=1
M=2
SEND
+MORE
MONEY
Cryptarithmetic – Constraint Propagation
Forward checking: After assigning a value to a variable X,
look at all the variables connected to X and prune inconsistent
values.
Constraint propagation using arc consistency:
The tradeoff: how much time to spend propagating vs.
searching.
SEND
+MORE
MONEY
Backtracking – Chronological vs.
Dependency Directed
Straight-Line Algorithms: Min-Conflicts
function Min-Conflicts(csp, max_steps) returns a solution or failure
inputs: csp, a constraint satisfaction problem
max_steps, the number of steps allowed before giving up
current  an initial assignment for csp
for i = 1 to max_steps do
if current is a solution for csp then return current
var  a randomly chosen, conflicted variable from Variables[csp]
value  the value v for var that minimizes Conflicts(var, v, current, csp)
set var = value in current
return failure
Do Straight-Line Algorithms Work?
Does Min-Conflicts work?
From: http://www.cs.mu.oz.au/303/slides/week03ah.pdf
Do Straight-Line Algorithms Work?
Another Win of Straight Line Algorithms
They can be used to perturb a solution that ceases to be correct:
Most scheduling problems