CSCE 420 Lecture 8

« previous | Thursday, February 7, 2013 | next »

Constraint Satisfaction Problems (CSP)

• Set of variables, say $x_{1}$ through $x_{n}$
• finite domains, say $\{v_{1},\ldots ,v_{m}\}$
• constraints: limits on combinations of choices:
  • $x_{1}=2x_{2}$
  • $x_{i}\neq x_{j}$
  • $x_{1}$ is even, i.e. $x_{1}\equiv 0{\pmod {2}}$

Extensional definition of binary constraints

• Involves $x_{i}$ and $x_{j}$
• Allowed combinations is a subset of dom($x_{i}$) × dom($x_{j}$)

Constraint Graph

• Nodes = edges
• Edges = binary constraints

Multivariable Constraints

• Subset of tuples from cross products of all domains: $C\subset \prod _{j=1}^{m}\mathrm {dom} (x_{j})$

Converting Multivariable Constraints to Binary Constraints

If a constraint depends on more than two variables, we introduce a new variable whose domain consists of tuples. Each component corresponds to a variable, and the values represent consistent combinations of the domain of other variables.

Edges specify dependence of elements with their target variables.

Example

Given the constraint satisfaction problem among X, Y, and Z, we introduce another variable U with domain dom(U) ⊆ dom(X) × dom(Y) × dom(Z). The resulting binary constraint graph is visible at right.

Binary constraint graph for this example

domains:

• $x\in \{1,2,3\}$
• $y\in \{1,2,3\}$
• $z\in \{1,2,3\}$

constraints:

1. $x+y+z=5$
2. $x<y$
3. $y<z$

We introduce a third variable U to represent the tertiary constraint in (1), and the corresponding constraints with other variables.

1. $u\in \left\{(x,y,z)~\mid ~x,y,z\in \{1,2,3\},\ x+y+z=5\right\}=\left\{(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)\right\}$
2. $x=u_{1}$
3. $y=u_{2}$
4. $z=u_{3}$

Map Coloring

No adjacent regions can have the same color

Australia, for example, has the following states:

• Western Australia
• Northern Territory
• Victoria
• New South Wales
• South Australia
• Tasmania
• Queensland

Variables are states: { WA, NT, V, NSW, SA, T, Q }
Domain of each variable is colors: { R, G, B }

Extensional binary constraints:

• WA ≠ NT: { (R,G), (R,B), (G,R), (G,B), (B,R), (B,G) }

Sudoku

No digits may be repeated in any row, column, or section

Variables are cells
Domain of each cell is digits 0–9

Other Problems

• Crossword Puzzles
• Time scheduling

CSP Algorithms

Search space = partial assignments. Goal is a set of complete assignments (all variables have a value) that satisfies all constraints

Operator: choose value for unassigned variable

• When generating children, we can see whether chosen assignment violates constraints and prune that part of the decision tree.

Back Tracking

def backtrack(csp, assignment = {})
  # check completeness of assignment
  return assignment if assignment.size == csp.vars.size and csp.constraints.all { |c| c(assignment) }

  # select variable
  var = (csp.vars - assignment.keys).sample

  csp.domain[var].each do |value|
    if csp.constraints.all { |constraint| constraint(assignment) }
      assignment[var] = value
      result = bt(csp, assignment)
      return result if result
      assignment.delete(var)
    end
  end

  # return failure if no assignments were found
  false
end

Not very efficient

Next Time

• Minimum remaining values (MRV)
• Least constraining value (LCV)
• Forward Checking