Problèmes de Satisfaction de Contraintes (CSP)

Problèmes de Satisfaction de Contraintes (CSP)

Une grande partie clés problèmes de l’Intelligence Artificielle et d’autres domaines de l’informatique peuvent être considérés comme des cas particuliers des problèmes de satisfaction de contraintes (CSP), [Nad90]. Cette thèse concerne les problèmes de satisfaction de contraintes qui peuvent être définis de la manière suivante. Les données du problème sont un ensemble fini de variables, un domaine fini pour chaque variable et un ensemble de contraintes. Chaque contrainte est définie sur un sous-ensemble de l’ensemble de variables et elle limite les combinaisons de valeurs que les variables qui appartiennent à ce sous-ensemble peuvent avoir. Le but est de trouver des valeurs dans les domaines des variables qui satisfassent toutes les contraintes. Plus formellement, nous définissons dans les sections suivantes les concepts utilisés par les CSP. 1.1 Concepts et notations Définition 1.1.1 (Problème de Satisfaction de Contraintes) Un problème de satisfaction de contraintes ou CSP. P = (V, D, Ç) est défini par: – un ensemble \ ‘ = {A’j,… . A’,.} de n variables – un ensemble D — {Du ,.., £)„} de n domaines finis -pour les variables de V. Le 5 Problèmes de Satisfaction de Contraintes (CSP)

PROBLÈMES DE SATISFACTION DE CONTRAINTES (CSP)

