154
D
g= I
h=3
[=4
g=2
g=2
h=2
h=4
[=4
f=6
Recherche de plus court chemin sur une carte
i--- -- -- --1
g=O
1--- -- --1 h=2
f=2
t--+- -+- -+- -<
g=I
h=3
[=4
g=I
h=3
[=4
FIGURE 8.7 - On développe une feuille de f minimal.
une position déjà visitée avec un plus petit g et le déplacement vers la droite amène à un
obstacle. Encore une fois la nouvelle feuille a un f = 4 qui est minimal.
D
g=2
h=2
[=4
g=3
1--- -- --1 h=I
>---+- --+- -+- -- -< [=4
g= I
h=3
[=4
g=2
h=4
f=6
g=O
h=2
1---t- -+- -+- -l f=2
g=I
h=3
[=4
g=I
h=3
[=4
FIGURE 8.8 - On développe la feuille ayant le plus petit f en évitant les positions déjà
visitées.
On développe alors de nouveau la feuille la plus à gauche avec un f minimal et on
arrive au but comme indiqué en figure 8.9.