local search algorithms for CSP's

Question 1

CSP local search

Answer 1

assume an assignment is inconsistent
the next assignment can be constructed in such a way that constraint violation is smaller
-only “small” changes of the assignment are allowed
-next assignment should be “better” than previous
–better=more constraints are satisfied
-assignments are not necessarily generated systematically
–we lose completeness but we hopefully get better efficiency

Question 2

local search terminology

Answer 2

search space S
set of solutions Sol
neighboring relation
evaluation function
initialization function
step function
set of memory states
termination criterion

Question 3

search space S

Answer 3

set of all complete variable assignments

Question 4

set of solutions Sol

Answer 4

subset of the search space

all assignments satisfying all the constraints

Question 5

neighborhood relation

Answer 5

a subset of SxS indicating what assignments can be reached by a search step given the current assignment during the search procedure

Question 6

evaluation function

Answer 6

mapping each assignment to a real number representing “how far the assignment is from being a solution”

Question 7

initialization function

Answer 7

returns an initial position given a possibility distribution over the assignments

Question 8

step function

Answer 8

given an assignment, its neighborhood and the evaluation function returns the new assignment to be explored by the search

Question 9

set of memory states(optional)

Answer 9

holding information about the state of the search mechanism

Question 10

termination criterion

Answer 10

stopping the search when satisfied

Question 11

CSP neighborhood of an assignment

Answer 11

all assignments differing on one the value of one variable (1-exchange-neighborhood)

Question 12

CSP evaluation function

Answer 12

mapping each assignment to the number of constraints it violates

Question 13

CSP initialization function

Answer 13

returns an initial assignment chosen randomly

Question 14

CSP termination criterion

Answer 14

if a soln is found or if a given number of search steps is exceeded

Question 15

CSP Hill Climbing

Answer 15

the basic technique of local search

• starts at randomly generated assignment
• at each state of the search
• iterative best improvement
• iterative first improvement
• if multiple choices choose one randomly
• neighborhood= differs in the value of any variable

Question 16

iterative best improvement:

Answer 16

move to the assignment in the neighborhood violating the minimum number of constraints

Question 17

iterative first improvement

Answer 17

choose the first improving neighbor in a given order