12.9 La recherche lo cale
207
12.9 La recherche locale
Une autre approche au problème de satisfaction de contraintes est de modifier une
instanciation totale de toutes les variables qui viole une ou plusieurs contraintes de façon
à se rapprocher d'une solution. Par exemple, pour le problème des 8 reines, on place les 8
reines sur le damier en évitant au maximum les prises au fur et à mesure des placements,
puis on bouge les reines une par une jusqu'à ce qu'on trouve une solution.
L' heuristique la plus naturelle consiste à déplacer la reine qui est en prise avec le plus
d'autres reines, et de la déplacer vers une position qui est en prise avec le moins de reines
possibles.
Cette heuristique est simple mais elle marche très bien, beaucoup mieux que le Backtrack. Les algorithmes de Backtrack peuvent résoudre des problèmes contenant des centaines de reines alors que la recherche locale permet de résoudre des problèmes contenant
beaucoup plus de reines.
L'inconvénient de la recherche locale est qu'elle ne permet pas toujours de trouver
une solution, même si une solution existe. De plus si il n'y a pas de solution, l'algorithme
ne termine pas alors que le Backtrack trouvera qu'il n'y a pas de solution.
12.10 La recherche Monte-Carlo imbriquée
On peut réutiliser l'algorithme de recherche Monte-Carlo imbriquée vu dans le chapitre sur la résolution de puzzles par la méthode de Monte-Carlo. Dans le cas d'un problème de satisfaction de contraintes l'évaluation d'une position est le nombre de variables
qu'on a réussi à affecter sans tomber sur une inconsistance. C'est l'évaluation que retournera une partie aléatoire. Les parties aléatoires consistent à choisir au hasard une affectation consistante à une variable.
Exercice : É crire un programme de recherche Monte-Carlo imbriquée pour le Sudoku
25x25.
12.11 Corrigés des exercices
12.11.1 Les N reines
On utilise une variable par colonne. Les variables sont notées C 1 , C 2 , ... , CN. Les
domaines de valeurs des variables sont {1, 2, ... , N}. les contraintes sont :
207
12.9 La recherche locale
Une autre approche au problème de satisfaction de contraintes est de modifier une
instanciation totale de toutes les variables qui viole une ou plusieurs contraintes de façon
à se rapprocher d'une solution. Par exemple, pour le problème des 8 reines, on place les 8
reines sur le damier en évitant au maximum les prises au fur et à mesure des placements,
puis on bouge les reines une par une jusqu'à ce qu'on trouve une solution.
L' heuristique la plus naturelle consiste à déplacer la reine qui est en prise avec le plus
d'autres reines, et de la déplacer vers une position qui est en prise avec le moins de reines
possibles.
Cette heuristique est simple mais elle marche très bien, beaucoup mieux que le Backtrack. Les algorithmes de Backtrack peuvent résoudre des problèmes contenant des centaines de reines alors que la recherche locale permet de résoudre des problèmes contenant
beaucoup plus de reines.
L'inconvénient de la recherche locale est qu'elle ne permet pas toujours de trouver
une solution, même si une solution existe. De plus si il n'y a pas de solution, l'algorithme
ne termine pas alors que le Backtrack trouvera qu'il n'y a pas de solution.
12.10 La recherche Monte-Carlo imbriquée
On peut réutiliser l'algorithme de recherche Monte-Carlo imbriquée vu dans le chapitre sur la résolution de puzzles par la méthode de Monte-Carlo. Dans le cas d'un problème de satisfaction de contraintes l'évaluation d'une position est le nombre de variables
qu'on a réussi à affecter sans tomber sur une inconsistance. C'est l'évaluation que retournera une partie aléatoire. Les parties aléatoires consistent à choisir au hasard une affectation consistante à une variable.
Exercice : É crire un programme de recherche Monte-Carlo imbriquée pour le Sudoku
25x25.
12.11 Corrigés des exercices
12.11.1 Les N reines
On utilise une variable par colonne. Les variables sont notées C 1 , C 2 , ... , CN. Les
domaines de valeurs des variables sont {1, 2, ... , N}. les contraintes sont :