Algorithme AC-3

Dans la satisfaction de contraintes, l’algorithme AC-3 (abréviation d'Arc Consistency Algorithm 3) fait partie d'une série d'algorithmes utilisés pour la résolution de problèmes de satisfaction de contraintes (ou CSP). Il a été développé par Alan Mackworth (en) en 1977. Les algorithmes AC antérieurs sont souvent considérés comme trop peu efficaces, et beaucoup des suivants sont difficiles à mettre en œuvre, ce qui fait d'AC-3 le plus souvent enseigné et utilisé dans les solveurs de contraintes très simples.

L'algorithme

AC-3 fonctionne sur les contraintes, les variables et les domaines des variables (scopes). Une variable peut prendre n'importe laquelle de plusieurs valeurs discrètes ; l'ensemble des valeurs d'une variable particulière est appelé son domaine . Une contrainte est une relation qui limite ou contraint les valeurs qu'une variable peut avoir. La contrainte peut impliquer les valeurs d'autres variables.

L'état actuel du CSP pendant l'algorithme peut être vu comme un graphe orienté, où les nœuds sont les variables du problème, avec des arêtes ou des arcs entre les variables liées par des contraintes symétriques, où chaque arc de la liste de travail représente une contrainte qui il faut vérifier la cohérence. AC-3 procède en examinant les arcs entre les paires de variables ( x, y ). Il supprime les valeurs du domaine de x qui ne sont pas cohérentes avec les contraintes entre x et y . L'algorithme conserve une collection d'arcs qui doivent encore être vérifiés ; lorsque le domaine d'une variable a des valeurs supprimées, tous les arcs de contraintes pointant vers cette variable élaguée (à l'exception de l'arc de la contrainte actuelle) sont ajoutés à la collection. Étant donné que les domaines des variables sont finis et qu'un arc ou au moins une valeur sont supprimés à chaque étape, cet algorithme est garanti de se terminer.

A titre d'illustration, voici un exemple de problème de contrainte très simple : X (une variable) a les valeurs possibles {0, 1, 2, 3, 4, 5} -- l'ensemble de ces valeurs est le domaine de X, ou D( X ). La variable Y a le domaine D( Y ) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Avec les contraintes C1 = " X doit être pair" et C2 = " X + Y doit être égal à 4", nous avons un CSP que AC-3 peut résoudre. Notez que le graphe de contraintes réel représentant ce problème doit contenir deux arêtes entre X et Y puisque C2 n'est pas orienté mais que la représentation graphique utilisée par AC-3 est orientée.

Pour ce faire, il supprime d'abord les valeurs non paires du domaine de X comme requis par C1, laissant D( X ) = { 0, 2, 4 }. Il examine ensuite les arcs entre X et Y impliqués par C2 . Seuls les couples ( X =0, Y =4), ( X =2, Y =2), et ( X =4, Y =0) correspondent à la contrainte C2 . AC-3 se termine alors, avec D( X ) = {0, 2, 4} et D( Y ) = {0, 2, 4}.

AC-3 est exprimé en pseudocode comme suit :

Entrée :
  Un ensemble de variables X
  Un ensemble de domaines D(x) pour chaque variable x dans X. D(x) contient vx0, vx1... vxn, les valeurs possibles de x
  Un ensemble de contraintes unaires R1(x) sur la variable x qui doivent être satisfaites
  Un ensemble de contraintes binaires R2(x, y) sur les variables x et y qui doivent être satisfaites
  
 Sortie :
  Arc domaines cohérents pour chaque variable.

function ac3 (X, D, R1, R2)
     // Les domaines initiaux sont rendus cohérents avec les contraintes unaires.
     pour chaque x dans X
         D(x) := { vx dans D(x) | vx satisfait à R1(x) }   
     // 'listedetravail' contient tous les arcs dont nous voulons vérifier la cohérence ou non.
     listedetravail := { (x, y) | il existe une relation R2(x, y) ou une relation R2(y, x) }
 
     faire
         sélectionner n'importe quel arc (x, y) de listedetravail
         listedetravail := listedetravail - (x, y)
         si arc-reduce (x, y) 
             si D(x) est vide
                 retourner échec
             sinon
                 listedetravail := listedetravail + { (z, x) | z != y et il existe une relation R2(x, z) ou une relation R2(z, x) }
     tant que listedetravail n'est pas vide
 
 function arc-reduce (x, y)
     bool changement = faux
     pour chaque vx dans D(x)
         trouver une valeur vy dans D(y) telle que vx et vy satisfassent la contrainte R2(x, y)
         si il n'y a pas de vy {
             D(x) := D(x) - vx
             changement := vrai
         }
     retourner changement

L'algorithme a une complexité temporelle dans le pire des cas de O ( ed ³ ) et une complexité spatiale de O ( e ), où e est le nombre d'arcs et d est la taille du plus grand domaine.

Références

• (en) AK Mackworth. Consistency in networks of relations, Artificial Intelligence, 8:99-118, 1977.
• (en) Stuart Russel et Peter Norvig. Artificial Intelligence : A Modern Approach, 202-233, 2003.