Définition de la consistance d'arc : Un CSP (X,D,C) est consistant d'arc si pour tout couple de variables (Xi,Xj) de X, et pour toute valeur vi appartenant à D(Xi), il existe une valeur vj appartenant à D(Xj) telle que l'affectation partielle {(Xi,vi),(Xj,vj)} satisfasse toutes les contraintes binaires de C.

Par exemple, si C contient la contrainte "X1 + X2 > 2", et si D(X1)=D(X2)={0,1,2}, alors le CSP n'est pas consistant d'arc car lorsque X1=0, il n'y a aucune valeur de D(X2) qui puisse satisfaire la contrainte "X1 + X2 > 2". Pour qu'il soit consistant d'arc, il faut enlever des domaines de X1 et X2 la valeur 0.

L'algorithme qui enlève les valeurs des domaines des variables d'un CSP jusqu'à ce qu'il soit consistant d'arc (on dit que l'algorithme filtre les domaines des variables) s'appelle AC (pour Arc Consistency). Il existe différentes versions de cet algorithme: AC1, AC2, AC3, ..., chaque version étant plus efficace (en général) que la précédente.

Pour plus d'informations sur les algorithmes AC, vous pouvez lire les articles scientifiques suivants :

• [AC1] : The complexity of some polynomial network consistency algorithms for constraint satisfaction problems
  A.K. Mackworth and E.C. Freuder, in Artificial Intelligence 25, pages 65-74, 1985.
• [AC4] : Arc and path consistency revised
  R. Mohr and T.C. Henderson, in Artificial Intelligence 28, pages 225-233, 1986.
• [AC5] : Arc consistency for factorable relations
  M. Perlin, in Artificial Intelligence 53, pages 329-342, 1992.
• [AC5] : A generic arc-consistency algorithm and its specializations
  P. Van Hentenryck, Y. Deville, and C.-M. Teng, in Artificial Intelligence 57, pages 291-321, 1992.
• [AC6] : Arc-consistency and arc-consistency again
  C. Bessiere, in Artificial Intelligence 65, pages 179-190, 1994.
• [AC7] : Using constraint metaknowledge to reduce arc consistency computation
  C. Bessiere, E.C. Freuder, and J.-R. Régin, in Artificial Intelligence 107, pages 125-148, 1999.