\chapter{Élagage de domaines}

L'élagage de domaines permet de supprimer certaines valeurs des domaines de
définition des variables.

\section{Noeud consistance}
Le noeud représentant  une variable $x_i$ dans un  graphe de contrainte est
un noeud  consistant si  pour chaque valeur  de son domaine  de définition,
chaque contrainte unaire sur $x_i$  est satisfaite.  Si le domaine $d_i$ de
la variable  $x_i$ contient une  valeur $v$ qui  ne satisfait pas  une des
contraintes unitaires sur $x_i$, alors,  l'instanciation de $x_i$ en $v$ sera
toujours un mauvais  choix. Par conséquent, on peut  enlever $v$ du domaine
de définition de  $x_i$. Après cette vérification sur  toutes les variables
du CSP, on peut supprimer toutes les contraintes unitaires du CSP.

\begin{algorithm}
\caption{Noeud consistance}
\label{alg1}
\begin{algorithmic}
  \Function{nconsist}{$X$}
    \State $\triangleright X$: ensemble des variables
    \ForAll{$x_i \in X$}
      \ForAll{$v \in d_i$}
        \If{$v$ est inconsistent avec une des contraintes unitaires sur $x_i$}
          \State $d_i \Leftarrow d_i \setminus v$;
        \EndIf
      \EndFor
    \EndFor
  \EndFunction
\end{algorithmic}
\end{algorithm}


\section{Arc consistance}
Dans un graphe de contrainte, un arc $(x_i, x_j)$ est arc-consitant si pour
toutes valeurs $v_i$ du domaine $d_i$, il existe une valeur $v_j$ du domaine
$d_j$ telle que l'instance $x_i  \Leftarrow v_i; x_j \Leftarrow v_j$ qui ne
viole pas la contrainte symbolisée par l'arc $(x_i, x_j)$.

Un arc  $(x_i, x_j)$  peut être rendu  consistant en supprimant  du domaine
$d_i$  les valeurs de  $x_i$ qui  ne peuvent  pas satisfaire  la contrainte
quelque soit la valeur de $x_j$.
 
