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 :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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

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