Week 2 - CSPs

Question 1

What 5 things make up a search problem?

Answer 1

State Space
Start State
Goal State
Goal Test
Successor function

Question 2

What is a solution for a search problem?

Answer 2

A sequence of actions which transforms the start state to a goal state.

Question 3

What 3 things make up a constraint satisfaction problem?

Answer 3

A set of variables
A domain of possible values for each variable
A set of constraints

Question 4

What is backtracking search for solving CSPs?

Answer 4

A depth first search method that considers one variable at a layer and only considers states which do not conflict with previous assignments.

Question 5

How is ordering used to speed up solving a CSP?

Answer 5

The next variable you consider is the variable with the fewest possible values.

Question 6

How is forward checking used to speed up solving a CSP?

Answer 6

When you assign a variable, cross of any neighbours that are now violated.

Question 7

Describe the local search algorithm for solving CSPs

Answer 7

Randomly generate a complete assignment
While constraints are violated:
- Randomly select a constraint violating variable
- Choose a new value that violates the least number of constraints