Catalogue of Artificial Intelligence Techniques
Aliases: AC, AC Algorithm, AC-3
Keywords: arc, arc consistent, arc inconsistency, constraint satisfaction problem, constraints, domains, queue , variables
Categories: Problem Solving
Author(s): Stuart Crichton
The AC-3 algorithm is used to find the solution of a Constraint Satisfaction Problem (CSP).
The Algorithm uses Constraints (a relation that restricts the value of the variable), Variables (Generally something with no fixed value. However in the AC-3 Algorithm it takes any value out of several discrete ones) and Variable Domains (the set of domains that are used for a specific value) to find out whether the arc is consistent or not.
The algorithm works as follows:
It starts by making a queue to make sure that every arc which needs to be checked is properly checked for inconsistency. The algorithm then takes every arc (Xi,Xj), one at a time, withdraws and checks for inconsistency. If the value is inconsistent then it is removed and is deleted if for every X in Domain[Xi] there is no value of Y in Domain[Xj] that allows (X,Y) to satisfy the constraint between Xi and Xj. If values are deleted then the arcs (Xk,Xi) pointing to Xi must be entered back into the queue and checked.
By using this algorithm it should be found that either every arc is consistent or that some variable has an empty domain. This leads to the conclusion that the CSP cant possible be arc consistent.
- Stuart Russel, Peter Norvig, Artificial Intelligence: A Modern Approach, Chapter 5, pp.144-147.