csp by symmetrical search

Question 1

what is the generate and test algorithm

Answer 1

generating all possibe solutions and then testing the solutions, returns the correct solution that satisfies all the constraints
It needs to store all 𝑑𝑛 complete assignments, where 𝑑 is the
domain size and 𝑛 is the number of variables

Question 2

describe solving the csp by the standard search function:
what is intial state, successor function and goal state

Question 3

can we solve csp by breadth first search

Answer 3

not ideal - solutions will be at the bottom of the tree/search will have to search through the entire tree and traverse through all the nodes

Question 4

can we solve csp by depth first search

Answer 4

better then bfs but have to take constraints into account
so you have to check constraints as you go
Consider only values which do not conflict previous assignments.
May have to do some computation to check the constraints,
like “Incremental goal test

Question 5

what is backtracking

Answer 5

Backtracking is a DFS method with two additional things: 1) Check
constraints as you go and 2) Consider one variable at a layer
commutative so fix ordering

Question 6

how to improve backtracking

Answer 6

General-purpose ideas give huge gain in speed
◆ Two ideas:
◆ Filtering: Can we detect inevitable failure early
◆ Ordering: Which variable should be assigned next

Question 7

what is filtering

Answer 7

detecting inevitable failure early
keep track of unassigned domains and cross off bad options
many different ways of filtering

Question 8

name one way of filtering in backtracking

Answer 8

foward checking

Question 9

what is foward checking

Answer 9

Forward Checking: cross off values of neighbouring
variables that violate a constraint when added to the
existing assignment. That is, when assign a variable, cross
off anything that is now violated on all its neighbours’
domains

Question 10

what is ordering

Answer 10

considering value with minimum remianing values to store