Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read the AC-3 algorithm. I don't understand some basic thing about it:

In function ac3 (X, D, R1, R2), we call arc-reduce (x, y), and then check if there is a value vy in D(y) which satisfy the constraint. As I understood, even if one of the vx is not satisfy with vy, then arc-reduce return true. And then, we will add to the worklist (z, x) where z!=y, if D(x) is not empty.

What I don't understand is why we do that? We have in D(x) all the values which satisfy with vy. Do why we need to check it also with vz? This is also strange because arc-reduce return false if all vx in D(x) are satsify with vy. So as I understood it, we add the vz constraint to the worklist only when one of the vx is not stasify with vy, but vx is not in the D(x) anymore, so why we do it?

share|improve this question
add comment

1 Answer

Two possible cases:

(1) Imagine if there is another constraint involving $z$ and some other variable $t$ that has yet to be checked before. Then reducing the domain of $z$ to match the updated domain of $x$ could result in a different arc-reduce $(z, t)$ since the domain of $t$ might be able to cover for the updated domain of $z$, but it may not cover for the un-updated (and actually thus obsolete and incorrect) version of $D(z)$.

(2) Another scenario would be arc-reduce $(t, z)$, and the domain of $z$ might appear to cover more values of $t$, than it would have, had it been properly reduced. This might cause your algorithm to return true, instead of false, if for example, no values of the trimmed $z$ actually fit the $z-t$ constrain anymore.

Hope this helps.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.