8.3 L'heuristique triangulaire
D
g=2
h=2
f=4
g=3
1--__ ___, h=I
1--f- -- - g=I
h=3
f=4
g=2
h=4
f=6
g=O
1--- -� h=2
1--f- -- - g=I
h=3
f=4
155
g=I
h=3
f:4
FIGURE 8.9 - On arrive au but et toutes les autres feuilles ont des f plus grands ou égaux.
L' algorithme 7 décrit la recherche de plus court chemin sur une carte avec A* .
Exercice : Montrer que lalgorithme A* est une généralisation de lalgorithme de
Dijkstra.
Exercice : É crire un programme qui trouve un plus court chemin sur une carte en
utilisant l ' algorithme A*. On utilisera l 'heuristique de Manhattan pour estimer de façon
optimiste la longueur du chemin restant à parcourir. On utilisera des structures de données
efficaces de façon à obtenir une complexité linéaire en fonction de la taille de la carte.
Exercice : Trouver une heuristique admissible lorsque les déplacements diagonaux
sont autorisés.
8.3 L'heuristique triangulaire
ALT est une bonne heuristique pour les cartes routières [40] . Elle consiste à pré calculer les distances d' un point donné à tous les autres points. Ces distances pré calculées