La notion de consistance d'arc

Définition 2.1 (Arc-consistance d'un domaine [1])   Soit $P=(\mathcal{X,D,C})$ un $\mathcal{CSP}$ dont les domaines sont finis, et $x$ une variable de $\mathcal{X}$ dont le domaine est $D_x$. On dit que $D_x$ est arc-consistant ssi pour chaque contrainte $c \in \mathcal{C}$, toute valeur de $D_x$ a un support dans les domaines des autres variables de $c$.

Définition 2.2 (Arc-consistance d'un $\mathcal{CSP}$ fini [1])   On dit qu'un $\mathcal{CSP}$ est arc-consistant ssi tous ses domaines sont arc-consistants.

Le filtrage par consistance d'arc consiste à éliminer les éléments qui ne peuvent trivialement figurer dans aucune solution. C'est une consistance locale, elle ne garantit pas l'existence de solutions.

Exemple 2.1   Soit le $\mathcal{CSP}$ suivant :

• $\mathcal{X}=\{a,b,c\}$.
• $\mathcal{D}=\{D_a,D_b,D_c\}$ tels que $D_a=D_b=D_c=\{Rouge,Vert\}$.
• $\mathcal{C}=\{a \neq b, b \neq c, a \neq c\}$.

Ce $\mathcal{CSP}$ est arc-consistant mais n'a pas de solutions. On verra dans la section 2.2.1, comment la contrainte globale all-diff permet de résoudre ce problème.

On peut renforcer cette notion par une extension à $k$ variables : la $k$-consistance. Dans ce cas, on dit qu'un ensemble de $k-1$ variables est $k$-consistant ssi pour chaque contrainte $c \in \mathcal{C}$, toute instanciation des ces variables a un support dans le domaine des autres variables de $c$. Un $\mathcal{CSP}$ est dit $k$-consistant si tout sous-ensemble de $\mathcal{X}$ de cardinal $k-1$ est $k$-consistant.