Discussion :

[denebj]

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

[PRomu@ld]

Je pense que ceci peut t'aider :

http://khayyam.developpez.com/articles/algo/astar/

[FrancisSourd]

Je comprends pas ce qu'ils veulent dire par "on passe au point n´ suivant" ?:

Il veulent simplement dire "passer à l'itération suivante de la boucle", ce qui serait équivalent à un "continue" en c++.

[denebj]

Ok merci bien
J'en profite pour poser une question plus technique, c'est possible de créer une table de hachage qui stocke plusieurs données sur une ligne, par exemple avoir pour clef Toulouse et que cela me renvoi plusieurs données ?
Exemple Clef Toulouse => 100 ,Toto , 487

Je n'ai vu que des tables de hachage ou la clef ne renvoi qu'à une valeur, mais pas à une série de valeurs.

[FrancisSourd]

Non, il n'y a pas de problème pour faire cela. On peut par exemple réunir toutes les données dans une seule structure ou mettre plusieurs champ dans la structure.

Si tu as des questions plus précises là-dessus, je te conseille d'ouvrir une nouvelle discussion avec un nouveau titre (éventuellement dans un nouveau forum s'il s'agit dun problème d'implantation).

[Sivrît]

J'en profite pour poser une question plus technique, c'est possible de créer une table de hachage qui stocke plusieurs données sur une ligne, par exemple avoir pour clef Toulouse et que cela me renvoi plusieurs données ?

Une table de hachage de listes ? (ou alors effectivement une structure créée pour l'occasion pour tout réunir)

[denebj]

A oui c'est bon, j'ai crée une table de hachage contenant une structure, ça marche au poil

Résolu.

Merci à tous