Salut à tous ^^
Je suis en train de plancher sur une implémentation de l'algo A* dans le cadre d'un problème de recherche opérationnel (Trouver le meilleur trajet entre un point A et un point B).
Je code tout ça en java.
J'ai vu ce pseudo code sur Wikipedia :
START : n%u0153ud de départ
GOAL : n%u0153ud d'arrivée
OPEN : liste des n%u0153uds à traiter (en général : représenté comme une file de priorité)
CLOSED : liste des n%u0153uds traités
N : nombre de n%u0153uds
h(i) : distance estimée d'un n%u0153ud i au n%u0153ud d'arrivée (i %u2208 {1, 2, ..., N})
g(i) : distance réelle d'un n%u0153ud i au n%u0153ud de départ (i %u2208 {1, 2, ..., N})
f(i) : somme des distances h(i) et g(i)
parent() : parent d'un n%u0153ud i (parent(x) donne la position dans parent() du n%u0153ud 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%u0153ud 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%u0153ud 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
Je comprends pas ce qu'ils veulent dire par "on passe au point n´ suivant"
Bizarrement la compréhension de l'algo en lui même ne me pose aucune difficulté mais j'ai du mal avec son implémentation
Merci de votre aide
Message édité par denebj le 15-02-2007 à 17:07:07