Discussion :

[Kazvert]

Bonjour,

Dans le tuto sur A* (https://khayyam.developpez.com/articles/algo/astar/), les étapes sont décrites ainsi :
"""

1 On commence par le noeud de départ, c'est le noeud courant
2 On regarde tous ses noeuds voisins
3 si un noeud voisin est un obstacle, on l'oublie
4 si un noeud voisin est déjà dans la liste fermée, on l'oublie
5 si un noeud voisin est déjà dans la liste ouverte, on met à jour la liste ouverte si le noeud dans la liste ouverte a une moins bonne qualité (et on n'oublie pas de mettre à jour son parent)
6 sinon, on ajoute le noeud voisin dans la liste ouverte avec comme parent le noeud courant
7 On cherche le meilleur noeud de toute la liste ouverte. Si la liste ouverte est vide, il n'y a pas de solution, fin de l'algorithme
8 On le met dans la liste fermée et on le retire de la liste ouverte
9 On réitère avec ce noeud comme noeud courant jusqu'à ce que le noeud courant soit le noeud de destination.
"""

je ne comprends pas dans quel cas on peut avoir l'étape 5 ou le cout serait plus faible que le cout déjà renseigné dans la liste ouverte. Pour moi, le cout n'a pas de raison de changer. Est il possible d'avoir un exemple ?

Un power point fait par qqn du CNRS va dans le meme sens mais les 2 exemples ne montrent pas ce cas (les couts sont toujours les mêmes) :
https://www.google.com/url?sa=t&rct=...Pw8jwlDCVk5I_W

Merci

Cordialement

[Gruzo]

Salut,

J'ai regroupé un petit ensemble de documents que je pense qui vont t'être utile.

[Flodelarab]

Bonjour

@Kazvert : En résumé, on a cru qu'un chemin était le meilleur, alors qu'il y avait mieux.

@Gruzo : Ton exemple ne fonctionne pas.
L'heuristique doit être admissible. C'est-à-dire qu'elle ne doit pas surpasser le coût réel.
Or, le point C n'est jamais évalué à cause de l'heuristique trop forte.
Les points étudiés sont :
A 4.2
C 4.8
B 4.5 ( < C 4.8)
D 5.6
E 4.6 ( < C 4.8)
G 4.4
Et le parcours final est ABEG, ce qui est faux.
À cause de l'heuristique trop forte qui disqualifie C.
E n'a aucune raison d'être réévalué.

[Kazvert]

Merci pour vos retours, je regarde tout ca.

En fait, mon heuristique est seulement basée sur la distance entre la case considérée et la destination et toutes les cases ont la même valeur.
Dans ce cas, j'ai l'impression que le cout total ne pourra pas changer pour une même case. Par contre cela ne serait probablement pas le cas si certaines cases avaient des malus en plus de la distance
C'est correcte ?

[Flodelarab]

toutes les cases ont la même valeur.

Euh ... on se moque de la valeur de la case.
Il y a le chemin parcouru et le chemin qui reste à parcourir.

Dans ce cas, j'ai l'impression que le cout total ne pourra pas changer pour une même case.

Tu reviens à ta question initiale.

Il est possible que tu aies fait entrer dans ta liste ouverte une case évaluée comme très mauvaise (donc pas traitée en priorité).
Puis un chemin (qui, lui, a eu l'honneur d'être traité) vient au voisinage de la-dite case.
Ce chemin apporte un coût moindre.
Et la case de la liste ouverte doit être modifiée vers un coût moindre.

Imagine 2 couloirs qui arrivent à un goulot d'étranglement.
Le chemin préféré sera systématiquement celui plus proche de la sortie.
Pourtant, le chemin le plus rapide est celui qui commence par s'éloigner de la sortie.
Donc le premier chemin arrivera au goulot d'étranglement.
Et le second chemin mettra à jour le goulot d'étranglement avec un coût moindre.
Pourtant, le goulot n'est pas plus prêt ou loin qu'avant.

Est-ce plus clair ?

[Kazvert]

Oui plus clair, merci

et je me suis aperçu que je ne tenais pas compte du chemin pris pour arriver à la case concernée mais que je calculais la distance Manhattan entre la source et la case concernée