206
Problèmes de satisfaction de contraintes
valeurs. Le choix de l'ordre des valeurs dépend en général du domaine.
L'ordre de vérification des contraintes permet de diminuer le nombre de tests de satisfaction de contraintes. On choisit en général de vérifier en premier les contraintes les
moins satisfiables.
Exercice : Modifier le programme de Sudoku pour qu'il commence par instancier les
variables de plus petit domaine.
12. 7 La recherche avec déviations limitées
De nombreux problèmes peuvent être résolus par un algorithme de recherche parce
qu'on dispose d'heuristiques pour ordonner les essais. Ces heuristiques permettent de
commencer par les essais qui ont le plus de chances d'amener vers les solutions. La recherche avec déviation limitée (limited discrepancy search) [42] est un algorithme de recherche qui permet de trouver des solutions à moindre coût quand l'heuristique d'ordonnancement des essais est défaillante sur un petit nombre de choix. Supposons par exemple
que l'heuristique ne soit pas défaillante, il suffirait alors de toujours prendre la première
valeur pour arriver à la solution. Supposons maintenant que l'heuristique se trompe une
seule fois, il faudra envisager les valeurs différentes de la première une seule fois sur le
chemin vers la solution. Or on ne sait pas à quel endroit de la recherche il faut envisager
les autres valeurs. On va donc envisager toutes les déviations possibles à partir du chemin
qui prend toujours la première valeur, et pour chacune des déviations on va continuer à ne
tenter qu'un seul essais après avoir pris la déviation. Si la profondeur de la recherche est
p, il y a p déviations possibles. On peut aussi envisager d'effectuer deux déviations, il y a
alors px ( � -l) chemins possibles.
La recherche avec déviations limitées recherche tous les chemins qui comporte un
nombre limité de déviations. Elle commence par le chemin avec zéro déviation, puis celui
avec une déviation, et incrémente ensuite le nombre de déviations permises à chaque
recherche infructueuse.
Exercice : Utiliser la recherche avec déviations limitées pour résoudre le Sudoku.
12.8 Les contraintes globales
Un exemple de contrainte globale est la contrainte all-diff qui porte sur un ensemble
de variables et qui vérifie qu'elles sont toutes différentes. Les contraintes globales permettent de formuler les problèmes plus élégamment et permettent aussi de mieux propager les contraintes. Un exemple d'utilisation des contraintes globales est l'utilisation de
2n contraintes n-aire all-diff pour modéliser les lignes et les colonnes du Sudoku.
Problèmes de satisfaction de contraintes
valeurs. Le choix de l'ordre des valeurs dépend en général du domaine.
L'ordre de vérification des contraintes permet de diminuer le nombre de tests de satisfaction de contraintes. On choisit en général de vérifier en premier les contraintes les
moins satisfiables.
Exercice : Modifier le programme de Sudoku pour qu'il commence par instancier les
variables de plus petit domaine.
12. 7 La recherche avec déviations limitées
De nombreux problèmes peuvent être résolus par un algorithme de recherche parce
qu'on dispose d'heuristiques pour ordonner les essais. Ces heuristiques permettent de
commencer par les essais qui ont le plus de chances d'amener vers les solutions. La recherche avec déviation limitée (limited discrepancy search) [42] est un algorithme de recherche qui permet de trouver des solutions à moindre coût quand l'heuristique d'ordonnancement des essais est défaillante sur un petit nombre de choix. Supposons par exemple
que l'heuristique ne soit pas défaillante, il suffirait alors de toujours prendre la première
valeur pour arriver à la solution. Supposons maintenant que l'heuristique se trompe une
seule fois, il faudra envisager les valeurs différentes de la première une seule fois sur le
chemin vers la solution. Or on ne sait pas à quel endroit de la recherche il faut envisager
les autres valeurs. On va donc envisager toutes les déviations possibles à partir du chemin
qui prend toujours la première valeur, et pour chacune des déviations on va continuer à ne
tenter qu'un seul essais après avoir pris la déviation. Si la profondeur de la recherche est
p, il y a p déviations possibles. On peut aussi envisager d'effectuer deux déviations, il y a
alors px ( � -l) chemins possibles.
La recherche avec déviations limitées recherche tous les chemins qui comporte un
nombre limité de déviations. Elle commence par le chemin avec zéro déviation, puis celui
avec une déviation, et incrémente ensuite le nombre de déviations permises à chaque
recherche infructueuse.
Exercice : Utiliser la recherche avec déviations limitées pour résoudre le Sudoku.
12.8 Les contraintes globales
Un exemple de contrainte globale est la contrainte all-diff qui porte sur un ensemble
de variables et qui vérifie qu'elles sont toutes différentes. Les contraintes globales permettent de formuler les problèmes plus élégamment et permettent aussi de mieux propager les contraintes. Un exemple d'utilisation des contraintes globales est l'utilisation de
2n contraintes n-aire all-diff pour modéliser les lignes et les colonnes du Sudoku.