CSPs are a special kind of search problem
- States defined by values of a fixed set of variables from domain
- Goal test defined by constraints on variable values
- acceptable solutions are complete and consistent
- binary CSP: relates two variables; constraint graph: nodes are variables, arc are constraits.
- Discrete variable(n) with finit domain(d): O(d^n) complete assignments
- Discrete variable with infinit domain need a constraint
- Varieties of constraints: involve one varible(unary), two(binary), three(higher-order)
Backtracking
- depth-first search with one variable assigned at each level
- the basic uninformed algorithm for CSP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | function BacktrackingSearch(csp) return solution or failure return Backtrack({}, csp) function Backtrack(assignment, csp) return solution or failure # goal test if assignment is complete then return assignment # variable ordering/selection var = SelectUnassignedVariable(csp) # value ordering for each value in OrderDomainValues(var, assignment, csp) do if value is consistent with assignment then add {var=value} to assignment # inferences from current state inferences = Inference(csp, var, value) if inferences != failure then add inferences to assginment result = Backtrack(assignment, csp) if result != failture then return result remove {var=value} and inferences from assignment return failure |
improve serach efficiency
- Variable ordering
- Most constrained variable or Minimum remaining values (MRV): choose the variable with the fewest legal values
- Degree heuristic: has the most number of unassigned neighbors
- Value ordering
- Least-constraining-value: the one that rules out the fewest values in the remaining variables
- Constraint propagation(inferences in code)
- Forward checking prevents assignments that lead to later failures
- Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies early. based on X -> Y is consistent iff for every value x in X there is some allowed y in Y.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | function AC-3(csp) return boolean inputs: csp, a binary csp with components(X, D, C) local varibales: queue, a queue of arcs, initially all the arcs in csp while queue is not empty do (xi, xj) = RemoveFirst(queue) if Revise(csp, xi, xj) then if Di is empty then return false for each Xk in Xi.neighbours - Xi do add (Xk, Xi) to queue return true function Revise(csp, xi, xj) return true iff revise domain revised = false for each x in Dj do if no value y in Dj allows(X, y) then delete x from Di revised = true return revised |
Contents