Algorithme A etoile
simo
-
hadji_ismail Messages postés 6 Statut Membre -
hadji_ismail Messages postés 6 Statut Membre -
Bonjour,
je cherche a un document de "l'algorithme A etoile" ou bien l'algorithme lui même.
Merci d'avance.
je cherche a un document de "l'algorithme A etoile" ou bien l'algorithme lui même.
Merci d'avance.
3 réponses
-
google ---> (avec le titre de ton message ou "algorithm A star" en anglais)
https://fr.wikipedia.org/wiki/Algorithme_A*
par exemple. -
-
Tant que la liste OPEN n'est pas vide
Faire
Retirer le noeud n de la liste OPEN tel que f(n) soit le plus petit
Si n est le GOAL Alors retourner la solution ;
Sinon ajouter n a CLOSED
Pour chaque successeur n' du noeud n
Heuristique H = estimation du coût de n' au GOAL
G_tmp := le coût g(n) + le coût pour aller de n à n' /* g(n')
F_tmp := G_tmp + H ; c'est l'heuristique /*f(n')
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
Fsi;
Fai t;
-------------------algo A*----------------------
Paramètres :
START : noeud de départ
GOAL : noeud d'arrivée
OPEN : liste des noeuds à traiter (en général : représenté comme une file de priorité)
CLOSED : liste des noeuds traités
N : nombre de noeuds
h(i) : distance estimée d'un noeud i au noeud d'arrivée (i ? {1, 2, ..., N})
g(i) : distance réelle d'un noeud i au noeud de départ (i ? {1, 2, ..., N})
f(i) : somme des distances h(i) et g(i)
parent() : parent d'un noeud i (parent(x) donne la position dans parent() du noeud précédant x))
Initialiser la liste OPEN à vide
Initialiser la liste CLOSED à vide
Ajouter START à la liste OPEN
-
