204
Problè mes de satisfaction de contraintes
12.2 Exemples de Problèmes
Une classe de problèmes connus sont les problèmes de cryptarithmétique où chaque
lettre correspond à un chiffre entre 0 et 9, de plus deux lettres différentes ont des valeurs
différentes et les lettres les plus à gauche ont des valeurs différentes de O. Un problème
célèbre est SEND + MORE = MONEY. D'autres problèmes amusants sont DONALD +
GERALD = ROBERT, ADAM + EVE + ON + A = RAFf, CROSS + ROADS = DANGER, FORTY + TEN + TEN = SIXTY.
Un autre problème classique est les N reines : le but est de placer sur un échiquier
NxN, N reines de façon à ce qu'aucune reine ne puissent prendre une autre reine directement.
Exercice : Donnez les variables, leurs valeurs possibles et les contraintes pour le problème des N reines. Trouver une solution au problème des 4 reines.
12.3 Le Backtrack
L' algorithme le plus simple pour résoudre un problème de satisfaction de contraintes
est l'algorithme de Backtrack. C'est un algorithme de force brute. Il commence par sélectionner l'ordre dans lequel instancier les variables, puis l'ordre dans lequel essayer les
valeurs, puis il affecte récursivement les valeurs aux variables.
Chaque fois qu'une variable est instanciée, toutes les contraintes qui la contiennent et
qui ne contiennent que des variables instanciées sont testées. Si une contrainte n'est pas
vérifiée, l'algorithme arrête sa recherche et essaie la valeur suivante pour la variable (c'est
ce qu'on appelle le Backtrack).
Un ensemble de variables instanciées est consistant s'il vérifie toutes les contraintes
vérifiables. Si un sous-ensemble de l'ensemble des contraintes n'est pas consistant, alors
tous les ensembles de variables instanciées qui le contiennent ne sont pas consistants.
C'est pourquoi on arrête la recherche dès qu'une contrainte n'est pas vérifiée.
L' arbre est exploré en profondeur d'abord pour minimiser la mémoire consommée et
parce qu'on connaît à l'avance la profondeur de recherche du problème.
On se place dans le cas particulier où le problème peut être modélisé à l'aide d'un
domaine de valeurs entières comprises entre zéro et une taille fixée.
Exercice : É crire une classe Domaineintervalle qui permettra de mémoriser
pour chaque variable son domaine de valeurs, la taille de ce domaine, ainsi que son instanciation. É crire ensuite un programme qui utilise le Backtrack pour résoudre le problème
des N reines sur un échiquier NxN.
Problè mes de satisfaction de contraintes
12.2 Exemples de Problèmes
Une classe de problèmes connus sont les problèmes de cryptarithmétique où chaque
lettre correspond à un chiffre entre 0 et 9, de plus deux lettres différentes ont des valeurs
différentes et les lettres les plus à gauche ont des valeurs différentes de O. Un problème
célèbre est SEND + MORE = MONEY. D'autres problèmes amusants sont DONALD +
GERALD = ROBERT, ADAM + EVE + ON + A = RAFf, CROSS + ROADS = DANGER, FORTY + TEN + TEN = SIXTY.
Un autre problème classique est les N reines : le but est de placer sur un échiquier
NxN, N reines de façon à ce qu'aucune reine ne puissent prendre une autre reine directement.
Exercice : Donnez les variables, leurs valeurs possibles et les contraintes pour le problème des N reines. Trouver une solution au problème des 4 reines.
12.3 Le Backtrack
L' algorithme le plus simple pour résoudre un problème de satisfaction de contraintes
est l'algorithme de Backtrack. C'est un algorithme de force brute. Il commence par sélectionner l'ordre dans lequel instancier les variables, puis l'ordre dans lequel essayer les
valeurs, puis il affecte récursivement les valeurs aux variables.
Chaque fois qu'une variable est instanciée, toutes les contraintes qui la contiennent et
qui ne contiennent que des variables instanciées sont testées. Si une contrainte n'est pas
vérifiée, l'algorithme arrête sa recherche et essaie la valeur suivante pour la variable (c'est
ce qu'on appelle le Backtrack).
Un ensemble de variables instanciées est consistant s'il vérifie toutes les contraintes
vérifiables. Si un sous-ensemble de l'ensemble des contraintes n'est pas consistant, alors
tous les ensembles de variables instanciées qui le contiennent ne sont pas consistants.
C'est pourquoi on arrête la recherche dès qu'une contrainte n'est pas vérifiée.
L' arbre est exploré en profondeur d'abord pour minimiser la mémoire consommée et
parce qu'on connaît à l'avance la profondeur de recherche du problème.
On se place dans le cas particulier où le problème peut être modélisé à l'aide d'un
domaine de valeurs entières comprises entre zéro et une taille fixée.
Exercice : É crire une classe Domaineintervalle qui permettra de mémoriser
pour chaque variable son domaine de valeurs, la taille de ce domaine, ainsi que son instanciation. É crire ensuite un programme qui utilise le Backtrack pour résoudre le problème
des N reines sur un échiquier NxN.