Concepts et notations doinamc D, est associé à la variable X, v,?i. eus trahie C = {Cj,. . .. C,,} de o contraintes. Chaque contrainte. C, est définie • jßu.r un. couple ! ;• ‘,, ‘/ »,); v; est un ensemble de variables {A »,,.. . .. À »;.,,,} C 1″ sur lesquelles porte la contrainte C¡. On appelle ari.té de. C, la longueur de la séquence v,, donc le cardinal de v.,: – r, est une relation, défi/nie par un sous-ensemble du produit cartésien Dn x … x Dh, des dornames associés aux variables de v,. Il représente les nuplets de valeurs autorisés pour ces variables. Définition 1.1.2 (Etre pertinente pour) Cluupie. variable X¡ est pertinente pour Ck (noté par Xj t> C¡J, si CY porte sur X,. V/’: € [1..7/J. Définition 1.1.3 (Ante de C,,) Et.an.t donné une. contrainte Ca et ses variables pertinentes, on définit Vanté de Ca ar , comme le nombre de variables pertinentes pour Ca. Définition 1.1.4 (CSP binaire) Un CSP binaire est un CSP P — (V, D, Q dont toutes les contraintes Ci & Ç ont une ante égale à 2, c ‘est à dire, chaque contrainte a exactement 2 variables pertinentes. Un CSP binaire peut être représenté par un graphe de contraintes dans lequel chaque nœud represente une variable, et chaque arc correspond à une contrainte entre 2 variables. Rossi et al. [RPD89] ont montré qu’il est possible de convertir un CSP avec des contraintes n-aires en un CSP binaire équivalent. C’est pour cela que la plupart, des recherches sur les méthodes pour la résolution de CSP avec domaines finis traitent, pour commencer, les CSP binaires, [Fre82l. Dans cette thèse, nous abordons 

PROBLÈMES DE SATISFACTION DE CONTRAINTES (CSP) 

Concepts et notations la résolution de CSP binaires en utilisant plus particulièrement leur représentation matricielle. Définition 1.1.5 (Matrice de Contraintes) Une Matrice de Contraintes R est un tableau rectangulaire r¡ X n, tel que R„,=RKy] 1 Si variable Xj E> Ca 0 sinon S’il s’agit d’un CSP binaire, dans R il y ajuste deux entrées non-nulles pour une contrainte Ca, comme cela est montré sur la figure 1.1. Dans l’exemple, les variables X-2 et A »„ sont les deux variables pertinentes pour Ca. Cela est représenté dans la matrice de contraintes avec le numéro 1 à l’intersection entre la colonne de chaque variable et la ligne correspondant à, Cn. Dans le graphe de contraintes, cela est indiqué par Parête a qui lie la variable Xo avec la variable A’„. ontra untes fi r X! O i ¡ V X2 [ !î Í) (Í t) anables 0 ! X-.i 0 Í) X 2 <* i* Xn Y y £ • / FlG. 1.1 – Matrice de Contraintes et son Graphe de Contraintes Définition 1.1.6 (Insta notation) Etant donne: un CSP P = (V,D,Ç), on appelle instanciation I une application qui associe à chaque variable A », G V une valeur I(A,) G D¡ Définition 1.1.7 (Instanciation Partielle) Etant donné un CSP P = (V, D,Ç). on appelle instanciation partielle I p de Vp = {Xp-,,. . ., XPi} Ç V une application qui associe à chaque variable XPt G Vp une videur 1P{XVI) G DPi (le domaine de XPi)  

Exemples de CSP

Les exemples suivants sont d’un intérêt particulier, car ils sont des prototypes pour une grande classe de problèmes pratiques. Le coloriage de graph e Le problème de coloriage de graphe avec 3 couleurs consiste à colorier un graphe non-orienté comprenant n nœuds. Chaque nœud doit être colorié avec une des trois couleurs disponibles de telle sorte que deux noeuds voisins n’aient pas la même, couleur. Ce problème est utilisé pour rnodéliser certains types de problèmes d’ordonnancement et de gestion de ressources. La figure 1.2 montre le problème de coloriage d’une carte avec 3 couleurs (noir, blanc, gris). Les contraintes sont toutes du même type: ne pas colorier avec la même couleur les pays voisins.  Les N-reines Placer sur un échiquier de N x N cases. N reines qui ne s’attaquent pas (suivant les règles classiques des échecs). Il s’agit d’un problème équivalent à la recherche d’un ensemble intérieurement stable (qui sera maximum) dans un graphe de Ar x N nœuds (un nœud pour chaque case), chaque arête correspondant à une diagonale, une verticale ou une horizontale. Il peut s’envisager pour d’autres types de pièces. Le problème du Zèbre Attribué à. Lewis Carroll, pasteur logicien et écrivain anglais auteur de nombreux autres puzzles. On considère cinq maisons, toutes de couleurs différentes (rouge, bleu, jaune, blanc, vert), dans lesquelles logent cinq personnes de profession différente (peintre, sculpteur, diplomate, docteur et violoniste) de nationalité différente (anglaise, espagnole, japonaise, norvégienne et italienne) ayant chacune une boisson favorite (thé. jus de fruits, café, lait et vin) et des animaux favoris (chien, escargots, renard, cheval et zèbre). On dispose des faits suivants: l’Anglais habite la maison rouge, l’Espagnol possède un chien, le Japonais est peintre, l’Italien boit du thé, le Norvégien habite la, première maison à gauche, le propriétaire de la maison verte boit du café, la maison verte est à droite de la blanche, le sculpteur élève des escargots.

Méthodes de résolution des CSP diplomate habite la maison jaune, on boit du lait dans la maison du milieu, le Norvégien habite à coté de la maison bleue, le violoniste boit du jus de fruit, le renard est dans la maison voisine du médecin, le cheval est à côté de la maison du diplomate. Il s’agit de trouver le possesseur du zèbre et le buveur de vin. En fait le problème n’admet qu’une seule solution et il s’agit de la trouver. CSP aléatoires t ne pratique qui devient de plus en plus courante est de tester un nouvel algorithme sur un jeu important de CSP binaires générés entièrement aléatoirement, |Sun95j. Chaque jeu de problèmes est décrit par quatre paramètres: n, le nombre de variables, m le nombre de valeurs de chaque domaine, p¡ la probabilité qu’il y ait nue contrainte entre deux variables, et p2 la probabilité conditionnelle qu’une paire de valeurs soit inconsistante pour un couple de variables, étant donné qu’il y a une contrainte entre les deux variables. Ces tests sont généralement utilisés pour juger très grossièrement les performances relatives de différents algorithmes, et pour déterminer pour quels problèmes (avec des graphes denses, contraintes difficiles) ils sont efficaces. Dans cette thèse, nous avons principalement testé nos algorithmes sur le problème de .’»-coloriage de graphe et sur les CSP binaires générés aléatoirement.