172
Recherche de la solution la plus courte pour les puzzles
2
6
9
4
14
10
15
5
1
11
8
7
3
13 12
FIGURE 9.3 - Une position au Taquin 4x4.
Exercice : Quelle valeur renvoie l 'heuristique de Manhattan pour la position de la
figure 9.3 ? Modifier la classe Position pour mettre à jour à chaque coup l 'heuristique
de Manhattan. É crire ensuite une fonction membre de Position qui permet de détecter la
position finale.
9.6 L'algorithme A*
L' algorithme A * [4 1] accélère la recherche de plus court chemin à l ' aide d' heuristiques admissibles. Le choix d' une bonne heuristique admissible est le paramètre qui
influence le plus l 'efficacité de A * . D 'une manière générale, on cherche à définir des
heuristiques admissibles qui renvoient les plus grandes valeurs possibles tout en restant
admissibles (c'est à dire en renvoyant toujours une valeur plus petite que la valeur du plus
court chemin entre la position courante et la position finale).
Dans l' implémentation de A* , on utilise deux ensembles de noeuds : l 'ensemble 0
des ouverts et l 'ensemble F des fermés. Un noeud correspond à une position et les arcs
orientés entre les noeuds à des coups. 0 contient tous les noeuds qui n 'ont pas de fils,
autrement dit toutes les feuilles de l 'arbre. F contient tous les noeuds qui ont eu des
fils, autrement dit, tous les noeuds internes de l ' arbre. On définit pour chaque noeud une
fonction f qui est un minorant du plus court chemin passant par le noeud. On calcule f en
sommant la taille du chemin déjà parcouru nommé g et l ' heuristique admissible nommée
h. A chaque étape du développement de l' arbre de recherche, on choisit de développer,
parmi les ouverts, le noeud qui a la fonction f minimale. L' algorithme se termine quand la
position finale est atteinte. On peut voir que l ' algorithme trouve bien le plus court chemin,
puisque tous les ouverts qui restent lorsqu' on a atteint la position finale ont des chemins
de taille supérieure au chemin trouvé.
Exercice : É crire une classe pour représenter un noeud de l' arbre de recherche.
Exercice : On veut disposer d' une fonction qui insère un noeud à la bonne place
dans l 'ensemble des ouverts trié par rapport à f. Programmer la fonction void insere
(Noeud * noeud ) de façon à ce que l ' insertion et la recherche d' un noeud de plus
petit f se fasse le plus rapidement possible.
Recherche de la solution la plus courte pour les puzzles
2
6
9
4
14
10
15
5
1
11
8
7
3
13 12
FIGURE 9.3 - Une position au Taquin 4x4.
Exercice : Quelle valeur renvoie l 'heuristique de Manhattan pour la position de la
figure 9.3 ? Modifier la classe Position pour mettre à jour à chaque coup l 'heuristique
de Manhattan. É crire ensuite une fonction membre de Position qui permet de détecter la
position finale.
9.6 L'algorithme A*
L' algorithme A * [4 1] accélère la recherche de plus court chemin à l ' aide d' heuristiques admissibles. Le choix d' une bonne heuristique admissible est le paramètre qui
influence le plus l 'efficacité de A * . D 'une manière générale, on cherche à définir des
heuristiques admissibles qui renvoient les plus grandes valeurs possibles tout en restant
admissibles (c'est à dire en renvoyant toujours une valeur plus petite que la valeur du plus
court chemin entre la position courante et la position finale).
Dans l' implémentation de A* , on utilise deux ensembles de noeuds : l 'ensemble 0
des ouverts et l 'ensemble F des fermés. Un noeud correspond à une position et les arcs
orientés entre les noeuds à des coups. 0 contient tous les noeuds qui n 'ont pas de fils,
autrement dit toutes les feuilles de l 'arbre. F contient tous les noeuds qui ont eu des
fils, autrement dit, tous les noeuds internes de l ' arbre. On définit pour chaque noeud une
fonction f qui est un minorant du plus court chemin passant par le noeud. On calcule f en
sommant la taille du chemin déjà parcouru nommé g et l ' heuristique admissible nommée
h. A chaque étape du développement de l' arbre de recherche, on choisit de développer,
parmi les ouverts, le noeud qui a la fonction f minimale. L' algorithme se termine quand la
position finale est atteinte. On peut voir que l ' algorithme trouve bien le plus court chemin,
puisque tous les ouverts qui restent lorsqu' on a atteint la position finale ont des chemins
de taille supérieure au chemin trouvé.
Exercice : É crire une classe pour représenter un noeud de l' arbre de recherche.
Exercice : On veut disposer d' une fonction qui insère un noeud à la bonne place
dans l 'ensemble des ouverts trié par rapport à f. Programmer la fonction void insere
(Noeud * noeud ) de façon à ce que l ' insertion et la recherche d' un noeud de plus
petit f se fasse le plus rapidement possible.