CSCE 420 Lecture 9

« previous | Tuesday, February 12, 2013 | next »

CSP

Backtracking

Choose random variable, set it to random value, and continue with remaining variables/values until constraint is violated (backtrack) or no variables remain (complete)

Forward Checking

Every time we make a choice (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 = v_i} ), we remove inconsistent values from domain of "neighboring" (in constraint graph) variables.

Constraint-Propagation: update the remaining choices of other nodes, and backtrack if any node has no choices left in domain.

Take advantage of heuristics by changing order of variables and values

Minimum Remaining Values (MRV): Choose variable with fewest values remaining in domain; thereby reducing effective branching factor
Least Constraining Value (LCV): Choose value that has least effect on neigboring variables

Arc-Consistency

A constraint graph is arc-consistent if for every edge 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,x_j)} and for every value in the domain of 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} , there is some value 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_j} in the domain of 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} that is consistent

For example, the following graph is arc-consistent:

          X1 != X2
X1(0,1) ------------ X2(0,1)
  |
  | X1 != X3
  |
X3(0,1)

and the following graph is not:

          X1 != X2
X1(0,1) ------------ X2(0,1)
  |
  | X1 != X3
  |
X3(1)

Algorithm: AC-3

Makes a graph arc-consistent by mantaining a queue of edges for the graph

def ac3 csp, start_node = nil
  queue = start_node.nil? ? csp.graph.nodes[start_node].neighbors : Queue.new(csp.graph.edges)
  until queue.empty?
    edge = queue.pop
    # remove value v_i from csp.domain[edge.source] that do not have consistent choice in csp.domain[edge.domain]
    return false if csp.domain[edge.source].empty? # inconsistent
    edge.source.neighbors.each { |neighbor| queue.push Edge.new(neighbor, edge.source) }
  end

  return true # reduced domains
end

AC-3 does not solve constraint satisfaction problem, but it can be used:

as a preprocessing agent (before search)
interleaved between choice selections during search (Make Arc-Consistent (MAC))

Algorithm: Make Arc-Consistent

Time complexity

$O(n^{2}\,d)$ , where $n$ is the number of variables and $d$ is the max domain size.

Also depends on number of constraints (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 O(n^2)} ), so running time may actually be 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 O(n^4)}

BUT CSP IS NP-COMPLETE!?

MAC: Four Queens Problem

Pass 0: AC3 does nothing; complete constraint graph
C = 3
Pass 1:
    init queue (A,C), (B,C), (D,C)
    pop (A,C) -- dom(A) \= {1,3}      (note: \= is 'set-minus equal')
    push (B,A), (C,A), (D,A)
    pop (B,A) -- dom(B) \= {3}
    push (A,B), (C,B), (D,B)
    pop (A,B) -- no change
    pop (C,B) -- already done
    pop (D,B) -- no change
    pop (C,A) -- already done
    pop (D,A) -- already done
    pop (B,C) -- dom(B) \= {2,4}
    push (A,B), (C,B), (D,B)
    ...
    pop (D,C)
    ...
    return false
C = 4
Pass 2:
...