Constraint satisfaction Flashcards
1
Q
What is backtracking search?
A
- Algorithm for solving constraint satisfaction problems
-
2
Q
Improving backtracking search efficency
A
- Least constraining value: choose the variable (value) that rules out the fewest values in the remaining variables.
- Minimum remaining values: choose variable with the fewest legal moves
- Degree heuristic: choose the variable most constraints on remaining values
- ## Forward checking: For each unassigned variable keep track of its legal values. If we make a decision that leaves a variable no legal values stop search and backup
3
Q
Structured CSPS
A
- Divide problems into smaller problems