Constraint Satisfaction ProblemsConstraint satisfaction problems (CSPs)Example: Map-ColoringSlide 4Constraint graphVarieties of CSPsVarieties of constraintsExample: CryptarithmeticStandard search formulationBacktracking (Depth-First) searchBacktracking exampleSlide 12Slide 13Slide 14Improving backtracking efficiencyWhich variable should be assigned next? minimum remaining values heuristicWhich variable should be assigned next? degree heuristicIn what order should its values be tried? least constraining value heuristicRationale for MRV, DH, LCVCan we detect inevitable failure early? forward checkingForward checkingSlide 22Slide 23Slide 24Slide 25Constraint propagationArc consistencySlide 28Slide 29Slide 30Arc ConsistencyConstraint Propagation AlgorithmTry it yourselfSlide 34Slide 35Slide 36Junction Tree DecompositionsLocal search for CSPsExample: 4-QueensHard satisfiability problemsSlide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Summary1Constraint Satisfaction ProblemsChapter 5Section 1 – 32Constraint satisfaction problems (CSPs)CSP:state is defined by variables Xi with values from domain Digoal test is a set of constraints specifying allowable combinations of values for subsets of variablesAllows useful general-purpose algorithms with more power than standard search algorithms3Example: Map-ColoringVariables WA, NT, Q, NSW, V, SA, T Domains Di = {red,green,blue}Constraints: adjacent regions must have different colorse.g., WA ≠ NT4Example: Map-ColoringSolutions are complete and consistent assignments, e.g., WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green5Constraint graphBinary CSP: each constraint relates two variablesConstraint graph: nodes are variables, arcs are constraints6Varieties of CSPsDiscrete variablesfinite domains:n variables, domain size d O(d n) complete assignmentse.g., 3-SAT (NP-complete)infinite domains:integers, strings, etc.e.g., job scheduling, variables are start/end days for each job: StartJob1 + 5 ≤ StartJob3Continuous variableslinear constraints solvable in polynomial time by linear programming7Varieties of constraintsUnary constraints involve a single variable, e.g., SA ≠ greenBinary constraints involve pairs of variables,e.g., SA ≠ WAHigher-order constraints involve 3 or more variables,e.g., SA ≠ WA ≠ NT8Example: CryptarithmeticVariables: F T U W R O X1 X2 X3Domains: {0,1,2,3,4,5,6,7,8,9} {0,1}Constraints: Alldiff (F,T,U,W,R,O)O + O = R + 10 · X1X1 + W + W = U + 10 · X2X2 + T + T = O + 10 · X3X3 = F, T ≠ 0, F ≠ 09Standard search formulationLet’s try the standard search formulation.We need:• Initial state: none of the variables has a value (color)• Successor state: one of the variables without a value will get some value.• Goal: all variables have a value and none of the constraints is violated.N! x D^NN layersWA NT TWA WAWANTWANTWANTNxD[NxD]x[(N-1)xD]NTWAEqual!There are N! x D^N nodes in the tree but only D^N distinct states??10Backtracking (Depth-First) searchWAWA WAWANTWANTDD^2• Special property of CSPs: They are commutative: This means: the order in which we assign variables does not matter.• Better search tree: First order variables, then assign them values one-by-one. WANTNTWA=WANTD^N11Backtracking example12Backtracking example13Backtracking example14Backtracking example15Improving backtracking efficiencyGeneral-purpose methods can give huge gains in speed:Which variable should be assigned next?In what order should its values be tried?Can we detect inevitable failure early?We’ll discuss heuristics for all these questions in the following.16Which variable should be assigned next? minimum remaining values heuristicMost constrained variable:choose the variable with the fewest legal valuesa.k.a. minimum remaining values (MRV) heuristicPicks a variable which will cause failure as soon as possible, allowing the tree to be pruned.17 Which variable should be assigned next? degree heuristicTie-breaker among most constrained variablesMost constraining variable:choose the variable with the most constraints on remaining variables (most edges in graph)18 In what order should its values be tried? least constraining value heuristicGiven a variable, choose the least constraining value:the one that rules out the fewest values in the remaining variablesLeaves maximal flexibility for a solution.Combining these heuristics makes 1000 queens feasible19Rationale for MRV, DH, LCV In all cases we want to enter the most promising branch, but we also want to detect inevitable failure as soon as possible.MRV+DH: the variable that is most likely to cause failure in a branch is assigned first. The variable must be assigned at some point, so if it is doomed to fail, we’d better found out soon. E.g X1-X2-X3, values 0,1, neighbors cannot be the same. LCV: tries to avoid failure by assigning values that leave maximal flexibility for the remaining variables. We want our search to succeed as soon as possible, so given some ordering, we want to find the successful branch.20 Can we detect inevitable failure early? forward checkingIdea: Keep track of remaining legal values for unassigned variables that are connected to current variable.Terminate search when any variable has no legal values21Forward checkingIdea: Keep track of remaining legal values for unassigned variablesTerminate search when any variable has no legal values22Forward checkingIdea: Keep track of remaining legal values for unassigned variablesTerminate search when any variable has no legal values23Forward checkingIdea: Keep track of remaining legal values for unassigned variablesTerminate search when any variable has no legal values24cadebCONSTRAINT GRAPH2) Consider the constraint graph on the right.The domain for every variable is [1,2,3,4].There are 2 unary constraints:- variable “a” cannot take values 3 and 4.- variable “b” cannot take value 4.There are 8 binary constraints stating that variables connected by an edge cannot have the same value.a) [5pts] Find a solution for this CSP by using the followingheuristics: minimum value heuristic, degree heuristic, forward checking. Explain each step of your answer.25cadebCONSTRAINT GRAPH2) Consider the constraint graph on
View Full Document
Unlocking...