1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
START : nœud de départ
GOAL : nœud d'arrivée
OPEN : liste des nœuds à traiter (en général : représenté comme une file de priorité)
CLOSED : liste des nœuds traités
N : nombre de nœuds
h(i) : distance estimée d'un nœud i au nœud d'arrivée (i ? {1, 2, ..., N})
g(i) : distance réelle d'un nœud i au nœud de départ (i ? {1, 2, ..., N})
f(i) : somme des distances h(i) et g(i)
parent() : parent d'un nœud i (parent(x) donne la position dans parent() du nœud précédant x))
* Initialiser la liste OPEN à vide
* Initialiser la liste CLOSED à vide
* Ajouter START à la liste OPEN
* Tant que la liste OPEN n'est pas vide
* Retirer le nœud n de la liste OPEN tel que f(n) soit le plus petit
* Si n est le GOAL retourner la solution ;
* Sinon ajouter n a CLOSED
* Pour chaque successeur n´ du nœud n
* Heuristique H = estimation du coût de n´ au GOAL
* Stocker dans G_tmp g(n´), le coût g(n) + le coût pour aller de n à n´
* Stocker dans F_tmp f(n´), g(n´) + H ; c'est l'heuristique
* Si n´ se trouve déjà dans OPEN avec un f(n´) meilleur on passe au point n´ suivant
* Si n´ se trouve déjà dans CLOSED avec un f(n´) meilleur on passe au point n´ suivant
* Mettre n dans parent(n')
* Mettre G_tmp dans g(n')
* Mettre F_tmp dans f(n´)
* Retirer n´ des deux listes OPEN et CLOSED
* Ajouter n´ à la liste OPEN |
