Constraint satisfaction Flashcards

1
Q

What is backtracking search?

A
  • Algorithm for solving constraint satisfaction problems

-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Structured CSPS

A
  • Divide problems into smaller problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly