Exercise 1
Recall the definition of domain consistency and relaxed domain consistency such as bound(Z), bound(D) and range consistency. What is the consistency level of the following CSPs?
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {1,3}, x3 ∈ {1,3}, x4 ∈ {1,3}, C≡ alldifferent(x1,x2,x3,x4)⟩ |
Solution
The weakiest form is bound(Z) consistency. Accordingly we
should ask whether the bounds of xi, i=1,2,3,4 have a bounded
support. For x1=1 we can have x2=2, x3=3 but no value would be
left for x4. Hence, P is not bound(Z) consistent.
Since this is the weakiest form of those asked all the others are also
not satisfied.
| P = ⟨ x1 ∈ {1,2,3}, x2 ∈ {2,3}, x3 ∈ {2,3}, x4 ∈ {1,2,3,4}, C≡ alldifferent(x1,x2,x3,x4)⟩ |
Solution
Same as above, it is not consistent in any of the forms.
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {2}, x3 ∈ {1,2,3}, C≡ alldifferent(x1,x2,x3)⟩ |
Solution
It is bound(Z). For being bound(D) it must be
that for all xi, i=1,2,3 its bounds belong to a support. This
holds true for this case.
For being range consistent all values of xi i=1,2,3 must belong to
a bounded support. This is not true since x3=2 has no support in
x2. Hence it is also not arc consistent.
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {2}, x3 ∈ {1,3}, C≡ alldifferent(x1,x2,x3) ⟩ |
Solution
It is bound(Z) and bound(D). Since 2 is
not anymore in the domain of x3 then it is also range consistent.
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {1,3}, x3 ∈ {1,3}, C≡ alldifferent(x1,x2,x3)⟩ |
Solution
bound(Z): yes, bounded support hence we can reintroduce the
value 2 in the support variables
bound(D): no.
range: yes, bounded support hence we can reintroduce the value 2 in the support variables