CSCE 420 Lecture 8

From Notes
Jump to navigation Jump to search

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


Constraint Satisfaction Problems (CSP)

  • Set of variables, say Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} through Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n}
  • finite domains, say Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ v_1, \ldots, v_m \}}
  • constraints: limits on combinations of choices:
    • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = 2 x_2}
    • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i \ne x_j}
    • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} is even, i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 \equiv 0 \pmod{2}}

Extensional definition of binary constraints

  • Involves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_j}
  • Allowed combinations is a subset of dom(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} ) × dom(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_j} )

Constraint Graph

  • Nodes = edges
  • Edges = binary constraints

Multivariable Constraints

  • Subset of tuples from cross products of all domains: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \{1,2,3\}}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in \{1,2,3\}}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z \in \{1,2,3\}}

constraints:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x + y + z = 5}
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y}
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y < z}

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

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = u_1}
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = u_2}
  4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_420_Lecture_8&oldid=7686"