IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

A étoile [A star, A*]


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    36
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Décembre 2004
    Messages : 36
    Par défaut A étoile [A star, A*]
    Bonjour,

    J'aimerais implémenter l'algorithme de recherche du chemin le plus cours (A*) avec javascript. malheureusement je n'ai rien trouvé sur développez et sur Internet je ne trouve que des pseudo-code incompréhensible.

    Quelqu'un pour-t-il me donner un pseudo-code simplifier et un code source ?

    merci...

  2. #2
    Membre expérimenté Avatar de Betatesteur
    Inscrit en
    Juillet 2003
    Messages
    210
    Détails du profil
    Informations forums :
    Inscription : Juillet 2003
    Messages : 210
    Par défaut
    ce pseudo code incompréhensible s'appelle algorithme. et y a que ça sur ce forum

  3. #3
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    36
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Décembre 2004
    Messages : 36
    Par défaut
    Excuse moi mais je sais ce ke c qu'un algorithme...

    Tu l'as toi ce pseudo-code (algorithme) ?

  4. #4
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Tu veux un code source en quel langage ? JS ? Ca va être difficile

  5. #5
    Membre éclairé Avatar de Biosox
    Profil pro
    Inscrit en
    Mai 2005
    Messages
    298
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Mai 2005
    Messages : 298
    Par défaut
    j'ai pas de pseudo-code ni de code source, mais une explication très détaillée du fonctionnement de l'algo, a partir de laquelle ça ne doit pas etre très dur d'implémenter l'algo.

    (je dis ça mais j'ai jamais essayé)

    http://www.gamedev.net/reference/articles/article2003.asp

  6. #6
    Membre expérimenté Avatar de Betatesteur
    Inscrit en
    Juillet 2003
    Messages
    210
    Détails du profil
    Informations forums :
    Inscription : Juillet 2003
    Messages : 210
    Par défaut
    pas mal le lien

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    36
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Décembre 2004
    Messages : 36
    Par défaut merci
    merci pour le lien

    je l'avais dj trouvé au paravent mais le lien de traduction francaise était naze...

    je l'avais laisser de coté pour chercher une version francaise...

    merci... un peut de traduction me fera pas de mal

    ++

  8. #8
    Expert confirmé
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2003
    Messages
    5 296
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Août 2003
    Messages : 5 296
    Par défaut
    Le principe est très .. intuitif.
    Tu réalises une exploration jusqu'au chemin final.
    A chaque nouvelle étape que tu vas évaluer le coût de passer par cette étape comme étant le coût connu (somme de coûts réels d'étape à étape) pour y arriver, plus le coût estimé pour aller jusqu'à l'arrivée (une heuristique comme p.ex. une distance ||Arrivée-Etape||).
    A chaque itération, tu choisis comme point de départ l'étape de plus faible coût total estimé.
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

  9. #9
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    Bonjour,

    Le lien donne une explication bien compliquée pour un algorithme simple :

    Supposons que l'on ait un graphe qui permette de connaitre les liens de chaque noeud (noeuds contigus) et la distances correspondante.

    Pour trouver le plus court chemin d'un noeud A à un noeud B, on calculera calculera le plus court chemin du noeud A à tous les noeuds du graphe.

    On a besoin comme de définir pour chaque noeud du graphe les valeurs suivantes :
    - DA(X) : distance d'un noeud X à A (que l'on initialisera à "infinie").
    - PR(X) : prédecesseur de X sur le chemin B à A.

    ProcessNode est la procédure permettant de traiter tous les noeuds contigus d'un noeud X.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    Procedure ProcessNode(X) ;
    begin
    Pour i de 1 au nombre de noeuds contigus à X : 
       begin
       Y=noeud_contigu(X,i)
       distance_ Y_ à_ A_via_X = DA(X) + Dist(X,Y) 
       si distance_ Y_ à_ A_via_X < DA(Y) : 
           begin
           DA(Y) = distance_ Y_ à_ A_via_X
           PR(X) = Y
           ProcessNode(Y) 
           end 
       end
    end
    On fait ProcessNode(A) et, au retour, on a la distance dans DA(B) et on récupére le chemin en parcourant les prédecesseurs de B jusqu'à A.
    Evidement, Si DA(B)="infinie", il n'y a pas de chemin de A à B.

    Pour optimiser dans une application réélle, on peut modifier l'ordre de parcours des noeuds contigus en utilisant des informations "géographiques" afin de traiter la ligne droite AB en priorité. On a alors des chances de tomber assez vite sur le point B. On peut alors comparer, dans la procedure processNode, DA(X) à DA(B) et si DA(X)>DA(B) il est alors inutile de traiter le noeud X.

  10. #10
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    36
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Décembre 2004
    Messages : 36
    Par défaut
    merci... beaucoup...

    voila qqe autres liens très interressants et qui ont été difficiles à déniché...

    l'article :
    http://www.policyalmanac.org/games/aStarTutorial.htm

    le lien mort retrouvé...
    http://blog.lalex.com/archives/20030...thfinding.html

    Wikipédia:
    http://fr.wikipedia.org/wiki/Algorithme_A%2A

    Geocities:
    http://www.geocities.com/jheyesjones/astar.html

    voila....

    je n'ai pas encore tout compris le system... mais j travail...

    merci encore pour votre aide

Discussions similaires

  1. composant rating note étoiles stars
    Par ouiouioui dans le forum Composants VCL
    Réponses: 0
    Dernier message: 14/03/2012, 14h15
  2. Réponses: 1
    Dernier message: 22/09/2009, 10h21
  3. Recherche "étoilée" avec std::set
    Par guejo dans le forum MFC
    Réponses: 2
    Dernier message: 06/05/2004, 13h28

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo