# AC-3 puts back on the queue every arc (Xk,Xi) whenever any value is deleted from the domain of Xi, even if each value of Xk is consistent with several remaining values of Xi.

+1 vote
397 views
AC-3 puts back on the queue every arc (Xk,Xi) whenever any value is deleted from the domain of Xi, even if each value of Xk is consistent with several remaining values of Xi. Suppose that, for every arc (Xk,Xi), we keep track of the number of remaining values of Xi that are consistent with each value of Xk. Explain how to update these numbers efficiently and hence show that arc consistency can be enforced in total time O(n2d2)

+1 vote
by
selected by (user.guest)

AC-3 algorithm is one of the well- known arc consistency algorithms for filtering CSPs.

This algorithm carries out revisions and require support check to identify and delete all unsupported values from the domains.

AC-3 algorithm puts every arc   back on the queue whenever any value is deleted from the domain of , even if each value of   is consistent with several remaining value of . Suppose that for every arc   we keep track of the number of the remaining values of  that are consistent with each value of . Whenever a value is deleted from some variable’s domain to remove arc inconsistency, it could result in arcs pointed to variables. If any value is deleted from the domain of , then every arc   pointed to  must be reinserted on the queue for the checking. The complexity of arc consistency can be given as .

Checking consistency of an arc can be done in . Arc consistency can be enforced by .

+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote