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

  1. #1
    Nouveau membre du Club
    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
    Points : 29
    Points
    29
    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 actif Avatar de Betatesteur
    Inscrit en
    Juillet 2003
    Messages
    210
    Détails du profil
    Informations forums :
    Inscription : Juillet 2003
    Messages : 210
    Points : 248
    Points
    248
    Par défaut
    ce pseudo code incompréhensible s'appelle algorithme. et y a que ça sur ce forum
    Le monde du DevLOpPEUR....
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    En train, il admire le scrolling du paysage..
    Il rédige ses chèques en héxadécimal..
    Sa dernière pensée avant de s'endormir est "shutdown completed"...

  3. #3
    Nouveau membre du Club
    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
    Points : 29
    Points
    29
    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 : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

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

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

  5. #5
    Membre actif 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
    Points : 203
    Points
    203
    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 actif Avatar de Betatesteur
    Inscrit en
    Juillet 2003
    Messages
    210
    Détails du profil
    Informations forums :
    Inscription : Juillet 2003
    Messages : 210
    Points : 248
    Points
    248
    Par défaut
    pas mal le lien
    Le monde du DevLOpPEUR....
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    En train, il admire le scrolling du paysage..
    Il rédige ses chèques en héxadécimal..
    Sa dernière pensée avant de s'endormir est "shutdown completed"...

  7. #7
    Nouveau membre du Club
    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
    Points : 29
    Points
    29
    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 éminent sénior
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2003
    Messages
    5 275
    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 275
    Points : 10 985
    Points
    10 985
    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 éminent 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
    Points : 7 903
    Points
    7 903
    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&#40;Y&#41; &#58; 
           begin
           DA&#40;Y&#41; = distance_ Y_ à_ A_via_X
           PR&#40;X&#41; = Y
           ProcessNode&#40;Y&#41; 
           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.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  10. #10
    Nouveau membre du Club
    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
    Points : 29
    Points
    29
    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, 15h15
  2. Réponses: 1
    Dernier message: 22/09/2009, 11h21
  3. Recherche "étoilée" avec std::set
    Par guejo dans le forum MFC
    Réponses: 2
    Dernier message: 06/05/2004, 14h28

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