\chapter{Algorithmes de backward et de forward}
Dans  le  chapitre  précédent,  nous  avons expliqué  comment  réduire  les
domaines de  définition des variables  en testant la consistance  de chaque
paire de valeur pour chaque contrainte.

Il est  possible d'utiliser les  algorithmes d'arc-consistance dynamiquement
lors du parcours de l'arbre de possibilité.

\section{Backtrack intelligent ou Backjumping}
Si on remarque lors du  parcours de l'arbre des possibilités qu'une variable
$x_i$ ne peut être instanciée  sans violer une contrainte sur $(x_i, x_j)$,
alors,  il n'est  pas possible  de trouver  une solution  avec  $x_j$ telle
qu'elle est  instanciée actuellement.  On  peut donc remonter  dans l'arbre
jusqu'à  l'instanciation de  $x_j$. L'algorithme  de \emph{Backjumping} (\ref{alg5})  implémente ce
principe.

\begin{algorithm}
\caption{Backjumping}
\label{alg5}
\begin{algorithmic}
  \Function{backjumping}{$X, A$}
    \State $\triangleright X$: ensemble des variables non instanciées
    \State $\triangleright A$: ensemble des instanciations de chaque variable (au départ vide)
    \If {$X = \emptyset$}
      \State $A$ est une solution;
      \State return $\emptyset$;
    \Else
      \State soit $x_i \in X$;
      \State conflit $\Leftarrow \emptyset$;
      \ForAll{$v \in d_i$}
        \If{conflit-local = $\emptyset$}
          \State Soit conflit-fils $\Leftarrow$ Backjumping($X \setminus \{x_i\}$, $A \cup \{x_i \rightarrow v\}$);
          \If{$x_i \in conflit-fils$}
            \State conflit $\Leftarrow$ conflit $\cup$ conflit-fils;
          \Else
            \State conflit $\Leftarrow$ conflit-fils;
            \State return conflit;
          \EndIf
        \Else
          \State conflit $\Leftarrow$ conflit $\cup$ conflit-local;
        \EndIf
      \EndFor
      \State return conflit;
    \EndIf
  \EndFunction
\end{algorithmic}
\end{algorithm}

Considérons les variables:
\begin{itemize}
\item $X_1 \in \{6,1,4\}$
\item $X_2 \in \{4,5,3\}$
\item $X_3 \in \{2,6,7\}$
\end{itemize}
avec les contraintes:
\begin{itemize}
\item $X_3 < X_1$
\item $X_2 < X_1$
\end{itemize}

Lorsque l'on  teste les instanciations  $X_1 = 1$  et $X_2 = 4$,  on remarque
qu'aucune des  valeurs de $X_3$  ne convient à  cause de la contrainte  $X_3 <
X_1$.  On peut  alors en  déduire  qu'il est  inutile de  tester les  autres
valeurs  de $X_2$ puisque  $X_2$ n'intervient  pas dans  la contrainte  $X_3 <
X_1$. On peut donc directement tester  la valeur suivante de $X_1$. La figure
\ref{tree} illustre cet exemple.

\begin{figure}
  \begin{center}
    %BEGIN IMAGE
    \begin{tabular}{lccccccccc}
%                   &            &            &            &\node{a1}{}  \\[3ex]
%                   &\node{b1}{6}&            &            &\node{b2}{1}&             &            &\node{b3}{4}\\[3ex]
%       \node{c1}{4}&\node{c2}{5}&\node{c3}{3}&\node{c4}{4}&\node{c5}{5}&\node{c6}{3}&\node{c7}{4}&            &\node{c8}{5}\\[3ex]
%                   &            &\node{d1}{2}&\node{d2}{6}&\node{d3}{7}&             &            &            &\node{d4}{2}
                       &            &            &            &\node{a1}{}  \\[3ex]
     $X_1$\hspace{1cm} &            &\node{b1}{6}&            &\node{b2}{1}&            &\node{b3}{4}\\[3ex]
     $X_2$\hspace{1cm} &\node{c1}{4}&\node{c2}{5}&\node{c3}{3}&\node{c4}{4}&\node{c7}{4}&            &\node{c8}{5}\\[3ex]
     $X_3$\hspace{1cm} &            &            &\node{d1}{2}&\node{d2}{6}&\node{d3}{7}&            &\node{d4}{2}
    \end{tabular}
    \nodeconnect{a1}{b1} 
    \nodeconnect{a1}{b2}
    \nodeconnect{a1}{b3}
    \nodeconnect{b2}{c4} 
