3-Constraint satisfaction problems

Question 1

1. backtracking search defini

Answer 1

Is a depth-first search for CSPs with single variable assignments
It chooses values for a not assigned variable at each level and backtracks when a variable has no legal values left ti assign.

Question 2

2. forward checking

Answer 2

Keep track of remaining legal values for unassigned variables and terminate search when a variable has no legal values.

Question 3

3.AC-3 algorithm

Question 4

4. what is c-semiring? and framework for soft CSPs

Answer 4

c-semiring is a set in which each assignment of values to its variables has an associated preference value.

soft csp framework: represented by a tuple <a>
A: set that specifies the preference values to be associated with each tuple, i.e. with each assignment of values of the variables.
+: model constraint projection
x: model constraint combination
𝟎: worst preference value (0 ∈ 𝐴)
𝟏: best preference values (1 ∈ 𝐴) </a>

Question 5

5. Fuzzy constraint satisfaction problems (FCCPs)

Answer 5

〈𝐴 = [0,1], += max,×= min, 0,1〉

0: worst preference
1: best preference

optimization criterion = maximize the minimum preference