Introduction genérale
Sans contrainte, on tourne en rond.
Mathieu Chedid
Dans notre vie quotidienne on est en train de résoudre
et de satisfaire des problèmes de contraintes sans le savoir.
Comment préparer un plat qui soit délicieux tout
en prenant soin de notre santé?
Comment arriver à temps à destination sans faire
des accidents?
Comment bien vivre selon nos moyens?
Ce types de taches n'exige pas d'algorithme
sophistiquéou d'ordinateurs pour l'accomplir, mais on doit prendre en
compte que les problèmes deviennent plus compliqués lorsque le
nombre de variable et de contraintes croient, par exemple on trouve que
ça prend du temps pour choisir un film qui satisfait un grand nombre
d'amis. Imaginons maintenant, la difficultéet le temps qu'il faut pour
faire le planning des voyages des trains. Il faut faire en sorte que les trains
ne coïncident pas sur le même chemin, un conducteur ne peut pas
conduire deux trains simultanément, les voyages doivent se faire dans un
intervalle de temps limité, le nombre de voyageurs ne doit pas
dépasser la capacitédu train tout en satisfaisant tous les
voyageurs, etc... Donc, à chaque fois que la complexitédevient
importante, on est obligéd'avoir recourt aux ordinateurs pour nous aider
à trouver des solutions acceptables et efficaces en terme de temps.
Ce type de problème s'appelle Les problèmes de
satisfaction des contraintes ou CSP (Constraint Sa-
tisfaction Problem) De nos jours, les CSP font le sujet de
plusieurs recherches à la fois en intelligence
7
artificielle et en recherche opérationnelle. Ils sont
notamment au coeur de la programmation par contraintes, un domaine fournissant
des langages de modélisation de problèmes et des outils
informatiques les résolvant [9].
Nous nous intéressons, dans ce projet de fin
d'étude, à résoudre un problème CSP particulier.
Dans un premier temps, nous étudierons les problèmes de
satisfaction des contraintes, en général et quelques algorithmes
déjàproposés pour les résoudre. Dans le Chapitre 3,
nous allons poser le problème auquel nous nous intéressons puis
nous montrons que les algorithmes étudiés dans le Chapitre 2
demande beaucoup de temps pour le résoudre. Ensuite, nous
présentons notre propre algorithme, avec un exemple explicatif. Enfin,
nous présenterons une partie d'évaluation dans laquelle nous
listerons quelques résultats obtenues pour avoir une idée sur
l'efficacitéde notre algorithme. Nous terminerons par une conclusion
générale qui résume ce travail.
8
Chapitre 2
Problèmes de satisfaction de
contraintes
2.1 Qu'est-ce qu'une contrainte?
Une contrainte est une relation logique (une
propriétéqui doit être vérifiée) entre
différents inconnus, appelées variables, chacune prenant ses
valeurs dans un ensemble donné, appelédomaine. Ainsi, une
contrainte restreint les valeurs que peuvent prendre simultanément les
variables. Par exemple, la contrainte »x + 3 x y = 12» restreint les
valeurs que l'on peut affecter simultanément aux variables x et y.
2.1.1 Quelques caractéristiques des contraintes
Une contrainte est relationnelle : elle n'est pas
»dirigée» comme une fonction qui définit la valeur
d'une variable en fonction des valeurs des autres variables. Ainsi, la
contrainte »x-2xy = z» permet de déterminer z dès lors
que x et y sont connues, mais aussi x dès lors que y et z sont connues
et y dès lors que x et z sont connues.
Notons également qu'une contrainte est
déclarative : elle spécifie quelle relation on doit
retrouver entre les variables, sans donner de procédure
opérationnelle pour effectivement assurer/vérifier cette
relation. Ainsi, lorsqu'on pose la contrainte »x - 2 x y = z», on ne
s'occupe pas de donner un algorithme permettant de résoudre cette
équation.
Notons enfin que l'ordre dans lequel sont posées
les contraintes n'est pas significatif : la seule chose importante
à la fin est que toutes les contraintes soient satisfaites
(...cependant, dans certains langages de programmation par contraintes l'ordre
dans lequel les contraintes sont ajoutées peut avoir une influence
sur
9
l'efficacitéde la résolution...).
| 
