Algorithmes de propagation locale

En préambule de ce chapitre, nous dirons que la recherche d’un algorithme efficace qui pourrait satisfaire tout type de contraintes en utilisant n’importe quel domaine et n’importe quel comparateur serait un essai rutile. Ce chapitre donne un aperçu des différents algorithmes existants pour le traite­ ment des hiérarchies de contraintes. Ce chapitre décrit la réponse à la question essentielle posée avant de concevoir tel ou tel algorithme, et qui est : « que fait le système lorsque l’ensemble des con­ traintes est un ensemble sur-contraint (pas de solution qui satisfasse cet ensemble) ou lorsque l’ensemble des contraintes est un ensemble sous-contraint (il y a plusieurs solutions qui satisfont cet ensemble) ».

Si le résolveur gère les contraintes d’une application d’interface utilisateur, alors il n’est pas acceptable de signaler une erreur de manipulation. La théorie des hiérarchies de contraintes décrite dans les chapitres précédents indique une voie pour spécifier déclarativement comment le résolveur doit réagir face à cette situation. Une hiérarchie de contraintes est un ensemble de contraintes où chaque contrainte possède une éti­ quette qui exprime l’importance de cette contrainte dans le système (ou la préférence de cette con­ trainte par rapport aux autres contraintes). Etant donnée une hiérarchie de contraintes sur-contrainte, le résolveur peut laisser certaines contraintes parmi les moins préférées non satisfaites pour satis­ faire celles qui sont les plus préférées. Si la hiérarchie est sous-contrainte, le résolveur peut choisir n’importe quelle solution. L’utilisateur peut contrôler quelle solution choisir en ajoutant des con­ traintes étiquetées par des étiquettes faibles.

Ces contraintes pourront porter sur les variables pour exprimer le maintien de leurs valeurs (i.e. l’utilisateur exprime via ces contraintes son désir de ne pas changer les valeurs de certaines variables). Ce chapitre discutera aussi un peu plus en détail des algorithmes basés sur la propagation locale. Nous nous attarderons sur quelques aspects intéressants d’ingénierie de certains algorithmes, sur les critères de comparaison utilisés et enfin sur la com­ plexité de ces algorithmes. Ce chapitre est composé de quatre parties. La première décrit le principe de la propagation locale. La deuxième partie décrit quelques algorithmes existants basés sur la propagation locale pour la résolution de hiérarchie de contraintes fonctionnelles. La troisième partie donne un aperçu sur des algorithmes existants pour la résolution de hiérarchies ayant des contraintes d’égalité et d’inégalité. Et enfin la quatrième partie donne un aperçu sur d’autres algorithmes existants.

Propagation locale

Parmi les techniques ordinaires pour satisfaire les contraintes, il y a la technique nommée propa­ gation locale. Dans cette technique, la contrainte peut être utilisée pour déterminer la valeur d’une de ses variables au cas où les valeurs de ses n – 1 autres variables sont connues. Dans ces conditions, on parle de contrainte à une seule variable de sortie (uni-sortie). La contrainte peut être utilisée pour déterminer les valeurs de m de ses variables si les valeurs de ses n – m autres variables sont connues et si l’on dispose d’une méthode qui calcule ces m valeurs à partir des n – m variables. Dans ces con­ ditions, on parle de contrainte à plusieurs variables de sortie (multi-sorties). Il est bien évident que ces n – m variables peuvent aussi être calculées par d’autres contraintes et ainsi de suite. La propagation locale est similaire à la propagation des valeurs dans le réseau de contraintes. Cepen­ dant, un problème se pose qui est l’existence de contraintes multi-directionnelles dans le réseau et donc il existe plusieurs chemins potentiels de propagation. Le rôle des résolveurs de contraintes en général est de choisir quel chemin prendre. Dans le cas de hiérarchie de contraintes, le chemin à choisir est celui qui doit fournir « la meilleure  » solution (ou une des meilleures).

Chaque contrainte du réseau possède une ou plusieurs méthodes : il s’agit de petites procédures dont l’exécution d’une seule produit la satisfaction de la contrainte. Chaque méthode détermine la valeur d’une ou plusieurs variables de sortie à partir de celles d’entrée. Par exemple, la contrainte d’addi­ tion suivante : A + B – C a trois méthodes possibles :A*—C-B,B<r-C-Ae\C*—A + B. L’algorithme de propagation locale produit un chemin de propagation en sélectionnant une méthode de chaque contrainte de la hiérarchie (si la contrainte ne peut pas être satisfaite, cela voudrait dire que l’algorithme n’a pas pu sélectionner de méthode pour cette contrainte). Par conséquent, un che­ min produit par l’algorithme de propagation locale utilise au plus une méthode pour déterminer la valeur d’une variable de sortie d’une méthode d’une contrainte. Dans ce cas on considère que toute contrainte possédant une méthode dans ce chemin est satisfaite.