Try โ€‚โ€‰HackMD

Week 3c - Constraint Satisfaction Problems II

Commutativity

  • In CSPs, variable assignments are commutative.
    • It doesn't matter which order you assign the variables
    • e.g. [WA=red then NT=green] == [NT=green then WA=red]
  • Only need to consider assignments to a single variable at each level/depth
    • Branching factor is the domain size d
    • We have
      dn
      leaves now instead of
      n!dn
      leaves

Overview

  • Backtracking Search is essentially like DFS for CSPs with single-variable assignments
    • Backtracking occurs when there are no legal values for a variable
    • Uses commutativity to reduce search from
      n!dn
      leaves to
      dn
      leaves
  • Backtracking search is the basic uninformed algorithm for CSPs

Algorithm

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

Example: Map Coloring

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

  • General-purpose methods can give huge gains in speed:
    • Which variable should be assigned next?
      • Idea 1: Min. remaining values
      • Idea 2: Degree heuristic
    • In what order should its values be tried?
      • Idea 3: Least constraining value
    • Can we detect inevitable failure early?
      • Idea 4: Forward checking / AC-3 Algorithm
    • Can we take advantage of problem structure?
      • Idea 5: Tree-structured CSPs

Minimum Remaining Values

  • Choose the variable with the fewest legal values, i.e., the most constrained variable
  • We choose the variable with the least remaining legal value, which means most likely to fail. If it fails early, we will ignore the entire branch and avoid wasting time.
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More โ†’

Degree Heuristic

  • What happens when multiple variables have the same MRV?
  • Degree Heuristic: Choose the variable with the most constraints on remaining variables (i.e. choose the variable that has the most impact on the domains of the other variables)
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More โ†’

Least Constraining Value

  • Given a variable, choose the least constraining value, i.e. the one that rules out the fewest values in the remaining variables
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More โ†’

    In the example above, using the principle of least constraining value, we will go with coloring the state red instead of blue, since it has more values left available for SA as opposed to 0.

Forward Checking

  • Keep track of remaining legal values for unassigned variables
    • Terminate search when any variable has no legal values
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More โ†’
  • Limitation of forward checking:
    • Forward checking propagates information from assigned to unassigned variables
      • However, it does not provide early detection for all failures
      • Hence, we need to repeatednly enforce constraints locally, i.e., constraint propagation
        Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More โ†’

Arc Consistency

  • Simplest form of propagation make each arc consistent
  • X โ†’ Y is consistent iff
    • For every value x of X there is some allowed y.
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More โ†’
  • If X loses a value, neighbors of X need to be rechecked if they are still arc consistent.
  • Arc consistency detects failure earlier than forward checking. It can be run as a preprocessor or after each assignment

Algorithm

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

Exercise: Application of AC-3

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

The ordering of arcs do not matter since it will still end up with one of the variables having no legal values remaining

Time Complexity of AC-3

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

Problem Structure

  • Tasmania and mainland are independent subproblems
  • Identifiable as connected components of constraint graph
  • Suppose each subproblem has c variables out of total n variables
  • Worst-case solution cost is
    (n/c)โ‹…dc
    , linear in n
    • e.g. n=80, d=2,c=20
      • 280
        = 4 billion years at 10m nodes/sec
      • broken down to 4 independent subproblems:
        4ร—220
        = 0.4 seconds at 10 million nodes/sec

Tree-structured CSPs

  • Theorem: if the constraint graph has no loops, the CSP can be solved in
    O(nd2)
    time
  • Compared to general CSPs, where worst-case time is
    O(dn)

Algorithm

  1. Choose a variable as root, order variables from root to leaves such that every node's parent precedes it in the ordering (this step is to order the graph as a tree)
  2. For j from n down to 2, apply RemoveInconsistent(Parent(Xj),Xj)
  3. For j from 1 to n, assign Xj consistently with Parent(Xj)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

Another example:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More โ†’

Nearly Tree-Structured CSPs

  • Conditioning: Instantiate a variable, prune its neighbors' domains
  • Cutset conditioning: instantiate (in all ways) a set of variables such that the remaining constraint graph is a tree
  • Cutset size c โ†’ runtime
    O(dcโ‹…(nโˆ’c)d2)
    , very fast for small c
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More โ†’