Algorithme AC-3
# 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 :

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.

