Chapitre 10
Bases de patterns
L' analyse rétrograde (cf chapitre 7) peut être utilisée pour calculer des bases de
patterns qui permettent d'accélérer la résolution de problèmes. Un pattern est un sousensemble d'une position.
10.1 Le Taquin
La fonction h a une grande influence sur 1 'efficacité de A* : plus les valeurs renvoyées
par h sont élevées (tout en restant admissibles), plus A* trouvera la solution rapidement.
La fonction utilisée traditionnellement pour calculer une heuristique admissible pour le
Taquin est la distance de Manhattan. On peut améliorer h en utilisant les bases de données
de patterns.
Pour construire une base de patterns pour le Taquin, on choisit un sous-ensemble des
pièces, et on calcule pour chaque arrangement possible de ce sous ensemble le nombre
minimal de déplacements qu'il est nécessaire de faire pour remettre toutes les pièces du
sous-ensemble à leurs places.
Les patterns engendrés donnent un chemin minimal jusqu'à la position finale qui est
plus grand que la distance de Manhattan, mais plus petit que le nombre réel. Pour évaluer
le chemin qui reste à parcourir jusqu'à la position finale depuis une position donnée, le
programme reconnaît tous les sous-buts qu'il a calculé sur la position, et l'heuristique
admissible consiste à prendre le maximum de toutes les valeurs calculées pour ces sousbuts. L' utilisation de bases de données de patterns permet de résoudre les problèmes de
Taquin 4x4 avec mille fois moins de noeuds [30].
Prenons pour exemple le Taquin 4x4. On décide de calculer toutes les configurations
des 7 premières pièces.
Bases de patterns
L' analyse rétrograde (cf chapitre 7) peut être utilisée pour calculer des bases de
patterns qui permettent d'accélérer la résolution de problèmes. Un pattern est un sousensemble d'une position.
10.1 Le Taquin
La fonction h a une grande influence sur 1 'efficacité de A* : plus les valeurs renvoyées
par h sont élevées (tout en restant admissibles), plus A* trouvera la solution rapidement.
La fonction utilisée traditionnellement pour calculer une heuristique admissible pour le
Taquin est la distance de Manhattan. On peut améliorer h en utilisant les bases de données
de patterns.
Pour construire une base de patterns pour le Taquin, on choisit un sous-ensemble des
pièces, et on calcule pour chaque arrangement possible de ce sous ensemble le nombre
minimal de déplacements qu'il est nécessaire de faire pour remettre toutes les pièces du
sous-ensemble à leurs places.
Les patterns engendrés donnent un chemin minimal jusqu'à la position finale qui est
plus grand que la distance de Manhattan, mais plus petit que le nombre réel. Pour évaluer
le chemin qui reste à parcourir jusqu'à la position finale depuis une position donnée, le
programme reconnaît tous les sous-buts qu'il a calculé sur la position, et l'heuristique
admissible consiste à prendre le maximum de toutes les valeurs calculées pour ces sousbuts. L' utilisation de bases de données de patterns permet de résoudre les problèmes de
Taquin 4x4 avec mille fois moins de noeuds [30].
Prenons pour exemple le Taquin 4x4. On décide de calculer toutes les configurations
des 7 premières pièces.