CSPs by local search

Question 1

describe tree search (symmetric search)

Answer 1

systematically search the space of
assignments in a constructive way.
◆ Start with an empty assignment.
◆ Assign a value to an unassigned variable and deal with constraints on
the way until a solution is found

Question 2

why would we decide to use local search method

Answer 2

if soace is too big or infinte , may fail to consider space so we may not get te answer we desire

Question 3

describe local search methods

Answer 3

systematically search environment , find solutions on averagesystematically seraches space but designed to find solution quickly on average
starts with an arbtrary complete assigments, constranits can be violated
works through assignment iteratively to improve it

Question 4

how to do a local search

Answer 4

◆ A typical local search algorithm (i.e. hill climbing for CSPs):
◆ Randomly generate a complete assignment
◆ When a solution not found or stop criterion not met,
iteratively perform the following two steps; otherwise
return the assignment.
◆ Step 1: Explore all the neighbours of the assignment (i.e., try
every assignment that only has one variable difference from the
considered assignment).
◆ Step 2: Choose the assignment that violates the fewest
constraints

Question 5

is local search always guaranteed to find a solution

Answer 5

can get stuck depending on problem’s landscape and serach strategy