Généralisation de Houria pour l’intégration d’autres critères de comparaison

Généralisation de Houria pour l’intégration d’autres critères de comparaison

Un des points importants de la théorie des hiérarchies de contraintes est le fait de pouvoir définir différents types de comparateurs. Ces différents types de comparateurs doivent être jugés d’après la réponse à la question suivante : à quel degré représentent-ils l’intention de l’utilisateur dans des pro­ blèmes réels ? Le chapitre précédent décrit notre résolveur Houria basé sur le critère global Nombre- Contrainîes-Non-Satisfaites. Ce résolveur permet de trouver des solutions qui sont plus intuitives que celles obtenues par un résolveur intégrant un comparateur local (Pour un même système sur­ contraint, les solutions trouvées par le comparateur de ce résolveur satisfont plus de contraintes que celles trouvées par un critère local). Cependant, ce résolveur de même que les autres résolveurs exis­ tants, supposent que les contraintes d’une hiérarchie donnée sont uniquement étiquetées et non pon­ dérées par des poids réels. L’objectif de ce chapitre est de surmonter cette restriction et donc de pouvoir résoudre des hiérar­ chies où les contraintes sont étiquetées et pondérées par des poids (ou associées à des indices) réels différents. Plusieurs applications illustrent ce besoin, on citera ici deux exemples. Le premier type d’application est celui où l’utilisateur a besoin d’exprimer des contraintes dites de remplacement. Au sein d’une même classe dans la hiérarchie, on peut avoir deux types de contraintes : celles asso­ ciées à un indice fort dont la satisfaction sera considérée prioritaire, et celles associées à des indices moms forts et qui sont considérées comme des contraintes de remplacement. Dans ce cas, le résol­ veur doit d’abord considérer la satisfaction des contraintes associées à un indice fort et dans les cas d’échec (si cette satisfaction ne peut pas avoir lieu), considérer la satisfaction des contraintes de remplacement. Le deuxième type d’application est celui où le poids d’une contrainte traduit son degré d’importance dans la classe de la hiérarchie où elle se trouve. Dans ce cas et selon le compara­ teur utilisé, les contraintes pondérées par des poids forts ne sont pas forcément à satisfaire en prio­ rité (si l’on suppose qu’on utilise le comparateur Somme-Pondérée en utilisant l’erreur prédicat, et qu’on a la disjonction exclusive entre la satisfaction d’une contrainte pondérée à 0.9 et de deux con­ traintes pondérées à 0.5 chacune, alors ces dernières sont prioritaires pour la satisfaction).

Ce chapitre est composé de cinq parties : la première et la deuxième parties décrivent les définitions d’autres critères de comparaison globaux intégrés dans Houria ainsi que les relations entre les ensembles de solutions produits par ces différents critères et celui produit par le premier critère décrit au chapitre précédent. Chacune de ces deux parties décrit également les techniques utilisées pour la construction des graphes solutions correspondant au critère intégré. La troisième partie décrit les procédures généralisées (paramétrées par un type de comparateur) d’ajout et de retrait d’une contrainte à la hiérarchie. La quatrième partie traite la complexité et 1’implementation de Houria ainsi des mesures effectuées sur des problèmes générés aléatoirement. Enfin, la cinquième partie décrit une comparaison fonctionnelle entre Houria et les autres algorithmes de propagation locale présentés auparavant. Le deuxième critère de comparaison dans cet algorithme est le comparateur Cardinal-Pire-Cas. Ce comparateur utilise le nombre de contraintes satisfaites associées au plus fort indice de chaque classe dans la hiérarchie. L’ensemble des solutions obtenues par l’utilisation de ce comparateur est généralement de taille plus petite que celle de l’ensemble obtenu en utilisant le critère Localement- Prédicat-Meilleur ou encore celle de l’ensemble obtenu en utilisant le critère global Pire-Cas. Avant de définir ce critère, on présentera d’abord la définition du comparateur Pire-Cas.

Soient H= {HQ, H¡, H2j avec HQ la classe des contraintes requises. H¡ est la classe des contraintes étiquetées par l’étiquette forte. H2 est la classe des contraintes étiquetées par l’étiquette moyenne. HQ contient deux contraintes c0} et c02. H¡ contient quatre contraintes c¡¡, c¡2, c¡¡, c¡4 et ont respective­ ment pour indices 0.9, 0.9, 0.9, 0.8. H2 contient trois contraintes c2¡, c22, c23 qui ont respectivement pour indices 0.9, 0.9, 0.9. On rappele que l’erreur prédicat utilisée rend 0 si la contrainte est satis­ faite et 1 sinon. On suppose aussi que : Après application de 8, le nombre de contraintes non satisfaites ayant le plus fort indice par niveau jusqu’au niveau k-1 est égal à celui obtenu après application de r¡. Dans ce cas au niveau k, après application de 8, il existe au moins une contrainte satisfaite par 8 (et non par r\) telle qu’elle possède un indice plus fort que celui de toute contrainte satisfaite parti (puis­ que Pire-Cas(B, r\, H)). Par conséquent, on a bien Cardinal-Pire-Cas(B, T\, H) et donc l’impli­ cation est vraie,