\begin{algorithm}
\caption{Revise}
\label{alg2}
\begin{algorithmic}
  \Function{revise}{$x_i, x_j$}
    \State DELETE $\Leftarrow$ false;
    \ForAll{$v_i \in d_i$}
      \If{il n'existe pas $v_j \in d_j$ tel que $(v_i,v_j)$ est consistant}
         \State $d_i \Leftarrow d_i \setminus v_i$;
         \State DELETE $\Leftarrow$ true;
      \EndIf;
    \EndFor;
    \State return DELETE;
  \EndFunction
\end{algorithmic}
\end{algorithm}

On  remarque qu'appliquer la  fonction revise  sur tous  les noeuds  du CSP
n'est  pas   suffisant.   Effectivement,  en  réduisant   les  domaines  de
définitions   des  variables  du   CSP,  il   est  possible   que  d'autres
arc-inconsistants  apparaissent.   Il  faut  donc revisiter  chaque  noeud.
L'algorithme \ref{alg3} connu sous le nom de AC-1 fait précisément ceci.

\begin{algorithm}
\caption{AC-1}
\label{alg3}
\begin{algorithmic}
  \Function{AC-1}{$X$}
    \State $\triangleright X$: ensemble des variables
    \State $Q \Leftarrow \{(x_i, x_j) \in X$ tel qu'il existe une contrainte sur $(x_i, x_j)\}$;
    \Repeat
      \State CHANGE $\Leftarrow$ false;
      \ForAll{$(x_i, x_j) \in Q$}
        \State CHANGE $\Leftarrow$ revise($x_i$,$x_j$) or CHANGE;
      \EndFor
    \Until{not(CHANGE)}
  \EndFunction
\end{algorithmic}
\end{algorithm}

Cet algorithme n'est  pas optimal puisque la révision  d'un arc entraîne la
revisite de tous les arcs, alors  que seuls les arcs étant en relation avec
les  variables  modifiées   auraient  besoin  d'être  revisités.  L'algorithme
\ref{alg4} connu  sous le nom de AC-3  permet de ne revisiter  que les arcs
potentiellement affectés par l'élagage de domaine de l'itération précédente.

\begin{algorithm}
\caption{AC-3}
\label{alg4}
\begin{algorithmic}
  \Function{AC-3}{$X$}
    \State $\triangleright X$: ensemble des variables
    \State $Q \Leftarrow \{(x_i, x_j) \in X$ tel qu'il existe une contrainte sur $(x_i, x_j)\}$;
    \While{$Q \neq \emptyset$}
      \State soit  $(x_i, x_j) \in Q$
      \State $Q \Leftarrow Q \setminus (x_i, x_j)$;
      \If {Revise($x_i, x_j$)}
        \State $Q \Leftarrow Q \cup \{(x_k, x_i)$ et $(x_k, x_j)$ tel qu'il existe une contrainte $(x_k, x_i)$ ou $(x_k, x_j)\}$;
      \EndIf
    \EndWhile
  \EndFunction
\end{algorithmic}
\end{algorithm}

On peut alors remarquer que lorsque  AC-3 revisite pour la seconde fois les
arcs, il re-test les  paires de valeurs qui ont déjà été  testées lors de la
première  itération et dont  on connaît  déjà la  consistance. L'algorithme
AC-4 permet de raffiner les paires de valeurs retestées.

Tout d'abord,  l'algorithme initialise une structure  interne utilisée pour
se souvenir des paires de  valeurs consistantes. La structure $S$ (au départ
vide)  contient les couples  de valeurs  consistantes. Lorsqu'un  élément du
domaine de  définition d'une variable  est supprimé, le  couple $<Variable,
Valeur>$ est sauvegardé  dans $Q$ pour connaître quels  noeuds doivent être
revisités.

\begin{algorithm}
\caption{Initialize}
\label{alg5}
\begin{algorithmic}
  \Function{Initialize}{$X$}
  \State $\triangleright X$: ensemble des variables
  \STATE $Q \Leftarrow \{\}$;
  \STATE $S \Leftarrow \{\}$;
  \FORALL{$(x_i,x_j) \in X$}
    \FORALL {$v_i \in d_i$}
      \STATE TOTAL $\Leftarrow$ 0;
      \ForAll {$v_j \in d_j$}
        \If {$(v_i, v_j)$ est consistant d'après la contrainte $(x_i, x_j)$}
          \State TOTAL $\Leftarrow$ TOTAL + 1;
          \State $S_{x_j, v_j} \Leftarrow S_{x_j, v_j} \cup \{<x_i, v_i>\}$;
        \EndIf
      \EndFor
      \State COUNTER[$(x_i, x_j), v_i$] <- TOTAL;
      \If {COUNTER[$(x_i, x_j), v_i$] = 0}
        \State $d_i = d_i \setminus v_i$;
        \State $Q \Leftarrow Q \cup \{<x_i,v_i>\}$;
      \EndIf
    \EndFor
  \EndFor
  \State return $Q$;
  \EndFunction
\end{algorithmic}
\end{algorithm}

Après l'initialisation, l'algorithme AC-4 permet de revisiter uniquement
les couples de valeurs affectés par l'itération précédente.

\begin{algorithm}
\caption{AC-4}
\label{alg6}
\begin{algorithmic}
  \STATE $Q \Leftarrow$ Initialize();
  \WHILE{$Q \neq \emptyset$}
    \STATE soit $<x_j, v_j> \in Q$
    \State $Q = Q \setminus <x_j, v_j>$;
    \FORALL{$<x_i, v_i> \in S_{x_j,v_j}$}
      \STATE COUNTER[$(x_i, x_j), v_i$] $\Leftarrow$ COUNTER[($x_i, x_j), v_i$] - 1;
      \IF{COUNTER[$(x_i, x_j), v_i$] = 0 and $v_i \in d_i$}
        \STATE $d_i = d_i \setminus v_i$;
        \STATE $Q \Leftarrow Q \cup \{<x_i, v_i>\}$;
      \EndIf
    \EndFor
  \EndWhile
\end{algorithmic}
\end{algorithm}

Les deux algorithmes AC-3 et AC-4 sont les plus utilisés pour maintenir l'arc
consistance. Il existe néanmoins d'autres algorithmes AC-5, AC-6, AC-7,
etc,\dots mais, ils ne sont pas aussi utilisés.

%\section{Chemin consistence}


%http://kti.ms.mff.cuni.cz/~bartak/constraints/consistent.html