0
$\begingroup$

Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm?

According to This Link and to Wikipedia's description of AC3: once one domain is empty, the algorithm stops, indicating there is no solution to the CSP.

This book says: if one domain of the non assigned variables becomes empty then backtracks to....

My challenge is about the behavior of this algorithms, i.e, in which phase (when) AC-3 stops, and when it's select Backtrack.

Update: Anyone could describe the behaviors of AC-3 on empty domain in each phase?

References: This question asked 5 month ago on SO but I think the answer is wrong, because I add some references that shows other things.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Welcome to CS.SE! 1. You say "some references say". Please edit the question to provide at least one citation for each claim, so we can read what they say for ourselves and see the context. In particular, please try to provide at least one citation for each claim -- ideally, where you can provide a full citation (authors, title, where published) and a link to freely available text, and a pointer to a specific place where that is said, or a quotation with appropriate context. $\endgroup$
    – D.W. ♦
    Jul 22, 2016 at 1:38
  • 2
    $\begingroup$ 2. What are your thoughts? What's your reasoning? Why do you think the answer on SO is wrong? I'm not sure what you mean by "I add some references that shows other things" -- I don't see any references in this question, merely a claim that such references exist. It'd help if could edit the question to spell out your reasoning. $\endgroup$
    – D.W. ♦
    Jul 22, 2016 at 1:39
  • 2
    $\begingroup$ 3. You claim "This book" says backstrack and start from other points. Where does it say that? Please provide a precise quotation. I don't see it saying that anywhere. 4. Rather than providing just a "this book" and a link to Google Books, please provide a full citation, including title and authors. We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$
    – D.W. ♦
    Jul 22, 2016 at 4:47
  • 1
    $\begingroup$ I'm afraid it needs a bit more editing -- re-read my comments. We need you to edit the question to address my point 3 (see above). Also we want a full citation for each claim. Just linking and saying "This link" or "this book" aren't good enough -- we want a question that will remain working even if those links stop working. Also, you should edit to add your thoughts and your reasoning; why do you think "this book" says otherwise? What is your detailed reasoning? Please support your reasoning with quotes from the book. Please take some time to improve your question. Thank you! $\endgroup$
    – D.W. ♦
    Jul 22, 2016 at 10:31
  • 2
    $\begingroup$ If you have doubts in the answer of the question on SO, you really should ask it on SO. If you want to ask it here, you need to provide full context so that we, the users on CS.SE, will understand the question. Right now, the question is unclear, in my opinion. By the way, I did not ask the question, nor answer the question on SO. $\endgroup$
    – Nobody
    Jul 22, 2016 at 13:24

2 Answers 2

Reset to default
1
$\begingroup$

You've misunderstood the book. It's not describing the AC-3 algorithm; it's describing some other algorithm. The book is describing an algorithm that combines both guess-and-backtrack together with arc consistency. The AC-3 algorithm doesn't do any guess-and-backtrack; it uses only arc consistency checks.

Thus, AC-3 does terminate if there is some variable whose domain set becomes empty; in this case, AC-3 declares the constraint system unsatisfiable (inconsistent). This is the correct thing to do, in the context of the AC-3 algorithm.

Of course, if you're talking about some totally different algorithm (like the book is), that other algorithm might do something totally different. No great surprise there.

I don't see anything wrong with the answer to the Stack Overflow question you link to.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Please see question 3- Part (b) or search backtrack in this file, s3-us-west-2.amazonaws.com/cs188websitecontent/exams/… $\endgroup$
    – Michle Niaye
    Jul 25, 2016 at 7:31
  • $\begingroup$ @MichleNiaye, what about it? That exam problem isn't talking about the AC-3 algorithm, either. It explicitly says "You decide to try a new approach..." (i.e., not AC-3; something different). $\endgroup$
    – D.W. ♦
    Jul 25, 2016 at 11:26
  • $\begingroup$ Ok, about this exam you are right, Is it possible to talk with you? the question says we run AC-3 on CSP problem, isn't related? $\endgroup$
    – Michle Niaye
    Jul 25, 2016 at 11:30
0
$\begingroup$

At the very first phase when you give empty domain it is non-conditional failure - it is the same as saying: "I have a function $f(x) = x^2 + 1$, but $x \in {\emptyset}$, find me feasible solutions, which are none.
In the phase when arcs are getting cut you check if the values are consistent between two variables - here arc is either in solution or is inconsistent.
You have the same function as above and points: $x \in \{0, 1\}, y \in \{1, 5\}$. This makes one consistent pair, the second is cut, it will not be in the solution. At this point if there were more constraints you would check the consistency of related variables (You might call it backtrack, because another variable that is related takes part, but here you might find that there are no arc, and it is perfectly fine here). But if $x \in \{23, 45\}$ then you cannot find any good pair, but now it turns out that domains of $x$ is $\emptyset$, so something was inconsistent - with checked constraints you have no feassible points, so it is failure.

The sildes you have provided show that AC-3 is detecting wrong candidate for solution faster than forward checking. The outer scheme is backtracking solver, which at every step assumes one of possible values, assigns it and continues guessing values until it finds solution or contradiction (in such case it goes back to assumption made and changes it to different possible value). Slides show that propagating constraints is superior to propagating values, because it allow faster checking of error.

AC-3 in this context is used as black-box function to determine failure, but the pure algorithm itself does not backtrack - it operates on one given instance - candidate for solution, and it's output serves as indicator to backtracking.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Sorry Evil, thanks from your well descriptive answer, D.W post and say the AC-3 hasn't backtrack. I think AC-3 on CSP has. would you please clarify it for me? thanks. $\endgroup$
    – Michle Niaye
    Jul 25, 2016 at 22:59
  • $\begingroup$ Of course. D.W. Is right, AC-3 does not backtrack, I thought that you call one thing backtrack and I wrote it in the place where I thought that you use this term. In the link I gave you there was backtracking, but it was AC-3 merged with other concepts. D.W. comment about the link you provided (I have not seen it earlier) was accurate. AC-3 does consistency test without backtracking, but of course it might be used with other techniques. But the test option about backtracking was bad choice. I would propose to look at some implementation and look at pure AC-3. $\endgroup$
    – Evil
    Jul 25, 2016 at 23:18
  • $\begingroup$ "It explicitly says "You decide to try a new approach..." (i.e., not AC-3; something different)." - I have read the task right now and as D.W. cited and paper says - it is a mixture of consistency check and backtracking, so there was some confusion but I hope it is clearer now as we get into the source. $\endgroup$
    – Evil
    Jul 25, 2016 at 23:26
  • $\begingroup$ Please let me to study more and say my idea. but one problem so you means AC-3 on CSP problem again is not using backtracking? Answer with yes or no please? I study more until tomorrow. $\endgroup$
    – Michle Niaye
    Jul 25, 2016 at 23:36
  • $\begingroup$ This is very critical for me and studying, please let me know your idea with Yes/No about AC-3 on CSP problem again is not using backtracking? thanks. $\endgroup$
    – Michle Niaye
    Jul 25, 2016 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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