9.5 Les heuristiques admissibles
171
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FIGURE 9.2 - Position finale au Taquin 4x4.
Un coup consiste à remplacer la case vide, par une de ses cases adjacentes qui devient
alors à son tour vide. Trouver une solution optimale aux Taquins NxN est un problème
NP-difficile.
La position finale du Taquin 4x4 est donnée dans la figure 9.2.
Exercice : Définir une classe Position qui représente une position au Taquin 4x4 à
l ' aide d' un tableau unidimensionnel. On définira un coup dans une position par un entier
qui correspond à la case que l ' on veut bouger. É crire les fonctions membres de cette classe
pour initialiser la position, jouer un coup, et une fonction qui pour mélanger la position
joue au hasard un nombre de coups donné en paramètre, à partir de la position finale.
9.5 Les heuristiques admissibles
Les heuristiques que nous utiliserons pour le calcul de plus court chemin dans les jeux
évaluent la plupart du temps le nombre de coups qui reste à jouer.
Une heuristique est admissible si elle ne surestime jamais la longueur du plus court
chemin qui reste à parcourir avant d' atteindre la position finale. Une heuristique admissible donne toujours une valeur plus petite ou égale à la valeur du plus court chemin.
Pour chaque noeud on peut calculer une fonction f qui estime une borne minimale sur la
longueur totale du chemin qui passe par ce noeud pour aller à la position finale.
Pour chaque position p on calcule une évaluation : f (p) = g(p) + h(p) . La fonction
g(p) est la longueur du chemin parcouru pour atteindre la position courante à partir de la
position initiale ; h(p) est une heuristique admissible qui estime la longueur minimale du
chemin qui reste à parcourir avant d' arriver à la position finale depuis la position courante.
f(p) est donc une borne inférieure sur la longueur finale minimale du chemin qui passe
par la position courante.
Une heuristique admissible simple et efficace pour le Taquin est la distance de Manhattan. Pour la calculer on fait la somme, pour chaque case non vide, du nombre de coups
qu' il faudrait pour déplacer la case vers sa case finale si toutes les autres cases étaient
vides.
171
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FIGURE 9.2 - Position finale au Taquin 4x4.
Un coup consiste à remplacer la case vide, par une de ses cases adjacentes qui devient
alors à son tour vide. Trouver une solution optimale aux Taquins NxN est un problème
NP-difficile.
La position finale du Taquin 4x4 est donnée dans la figure 9.2.
Exercice : Définir une classe Position qui représente une position au Taquin 4x4 à
l ' aide d' un tableau unidimensionnel. On définira un coup dans une position par un entier
qui correspond à la case que l ' on veut bouger. É crire les fonctions membres de cette classe
pour initialiser la position, jouer un coup, et une fonction qui pour mélanger la position
joue au hasard un nombre de coups donné en paramètre, à partir de la position finale.
9.5 Les heuristiques admissibles
Les heuristiques que nous utiliserons pour le calcul de plus court chemin dans les jeux
évaluent la plupart du temps le nombre de coups qui reste à jouer.
Une heuristique est admissible si elle ne surestime jamais la longueur du plus court
chemin qui reste à parcourir avant d' atteindre la position finale. Une heuristique admissible donne toujours une valeur plus petite ou égale à la valeur du plus court chemin.
Pour chaque noeud on peut calculer une fonction f qui estime une borne minimale sur la
longueur totale du chemin qui passe par ce noeud pour aller à la position finale.
Pour chaque position p on calcule une évaluation : f (p) = g(p) + h(p) . La fonction
g(p) est la longueur du chemin parcouru pour atteindre la position courante à partir de la
position initiale ; h(p) est une heuristique admissible qui estime la longueur minimale du
chemin qui reste à parcourir avant d' arriver à la position finale depuis la position courante.
f(p) est donc une borne inférieure sur la longueur finale minimale du chemin qui passe
par la position courante.
Une heuristique admissible simple et efficace pour le Taquin est la distance de Manhattan. Pour la calculer on fait la somme, pour chaque case non vide, du nombre de coups
qu' il faudrait pour déplacer la case vers sa case finale si toutes les autres cases étaient
vides.