Propagation et Satisfaction de Contraintes


Certains problèmes peuvent être modélisés en utilisant un ensemble de variables mathématiques, et en exprimant un certain nombre de contraintes permettant de relier ces variables, et ainsi restreindre les valeurs qui peuvent leur être assignées.


Puisqu'on dispose d'un nombre fini de variables pouvant prendre (c'est l'hypothèse que nous émettrons dans un premier temps) un nombre fini de valeurs, la résolution d'un problème peut consister en l'analyse de toutes les combinaisons possibles variable/valeur pour les valider ou non. Le temps nécessaire pour cela peut bien entendu vite devenir prohibitif.


Nous abordons d'abord les principes généraux d'une telle modélisation d'un problème, et supposons une analyse au moyen d'un arbre de recherche représentant les choix de valeurs effectués et ceux à venir.
Nous voyons alors des techniques permettant, au fur et à mesure de l'analyse, de réduire l'ensemble des combinaisons à analyser. Il s'agit de réduire les tests à effectuer, et si possible de ne pas émettre une hypothèse (variable = valeur) s'il est possible de déterminer à l'avance que cela ne peut conduire à aucune solution.