8.2 L'algorithme A*
153
Algorithm 6 Recherche du plus court chemin sur une carte avec l ' algorithme de Dijkstra
dijkstra (depart, arrivee)
for tous les points de la carte do
g [point] f- -1
end fo r
positions à développer f- 0
point f- depart
g [point] f- 0
while point =/:- arrivee do
for tous les voisins de point do
if le voisin est accessible then
if g [voisin] = -1 then
g [voisin] f- g[point] + 1
aj outer voisin dans les positions à développer
end if
end if
end for
retirer le point qui a le plus petit g des positions à développer
end while
retourner g [arrivee]
g=I
h=3
f=4
g=O
h=2
f=2
g=I
h=3
f=4
g=I
h=3
f=4
FIGURE 8.6 - On insère dans les positions à développer tous les fils de la position de
départ.
Si on prend le même exemple que pour l ' algorithme de Dijkstra, on commence par
développer la position initiale comme décrit dans la figure 8.6. On calcule pour chaque
nouvelle feuille les valeurs pour g, h et f.
On choisit ensuite une feuille ayant un f minimal et on la développe comme dans la
figure 8.7. On voit qu' une des feuilles développées à un f = 4 ce qui correspond au f
minimal sur toutes les feuilles.
On développe alors la feuille de f minimal la plus à gauche et on obtient l ' arbre de la
figure 8.8. On ne développe qu' une seule feuille car le déplacement vers le bas amène à