+1 vote
in Artificial Intelligence by
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 Answer

0 votes
by

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 image  back on the queue whenever any value is deleted from the domain of image, even if each value of image  is consistent with several remaining value of image. Suppose that for every arc image  we keep track of the number of the remaining values of image that are consistent with each value of image. 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 image, then every arc  image pointed to image must be reinserted on the queue for the checking. The complexity of arc consistency can be given as image.

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

Related questions

Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that

ONE SOLUTION

Chuck Norris can delete the Recycling Bin.
...