%    \nodeconnect{b2}{c5}
%    \nodeconnect{b2}{c6}
    \nodeconnect{b3}{c7} 
    \nodeconnect{b3}{c8}
    \nodeconnect{c8}{d4} 
    { 
      \makedash{2pt}
      \nodeconnect{b1}{c1} 
      \nodeconnect{b1}{c2}
      \nodeconnect{b1}{c3}
      \nodeconnect{c4}{d1} 
      \nodeconnect{c4}{d2}
      \nodeconnect{c4}{d3}
      \anodecurve[r]{c4}[l]{b3}{10pt}
   }
   %END IMAGE   
  %HEVEA\imageflush
  \end{center}
  \caption{Exemple d'utilisation de l'algorithme de Backjumping}
  \label{tree}
\end{figure}


\section{Forward Checking}
Le  \emph{Forward Checking}  est la  façon la  plus simple  de  trouver les
futurs conflits.   Au lieu  de tester l'arc-consistance sur  les variables
instanciées, on peut tester l'arc-consistance sur les variables qui ne sont
pas  encore  instanciées. Quand  une  valeur  est  affectée à  la  variable
courante, toutes  les valeurs  des domaines des  variables qui ne  sont pas
encore  instanciées  et qui  entrent  en  conflit  avec  cette  affectation  sont
(temporairement) supprimées du domaine. L'avantage de cet algorithme est que
si le domaine d'une future  variable devient vide, on sait immédiatement que
la solution partielle courante n'est pas consistante.

On remarque  que le  Backjumping n'est pas  utile lors de  l'utilisation du
Forward-Checking. Effectivement,  on est sûr que  toutes les instanciations
suivantes seront consistantes avec les variables précédentes.

\begin{algorithm}
\caption{Forward Checking}
\label{alg6}
\begin{algorithmic}
  \Function{AC3-FC}{$X, c$}
    \State $\triangleright X$: ensemble des variables non instanciées
    \State $\triangleright c$: noeud courant
    \State $Q \Leftarrow \{(x_i,x_c) \in X$ tel que $i > c\}$;
    \State consistent $\Leftarrow$ true;
    \While {$Q \neq \emptyset et Q consistant$}
      \State soit $(x_i, x_j) \in Q$;
      \State $Q \leftarrow Q \setminus (x_i, x_j)$;
      \If {revise($x_i, x_j$)}
        \State consistent $\Leftarrow$ ($D_i \neq \emptyset$);
      \EndIf
    \EndWhile
    \State return consistent;
  \EndFunction
\end{algorithmic}
\end{algorithm}

\section{Full Look Ahead Forward}

Le  Forward-Checking vérifie  seulement les  contraintes entre  la variable
courante et les  futures variables. Alors, pourquoi ne  pas vérifier toutes
les arc-consistances pour réduire au maximum les domaines et supprimer tous
les  conflits  possibles? Cette  approche  s'appelle  le \emph{(Full)  Look
Ahead} ou encore \emph{Maintenance de l'Arc-Consistence} (MAC)\footnote{Les
anglophones parlent de maintaining arc consistency}

L'avantage du Full  Look Ahead Forward est qu'il  détecte aussi les conflits
entre les  futures variables et par conséquent  permet d'élaguer rapidement
les branches qui conduisent à des échecs.

Tout  comme  pour  le  Forward  Checking, il  est  inutile  d'appliquer  le
Backjumping avec le Full Look Ahead.

\begin{algorithm}
\caption{Full Look Ahead Forward}
\label{alg7}
\begin{algorithmic}
    \Function{AC3-LA}{$X, c$}
    \State $\triangleright X$: ensemble des variables non instanciées
    \State $\triangleright c$: noeud courant
    \State $Q \Leftarrow \{(x_i,x_c) \in X$ tel que $i > c\}$;
    \State consistent $\Leftarrow$ true;
    \While {$Q \neq \emptyset$ et $Q$ consistant}
      \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)\}$ pour tout $i > c$;
        \State consistent $\Leftarrow$ ($D_i \neq \emptyset$);
      \EndIf
    \EndWhile
    \State return consistent;
  \EndFunction
\end{algorithmic}
\end{algorithm}

Le Full Look Ahead Forward permet  d'élaguer plus de branches de l'arbre de
possibilité que le  Forward Checking. Mais, il faut  remarquer qu'il demande
plus de temps à chaque instanciation de variables.