214 lines
9.3 KiB
TeX
214 lines
9.3 KiB
TeX
\section{Chapitre 2: Fouille et filtrage}
|
|
\label{sec:ch2}
|
|
|
|
\subsection{Processus de résolution}
|
|
\label{sec:ch2res}
|
|
|
|
\paragraph{Énumération}
|
|
|
|
\begin{itemize}
|
|
\item Force brute: énumérer toutes les solutions candidates
|
|
\item Itération et filtration
|
|
\item Au moins une unité de temps sur chaque solution candidate
|
|
\item Compléxité dans
|
|
\begin{align}
|
|
\Omega \left( \prod_{i=1}^{n} \| \texttt{dom}(x_i) \| \right)
|
|
\end{align}
|
|
\item Fondement des algorithmes les plus sophistiqués
|
|
\end{itemize}
|
|
|
|
\paragraph{Fouille en profondeur}
|
|
|
|
\begin{itemize}
|
|
\item Créer un arbre de recherche
|
|
\item Chaque noeud équivaut à une solution partielle
|
|
\item Ordre de visite:
|
|
\begin{itemize}
|
|
\item Racine
|
|
\item Premier enfant non visité depuis la gauche
|
|
\item Si tous les enfants visités, retour au noeud parent
|
|
\end{itemize}
|
|
\item Validité
|
|
\begin{itemize}
|
|
\item Doit visiter toutes les solutions candidates possibles
|
|
\item Ne devrait pas visiter deux fois la même solution partielle ou candidate
|
|
\end{itemize}
|
|
\item Décisions de l'arbre de recherche: \textbf{heuristique} décide de la politique de choix
|
|
\item Voir Algorithme \ref{alg:fouilleprofcomp}: $K$=Solution candidate, $P$=Solution partielle, $S$=Solution
|
|
\end{itemize}
|
|
|
|
\begin{algorithm}[H]
|
|
\DontPrintSemicolon
|
|
\Deb{
|
|
\Repeter{$S \neq \emptyset$}{
|
|
$K \leftarrow \lbrace x_i \mid \left\lVert \mathtt{dom}(x_i)\right\rVert > 1 \rbrace$ \;
|
|
\Si{$K = \emptyset$}{
|
|
\Si{$\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n) \text{ satisfait contraintes}$}{
|
|
\Retour{$\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$}
|
|
}
|
|
\Sinon{\Retour{$\emptyset$}}
|
|
}
|
|
Choisir une variable $x_i \in K$\;
|
|
Choisir une valeur $v\in \mathtt{dom}(x_i)$\;
|
|
$S \leftarrow \texttt{FouilleEnProfondeurComplète}(\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_{i-1}),\lbrace v \rbrace, \mathtt{dom}(x_{x+1}), \ldots, \mathtt{dom}(x_{n}))$\;
|
|
\Si{$S=\emptyset$}{$\mathtt{dom}(x_i) \leftarrow \mathtt{dom}(x_i) \setminus \lbrace v \rbrace$}
|
|
}
|
|
\Retour{$S$}
|
|
}
|
|
\caption{FouilleEnProfondeurComplète($\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$)}
|
|
\label{alg:fouilleprofcomp}
|
|
\end{algorithm}
|
|
|
|
\paragraph{Fouille en profondeur avec retours arrières}
|
|
|
|
On améliore l'algorithme précédent en validant les contraintes pour chaque solution partielle. Algorithme \ref{alg:fouilleprofretarr}. Seul un sous-ensemble des noeuds est exploré. Permet de résoudre certains problèmes en temps polynomial.
|
|
|
|
\begin{algorithm}[H]
|
|
\DontPrintSemicolon
|
|
\Deb{
|
|
\Repeter{$S \neq \emptyset$}{
|
|
$K \leftarrow \lbrace x_i \mid \left\lVert \mathtt{dom}(x_i)\right\rVert > 1 \rbrace$ \;
|
|
$P \leftarrow \lbrace x_i \mid \left\lVert \mathtt{dom}(x_i)\right\rVert = 1 \rbrace$
|
|
\Pour{$C_j \in \mathcal{C}$}{
|
|
\Si{$Portée(C_j) \subseteq P \wedge \neg C_j$}{\Retour{$\emptyset$}}
|
|
}
|
|
\Si{$C = \emptyset$}{ \Retour{$\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$}}
|
|
Choisir une variable $x_i \in K$\;
|
|
Choisir une valeur $v\in \mathtt{dom}(x_i)$\;
|
|
$S \leftarrow \texttt{FouilleEnProfondeurRetArr}(\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_{i-1}),\lbrace v \rbrace, \mathtt{dom}(x_{x+1}), \ldots, \mathtt{dom}(x_{n}))$\;
|
|
\Si{$S=\emptyset$}{$\mathtt{dom}(x_i) \leftarrow \mathtt{dom}(x_i) \setminus \lbrace v \rbrace$}
|
|
}
|
|
\Retour{$S$}
|
|
}
|
|
\caption{FouilleEnProfondeurRetArr($\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$)}
|
|
\label{alg:fouilleprofretarr}
|
|
\end{algorithm}
|
|
|
|
\paragraph{Vérification anticipée}
|
|
|
|
S'il reste une seule variable non instanciée, itérer sur toutes les valeurs du domaine de celle-ci. Explore un sous-ensemble de noeuds explorés par la fouille avec retours arrières. Certains problèmes peuvent être résolus sans retour arrière.
|
|
|
|
\subsection{Filtrage des domaines}
|
|
\label{sec:ch2filt}
|
|
|
|
\begin{itemize}
|
|
\item \textbf{Algorithme de filtrage}: domaine des variables dans la portée de la contrainte, modifie les domaines
|
|
\item Un algorithme de filtrage par contrainte
|
|
\end{itemize}
|
|
|
|
\paragraph{Support}
|
|
|
|
Affectation de variables (tuple) qui satisfait une contrainte
|
|
|
|
\begin{itemize}
|
|
\item Types de support:
|
|
\begin{itemize}
|
|
\item Support de domaine: tuple $t$ satisfait $C$ tel que $t[i] \in mathtt{dom}(X_i)$et $\lbrace x_i = t[i] \forall 1 \leq i \leq n$
|
|
\item Support d'intervalle tuple $t$ satisfait $C$ tel que $min(\mathtt{dom}(X_i)) \leq t[i] \leq max(\mathtt{dom}(X_i))$ et $\lbrace x_i = t[i] \forall 1 \leq i \leq n$
|
|
\end{itemize}
|
|
\item Propriétés:
|
|
\begin{itemize}
|
|
\item Support de domaine $\subset$ Support d'intervalle
|
|
\item Support d'intervalle: ne garantit pas l'existence d'une solution pour la contrainte
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\paragraph{Cohérence}
|
|
|
|
Algorithme de \textbf{filtrage}: retire les valeurs d'un domaine pour lesquelles il n'y a pas de support
|
|
|
|
Niveaux de cohérence:
|
|
\begin{itemize}
|
|
\item Domaine: $\exists$ support de \textbf{domaine} pour toute variable $X$ de la portée de la contrainte et toute valeur $v$ dans le domaine de $X$.
|
|
\item Intervalle: $\exists$ support d'\textbf{intervalle} pour toute variable $X$ de la portée de la contrainte et toute valeur $v$ dans le domaine de $X$.
|
|
\item Bornes: $\exists$ support d'\textbf{intervalle} pour toute variable $X$ de la portée de la contrainte et la plus petite et la plus grande valeur du domaine de $X$.
|
|
\end{itemize}
|
|
|
|
Propriétés des cohérences:
|
|
\begin{itemize}
|
|
\item Cohérence de domaine $\subset$ Cohérence d'intervalle $\subset$ Cohérence de bornes
|
|
\item Cohérence locale: on a filtré itérativement les contraintes d'un problème
|
|
\item Algorithme \ref{alg:fouilleproffiltrage}
|
|
\end{itemize}
|
|
|
|
\begin{algorithm}[H]
|
|
\DontPrintSemicolon
|
|
\Deb{
|
|
\Repeter{$S \neq \emptyset$}{
|
|
Filtrer les domaines jusqu'à la cohérence locale \;
|
|
$K \leftarrow \lbrace x_i \mid \left\lVert \mathtt{dom}(x_i)\right\rVert > 1 \rbrace$ \;
|
|
\Si{$\exists dom(X_i)=\emptyset$}{$\emptyset$}
|
|
\Si{$C = \emptyset$}{ \Retour{$\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$}}
|
|
Choisir une variable $x_i \in K$\;
|
|
Choisir une valeur $v\in \mathtt{dom}(x_i)$\;
|
|
$S \leftarrow \texttt{FouilleEnProfondeurFiltrage}(\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_{i-1}),\lbrace v \rbrace, \mathtt{dom}(x_{x+1}), \ldots, \mathtt{dom}(x_{n}))$\;
|
|
\Si{$S=\emptyset$}{$\mathtt{dom}(x_i) \leftarrow \mathtt{dom}(x_i) \setminus \lbrace v \rbrace$}
|
|
}
|
|
\Retour{$S$}
|
|
}
|
|
\caption{FouilleEnProfondeurFiltrage($\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$)}
|
|
\label{alg:fouilleproffiltrage}
|
|
\end{algorithm}
|
|
|
|
\paragraph{Propagation des contraintes}
|
|
|
|
Méthode efficace pour obtenir la cohérence locale
|
|
|
|
\begin{itemize}
|
|
\item À chaque noeud de l'arbre, on applique la cohérence locale puis instancie une variable $X$
|
|
\item On filtre les contraintes contenant $X$. Si d'autres variables $Y$ voient leur domaine modifié, on filtre ensuite les contraintes sur $Y$ ainsi de suite. On garde une liste de contraintes à vérifier.
|
|
\item On ordonne $S$ en donnait priorité aux contraintes qui filtrent davantage de valeurs en moins de temps
|
|
\end{itemize}
|
|
|
|
\begin{algorithm}[H]
|
|
\DontPrintSemicolon
|
|
\Deb{
|
|
$S \leftarrow \lbrace C_k \mid X_i \in Portée(C_k) \rbrace$\;
|
|
\Tq{$S \neq \emptyset$}{
|
|
Choisir une contrainte $C_k$ dans $S$\;
|
|
Filtrer $C_k$\;
|
|
\Si{la contrainte n'est pas satisfiable}{\Retour{Échec}}
|
|
\PourCh{$X_j \mid dom(X_j) filtré$}{
|
|
$S \leftarrow S \cup \lbrace C_a \mid X_j \in Portée(C_a) \rbrace$
|
|
}
|
|
$S \leftarrow S \setminus \lbrace C_k \rbrace$
|
|
}
|
|
\Retour{Succès}
|
|
}
|
|
\caption{PropagationDesContraintes($X_i,C_1,\ldots,C_m$)}
|
|
\label{alg:propcontr}
|
|
\end{algorithm}
|
|
|
|
\paragraph{Types de filtrage}
|
|
|
|
\begin{itemize}
|
|
\item Instanciation: toutes les valeurs retirées sauf une
|
|
\item ValeurSupprimée: Une valeur est supprimée du domaine
|
|
\item BorneInferieure: La borne inférieure est augmentée
|
|
\item BorneSuperieure: La borne supérieure est diminuée
|
|
\end{itemize}
|
|
|
|
Idéal: Un algorithme de filtrage pour chaque par type de filtrage pour les autres variables. Il est moins couteux de rétablir la cohérence que l'appliquer la première fois.
|
|
|
|
\paragraph{Branch \& Bound}
|
|
|
|
Optimisation: En minimisant $X$, si on trouve une solution où $X=v$, on ajoute la contrainte $X<v$ au problème. Cette contrainte filtre al borne supérieure et les autres la borne inférieure. Si la borne inférieure est supérieure à la borne supérieure de cette nouvelle contrainte, on déclenche un retour arrière.
|
|
|
|
\paragraph{Cohérence de singleton}
|
|
|
|
Affecter temporairement une valeur à une variable, puis appliquer la cohérence locale.
|
|
S'il n'y a pas de cohérence locale, on retire cette valeur du domaine.
|
|
En pratique, on teste chaque paire variable/valeur une seule fois.
|
|
|
|
\paragraph{Cohérence de chemin}
|
|
|
|
Créer un graphe où chaque paire variable et valeur représente un noeud. On ajoute les arêtes entre les noeuds si aucune contrainte n'empêche une solution partielle incluant ces deux noeuds.
|
|
|
|
On vérifie si pour chaque arête, il existe une chemin de longueur $l$ reliant les deux noeuds. Sinon on supprime l'arête. Si un noeud est isolé du graphe, on le supprime. Il existe $n!$ permutations.
|
|
|
|
On applique généralement la cohérence de chemin de longueur 2 qui est équivalente et a $\binom{n}{3}$ permutations. La complexité est $\mathcal{O}(n^3)$.
|
|
|
|
%%% Local Variables:
|
|
%%% mode: latex
|
|
%%% TeX-master: "notes_de_cours"
|
|
%%% End:
|