[Résolu]A Star ou A *

A Star ou A * [Résolu] - Algo - Programmation

Marsh Posté le 13-02-2007 à 04:02:51    

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
Reply

Marsh Posté le 13-02-2007 à 04:02:51   

Reply

Marsh Posté le 13-02-2007 à 08:29:27    


Algorithme A-étoile
 
Début
  ouverts = { état initial }
  fermés  = vide
  succès  = faux
  Tant que (ouverts non vide) et (non succès) faire
    choisir n dans les ouverts tel que f(n) est minimum
    Si est_final(n) Alors succès=vrai
    Sinon ouverts = ouverts privé de n
          fermés  = fermés + n
          Pour chaque successeurs s de n faire  
            Si (s n'est ni dans ouverts ni dans fermés)
            Alors
              ouverts = ouverts + s
              père(s) = n
              g(s) = g(n) + coût(n,s)
            Sinon
              Si (g(s) > g(n) + coût(n,s)) Alors
                père(s) = n
                g(s) = g(n) + coût(n,s)
                Si (s se trouve dans fermés) Alors
                  fermés  = fermés  - s
                  ouverts = ouverts + s
                Fin si
              Fin si
            Fin si
          Fin pour
    Fin si
  Fin TQ
Fin  

Reply

Marsh Posté le 13-02-2007 à 16:34:02    

J'avais vu cet algo dans ton topic du taquin :)
Par contre ils ne font jamais l'opération f(n) = g(n) + h(n) :??:


Message édité par denebj le 13-02-2007 à 17:10:59
Reply

Marsh Posté le 14-02-2007 à 09:34:09    

Il y a souvent une différence certaine entre l'algo théorique et son implémentation.
Moi par exemple, je suis sur les cross-over, et entre ce que je trouve théoriquement et l'implémentation, sa diffère pas mal, car tu peux gagner des étapes en faisant certaine boucle qu'il ne font pas pour expliquer théoriquement l'algo.
J'avoue que je n'ai aps regarder le code de A*, mais pense à ça et tiens nous au courant ;)
Bon amusement

Reply

Marsh Posté le 15-02-2007 à 01:04:24    

Oué c'est bon, tout marche c'est cool :)

Reply

Marsh Posté le 15-02-2007 à 09:33:36    

Dans ce cas la, met [RESOLU] devant le sujet de ton post ;)
voilà, bon continuation :)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed