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 pour laquelle 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 3 ) et une complexité spatiale de O ( e ), où e est le nombre d'arcs et d est la taille du plus grand domaine.
