Generate and Test
Theexhaustivegenerate‐and‐testalgorithmistogenerateall the complete assignments, then test them in turn, and return the first one that satisfies all of the constraints.
It needs to store all complete assignments, where is the domain size and is the number of variables.
Sowemustfindalternativemethods.
Solving CSPs by standard search formulation
InCSPs,statesdefinedbythevaluesassignedsofar(partial assignments)
Initial state: the empty assignment {}.
Successor function: assign a value to an unassigned variable.
Goal test: if the current assignment is complete and satisfies all the constraints.
Solving CSPs by BFS
Example:TherearethreevariablesA,B,andC,allwithdomain {0, 1, 2}. The constraint is A+B+C=1.
Sincethesolutionarealwaysinthebottomlayer,BFSneedsto traverse all the nodes (partial assignments).
C=0 C=1 C=2
……
A=0 A=1 A=2 B=0 ……
ABC A+B+C=1
B=0 B=1 B=2 C=0
……
Not a good idea!
Solving CSPs by DFS
Example:TherearethreevariablesA,B,andC,allwith domain {0, 1, 2}. The constraint is A+B+C=1.
Soundsagoodidea,butwhatiftheconstraintisA>B>C? ABC
C=0 C=1
We need to consider constraints as we go!
B=0
……
A=0
……
A+B+C=1
Backtracking Search
Backtracking is a DFS method with two additional things: 1) Check constraints as you go and 2) Consider one variable at a layer.
Example:therearethreevariables A, B, and C, all with domain {0, 1, 2}. The constraint is A
WhenAisassigned0,domainsofitsneighboursBandCare reduced, so it is quick to know this assignment is not legal (as C is empty now).
A {0,1,2}
A=0
BC {0,1,2} {0,1,2}
BC {1,2} {}
Ordering
Considerminimumremainingvalues,i.e.,choosethe variable with the fewest legal values left in its domain.
Example:TherearethreevariablesA,B,andC,allwith domain {0, 1, 2}. The constraint is .
OnceAisassigned0,afterforwardcheckingCwillbe assigned since its domain is smaller than B’s domain.
Alsocalled“mostconstrainedvariable”or“fail‐fast”ordering
A {0,1,2}
A=0 A=0
BCBCB {0,1,2} {0,1,2} {0,1,2} {1,2} {0}
C=1
Example: Backtracking + Forward Checking + Ordering
Example:TherearethreevariablesA,B,C,allwithdomain {0, 1, 2}. The constraints: and . Tie is broken alphabetically/numerically.
A=0 A+B+C=3
A=0 A+B+C=3
Order of states to be visited: A=0 => C=1 => C=2 => B=1
A=0
A+B+C=3
A+B+C=3 BC
{0,1,2}
{1,2}
B C=1 B C=2 {} {1}
A {0,1,2}
BC {0,1,2} {0,1,2}