\chapter{Programmation par contraintes}
% Refaire une intro pour les PPC
% Utilité?

Un problème de satisfaction de contraintes (CSP)\footnote{Acronyme
  anglophone de Constraint Satisfaction Problem} est composé:
\begin{itemize}
\item d'un ensemble de variables, $X = (x_1, \dots, x_n)$
\item pour  chaque variable, un  domaine y est  associé, $D =  (d_1, \dots,
  d_n)$.  Les domaines  doivent tous  être discrets.  D'autres algorithmes,
  tels  que le  simplexe,  permettent  de résoudre  des  problèmes sur  des
  domaines continus en temps polynomial.
\item d'un ensemble de contraintes  qui restreignent les valeurs que peuvent
  prendre les variables $C =  (c_1, \dots, c_m)$. Chaque contrainte est une
  relation sur une séquence de variables.
\end{itemize}

Une \emph{instanciation} d'un CSP est l'affectation d'une valeur du domaine
$d_i$ à chaque variables $x_i$.

On  dit qu'une  instanciation est  \emph{consistante} si  aucune contrainte
n'est violée.

Une solution  à un CSP  est une instanciation  de $X$ telle que  toutes les
contraintes soient satisfaites.

Un CSP  dont toutes  les contraintes concernent  au plus deux  variables est
appellé   un  CSP   binaire.  L'intérêt   des  CSP   binaire   est  surtout
pédagogique. Effectivement,  on peut facilement représenter  un CSP binaire
sous la forme  d'un graphe. Les noeuds représentent  alors les variables et
les  arêtes   représentent  les  contraintes.  On   peut  transposer  cette
représentation  aux  CSP n-aires  en  utilisant des  hypergraphes\footnote{Un
hypergraphe  est un  graphe dont  les  aretes sont  reliés à  plus de  deux
noeuds}

\section{Generate and Test}
La façon  la plus  intuitive de  résoudre un CSP  consiste à  instancier la
variable à chaque  élément de leurs domaines de  définition les unes après
les  autres.  Cette  méthode  équivaut  au parcours  d'un  arbre où  chaque
profondeur  correspond  à l'instanciation  d'une  variable.  Cet  algorithme
s'appelle \emph{Generate and Test}.
%% Ajouter un schema ici


%X = la liste des varaiable
%A = l'ensemble des instanciation de chaque variable (au depard vide)
\begin{algorithm}[!htb]
\caption{Generate and Test}
\label{alg5}
\begin{algorithmic}
  \Function{testgenerate} {$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 return est\_consistant($A$);
    \EndIf
    \State soit $x_i \in X$;
    \ForAll {$v \in d_i$}
      \State return testgenerate($X \setminus x_i$, $A \cup \{ x_i \rightarrow v \} $);
   \EndFor
  \EndFunction
\end{algorithmic}
\end{algorithm}

Cette méthode est évidement très coûteuse en temps.

\section{Le Backtracking}
On remarque sur l'algorithme  précédant qu'il suffit qu'une contrainte soit
violée pour qu'aucune des instanciations  filles ne soit consistantes. Or il
est possible  de vérifier qu'une contrainte  est violée dès  que toutes ses
variables sont  instanciées. Par conséquent, en vérifiant  dès que possible
la  satisfaction  de  chaque  contrainte,  on  aboutit  à  l'algorithme  de
recherche   \emph{Test   and   Generate}   plus  souvent   référencié   sous
\emph{Backtrack} ou \emph{BT}.
% Ajouter un shema
\begin{algorithm}[h]
\caption{Backtracking}
\label{alg5}
\begin{algorithmic}
  \Function{backtrack} {$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
    \Else
      \State soit $x_i \in X$;
      \ForAll {$v \in d_i$}
	\If {est\_consistent($A \cup \{x_i \rightarrow v\}$)}
	  \State return backtrack($X \ x_i$, $A \cup \{x_i \rightarrow v\}$);
	\EndIf
      \EndFor
    \EndIf
  \EndFunction
\end{algorithmic}
\end{algorithm}

\section{Utilisation d'heuristique dans le Backtrack}
On remarque que trois ordres influencent l'algorithme de backtrack : 
\begin{description}
\item[L'ordre d'instanciation des variables (l'ordre vertical):] 
On  utilise habituellement une  heuristique s'appuyant  sur le  principe de
\emph{l'échec d'abord}  qui cherche à  faire apparaître le  plus rapidement
possible  des   violations  de   contraintes.   Elle  peut   être  utilisée
statiquement  avant  l'exécution  ou  dynamiquement, en  calculant  pendant
l'exécution de  l'algorithme et  à chaque noeud  la prochaine  variable qui
sera instanciée.

Dans le  cas statique,  la meilleure des  heuristiques ne prenant  en compte qu'un
seul critère  semble être la  cardinalité maximum. Elle consiste  à choisir
une première  variable à  instancier aléatoirement.  La  prochaine variable
instanciée sera celle reliée (par  des contraintes) au plus grand nombre de
variables déjà  définies dans l'instanciation  courante.  D'autres éléments
peuvent  être  considérés  :  variable  du  plus  petit  domaine,  variable
participant au plus grand nombre de contraintes, variable impliquée dans la
contrainte la moins satisfiable, etc\dots

Dans   le  cas  dynamique,   l'heuristique  appelée   \emph{min-domain}  ou
\emph{ré-arrangement  dynamique} a  longtemps  été considérée  comme un  des
meilleurs choix  possibles.  Elle consiste  à choisir la variable  ayant le
nombre  minimum de valeurs  vérifiant une  propriété de  consistance locale
donnée. La  prise en compte simultanée d'autres  caractéristiques permet en
général une amélioration sensible des performances.

\item[L'ordre d'instanciation des valeurs (l'ordre horizontal):]
Là encore, on  peut choisir une heuristique statique  ou dynamique. Il faut
noter qu'une  telle heuristique n'aura  aucun effet sur l'efficacité  de la
recherche  si  le  CSP est  inconsistant  ou  si  l'on cherche  toutes  les
solutions puisqu'on devra alors explorer  toute la largeur de l'arbre. Bien
que  quelques propositions  d'heuristiques horizontal  à  caractère général
aient   été   faites\footnote{Heuristique   s'appuyant  sur   des   modèles
statistiques},  les  heuristique  dépendantes   du  domaine  sont  les  plus
efficaces. En particulier, l'ordre d'instanciation des valeurs peut souvent
être avantageusement guidé par le critère d'optimisation (si il y en a un).

\item[L'ordre de vérification des contraintes:]
Il  n'apparaît pas  explicitement dans  la fonction  \emph{backtrack}, mais
sera   utilisé  par   la  fonction   qui  vérifie   la   consistance  d'une
instanciation.    En   effet,  il   est   habituellement  possible,   après
l'instanciation d'une  nouvelle contrainte  de vérifier la  satisfaction de
plusieurs contraintes.  L'ordre de vérification des contraintes n'influence
pas la  taille de l'espace  exploré, mais, la vérification  des contraintes
les moins satisfiables  en premier permet de diminuer le  nombre de tests de
satisfaction de contraintes.
\end{description}

%\section{Mémorisation des contraintes}