2005 | OriginalPaper | Chapter
AC-*: A Configurable, Generic and Adaptive Arc Consistency Algorithm
Author : Jean-Charles Régin
Published in: Principles and Practice of Constraint Programming - CP 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we present AC-*, a new configurable, generic and adaptive algorithm for establishing arc consistency for binary constraints. AC-* is configurable, that is by combining some parameters AC-* corresponds to any existing AC algorithm: AC-3, AC-4, AC-6, AC-7, AC-2000, AC-2001, AC-8, AC-3
d
, AC-3.2 and AC-3.3. AC-* is generic, like AC-5, because it may take into account the structure of the constraints.
AC-* is adaptive because the underlining algorithm can be changed during the computation in order to use the most efficient one. This new algorithm leads to a new nomenclature of the AC algorithms which is based on the different features used by the algorithm like the values that are reconsidered when a domain is modified, or the fact that bi-directionality is taken into account, or the way a new support is sought. This new nomenclature shows that several new possible combinations are now possible. That is, we can easily combine some ideas of AC-3 with some ideas of AC-7 and some ideas of AC-2001 with some ideas of AC-6. Some experimental results highlight the advantages of our approach.