0
$\begingroup$

I am studying CSP problems in artificial intelligence. I don't understand the MAC-3 algorithm especially line number 10. Could you tell me with step by step?

1. Function AC-3MAC(Q,CV)
   1.1 Q ← {(V i ,V cv ) in arcs(G),i>cv} % start with arcs going to cv 
   cv means current variable
2. Begin
3.     consistent := true;
4.     While not (empty?(Q)) and consistent
5.     Do Begin
6.         (i,j) := pop(Q);
7.         if revise(i,j)
8.         then begin
9.             consistent := not(empty?(domain[i]));
10.            Q:=Q U {(k,I) | (k,I) in arcs(G) & k<>j & k>cv}
11.        end;
12.    end;
13.    consistent←not Empty Di;
14. end;

I understand the process of AC-3 algorithm. This is AC-3 algorithmProcedure AC3 Begin 1. Q:= {(i, j)|C ij ∈ C i ≠ j} 2. While Q not empty Do 3. Begin 4. Select or delete a pair (i, j) from Q 5. If Revise (i, j) then 6. Q:= Q ∪ {(k, i)|C ki ∈ C, k ≠ i et k ≠ j} 7. End if 8. End while End

The below pictures represent map coloring example.I have traced manual with AC-3 algorithm.The point I want to know is line number 1.1 in MAC algorithm. How can I add arcs in queue with i>cv ? Furthermore ,in line number 10 how to add queue of arcs k>cv.

This is example of map coloring problem

This is hand manual of AC-3 algorithmcccc

$\endgroup$
  • 2
    $\begingroup$ I'm more confused by line 13, where the code is just the name of a Boolean variable. Did you copy that line wrongly? $\endgroup$ – David Richerby Feb 4 at 13:16
  • $\begingroup$ Asking us to explain every step of the algorithm sounds like a lot to ask. Can you edit your question to ask about one specific aspect that you are unclear on? Perhaps you'd like to ask only about line number 10? Also could you tell us what your current understanding is, and what you're stuck on, to help us narrow down the source of your confusion? $\endgroup$ – D.W. Feb 4 at 18:16
  • $\begingroup$ I have edited.please review again. $\endgroup$ – Thuriya Thwin Feb 5 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.