Constraint Satisfaction

Challenge Question

https://dl.dropbox.com/s/jshq91z8qkpgle7/Screenshot%202017-03-05%2019.49.10.png

  • Backtracking

  • Forward Checking

  • Minimum Remaining Values (MRV)

  • Least Constraint Value.

Map Coloring

https://dl.dropbox.com/s/64nvvjeys0l9cxm/Screenshot%202017-03-05%2019.51.18.png https://dl.dropbox.com/s/c2pp2m8ucxpjely/Screenshot%202017-03-05%2019.51.50.png

Constraint Graph

https://dl.dropbox.com/s/r9y9obplq8r9hdi/Screenshot%202017-03-05%2019.52.47.png

  • The nodes are the variables.

  • ARCs show the constraints between the variables.

Map Coloring Quiz

https://dl.dropbox.com/s/f9atvvr680n4i35/Screenshot%202017-03-05%2019.54.10.png

CSP Examples

  • Preferences Constraints are called - Optimization Problem.

  • Solved using Linear Programming.

Constraint Hypergraph

https://dl.dropbox.com/s/fe9cugk4zfoxh1o/Screenshot%202017-03-05%2019.59.24.png

Improving Backtracking Efficiency

https://dl.dropbox.com/s/9zop2vf2cs9hw1k/Screenshot%202017-03-05%2020.04.07.png

  • Orange was the value that least constrainted the future choices.

https://dl.dropbox.com/s/4hzt06su55wq33a/Screenshot%202017-03-05%2020.10.53.png

  • The variable with the least number of values remaining is south australia, so we assign that next.

  • When there is a tie, use degree heuristic. Choose the variable with the most constraints on remaining variables.

https://dl.dropbox.com/s/o9kw0u2ridptwqv/Screenshot%202017-03-05%2020.12.51.png https://dl.dropbox.com/s/6bzo1ssa7yiww6p/Screenshot%202017-03-11%2013.22.02.png?dl=0

Forward Checking

https://dl.dropbox.com/s/33ajsgbb4jz5tbr/Screenshot%202017-03-05%2020.16.18.png

  • Forward Checking is an early warning system to that helps us notify that our search is going in the wrong direction.

Constraint Propagation And Arc Consistency

https://dl.dropbox.com/s/iv719mc5o7nloev/Screenshot%202017-03-05%2020.23.35.png

  • What is ARC Consistency?

Constraint Propagation Quiz

https://dl.dropbox.com/s/s51m6psst1equ1t/Screenshot%202017-03-05%2020.24.28.png

Structured CSPs

https://dl.dropbox.com/s/v9cqnlknyt1wm81/Screenshot%202017-03-05%2020.26.34.png

  • Break it down into smaller problems.

https://dl.dropbox.com/s/jamhr59wo9q1pz8/Screenshot%202017-03-05%2020.29.27.png

  • If we have CSP with no loops, we can solve the problem in \(O(nd^2)\) times.

  • Topological Search

https://dl.dropbox.com/s/81f4wmojuaqpn2h/Screenshot%202017-03-05%2020.30.02.png

Iterative Algorithms

https://dl.dropbox.com/s/sfgrwch7yvuv8zt/Screenshot%202017-03-05%2020.31.13.png

  • MinConflict Algorithm illustration.

Challenge Question

https://dl.dropbox.com/s/ehrw30viveda41w/Screenshot%202017-03-05%2020.32.38.png