1
$\begingroup$

I was watching the video Constraint Satisfaction: the AC-3 algorithm, and I tried to solve this question:

Given the variables A, B, C and D, with domain {1, 2, 3, 4} in each of them and restrictions A> B, B = C and D ≠ A, use the AC algorithm.

But the teacher told me that my answer below is wrong!

He gave me a tip: Domain D will not be changed!

Below, I is my answer step by step. If someone can help me find the error, I appreciate it!

To solve this exercise, it is first necessary to organize the data in order to separate what is the domain, agenda and arc.

Step 1

Soon after, we will analyze the first item on the agenda “A> B” with domain A, in order to eliminate unnecessary elements from the domain.

step 2.

Analyze domain B with the agenda item “B <A”

3 step

Analyze domain B with the agenda item “B = C” and add the constraint “A> B”

4 Step

Analyze domain D with the agenda item “D ≠ A” and add the constraint “B <A”

5 Step

Analyze domain A with the agenda item “A ≠ D”

6 Step

Analyze domain A with the agenda item “A> B”

7 Step

Analyze domain B with the agenda item “B = C”

8 Step

Analyze domain B with the agenda item “B <A”

9 Step

Result

10 Step

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

To satisfy $D\ne A$, for each element in the domain of $D$, say $d$, there must be at least one element in the domain of $A$, say $a$, that $d \ne a$.

Domain of $D$: $ \{ 1, 2, 3, 4 \} $

Domain of $A$: $ \{ 2, 3, 4 \} $

So, for example if $d=2$, there is at least one element in the domain of $A$ like $a$ such that $d \ne\ a$. E.g. $1, 3$ and $4$. So, $2$ remains in the domain of $D$. This is the case for other elements of $D$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .