Constraint Satisfaction¶
Challenge Question¶
- Backtracking
- Forward Checking
- Minimum Remaining Values (MRV)
- Least Constraint Value.
Map Coloring Quiz¶
CSP Examples¶
- Preferences Constraints are called - Optimization Problem.
- Solved using Linear Programming.
Constraint Hypergraph¶
Improving Backtracking Efficiency¶
- Orange was the value that least constrainted the future choices.
- 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.
Forward Checking¶
- Forward Checking is an early warning system to that helps us notify that our search is going in the wrong direction.
Constraint Propagation Quiz¶
Structured CSPs¶
- Break it down into smaller problems.
- If we have CSP with no loops, we can solve the problem in \(O(nd^2)\) times.
- Topological Search