Discussion :

[guillaume07]

Bonjour,
J'essaye de comprendre le fonctionnement de l'algorithme A* , mais je suis perdu avec la notion d'arbre de recherche.
cet algo est bien fait pour être utiliser dans un graphe , alors pourquoi parle t-on d'arbre de recherche ?
Merci

[khayyam90]

Bien le bonsoir,

l'algorithme A* ne nécessite pas d'arbre de recherche.
Il fonctionne sur un graphe et il a besoin de deux listes.

Ensuite, et selon les optimisations que tu souhaites apporter, tu peux utiliser des arbres de recherche à la place des listes, de même que tu peux utiliser des listes triées à la place des simples listes. Mais rien ne t'y oblige.

comprendre l'algo A*

[guillaume07]

Merci

[buzard]

L'algo A* est bien un algorithme de recheche dans un graphe. Son but est de construire un chemin d'un sommet de départ, vers un sommet d'arrivée (ou un ensemble désignés comme finaux). Il se base sur une évaluation heuristique du chemin restant à parcourir, permetant ainsi de rechercher d'abord les noeuds les plus prometteurs.

Son principe n'est guere different d'un parcours classique d'arbre. Dans le cas ou l'on considère une heuristique nulle, (aucune information pour avantager des noeuds) elle se comporte comme un parcours en largeur.

Tu trouveras sur le net, ou dans des livres. De nombreuses explications et démonstration de l'optimalité avec une heuristique admissible (qui ne surestime jamais la distance restante à parcourir). Par contre, plus l'heuristique est proche de la réalité plus vite l'algo trouvera une solution.

Le point important, c'est le choix d'une heuristique. En cela seul l'expérience et la nature du graphe, permet vraiment de décider.

[buzard]

Au sujet de l'arbre, c'est celui que dessine le parcours dans le graphe. La structure d'arbre est implicte. On y a souvent recourt, en ne conservant que les transformations d'etat et le parent du noeud sur son chemin. Alors il suffit d'effectuer ces transformations jusqu'aux parent commun, pour faire le saut d'un noeud à l'autre. (ou simplement depuis la racine)

C'est pratique lorsque l'information à chaque noeud est lourde. Un tableau même s'il n'est pas grand pris tous seul, s'il est alloué pour 1000 ou 10000 noeuds consomme vite la memoire.

[guillaume07]

si on applique A* au 'jeux du taquin' , précisement un plateau d'une taille 2*2 et en prenant comme heuristique
le nombre de case mal placé, en quoi le test présant dans A* g(e') > g(e) + h(e) avec e' successeur de e est utile?

merci

[buzard]

en quoi le test présant dans A* g(e') > g(e) + h(e) avec e' successeur de e est utile?

Je dirais qu'il n'est pas présent, enfin je vois pas où tu le case. par contre

g_nouveau(e') < g_ancien(e')

sert à savoir s'il faut modifier le chemin menant à e'.

les tests d'évaluation ne servent que dans la file de priorité des noeuds en attente (noeuds ouverts), pour savoir lequel traiter en premier. Le critère étant f(e) = g(e) + h(e)

En ce qui concerne le taquin. l'heuristique
h1(e) = nb d'éléments mal placés

est moins précise que
h2(e) = somme des déplacements nécéssaire (chaque case étant considérée seule)

[guillaume07]

oui et en cherchant sur google tu verras qu'il y a une heuristique encore plus informée, le test dont je parle se situe au même niveau que le test de la présence () ou non du noeud dans 'la file des ouverts et des fermés', c'est à dire juste avant de mettre à jour la qualité du noeud et de l'ajouter à l'ensemble des ouverts.

[buzard]

Non non, je confirme. Pas de tel test dans A*, seul les evaluations totales sont comparés, (f=g+h). Que ce soit pour mettre à jour les noeud open, ou pour choisir le meilleur.

Jamais tu ne compare les g ou les h, encore moins un g à un g+h. Du moins dans l'algo standard. Regarde l'article sur wikipedia il est plutôt bien fait.

[guillaume07]

a oui erreur de clavier, le test dont je parle c'est le suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
g(e')>g(e)+k(e,e')

où k représente le coût pour aller de e à e'

mais malgrès tout je n'en perçoit toujours pas l'intérêt dans le cas que j'ai mentioné..

[buzard]

g(e')>g(e)+k(e,e')

ok, c'est juste pour tester si le nouveau chemin (g(e)+k(e,e')) est plus court que l'ancien (g(e'))

tu peut également tester directement les f = g + h, h n'étant pas sensé dépendre du chemin (que t'as emprunté), mais seulement de l'état courant. Ce test est donc equivalent à

ancienne_evalution(e') moins bonne que nouvelle_evaluation(e')

dans l'affirmative de laquelle il faudra modifier les infos concernant le noeud dans OPEN (et l'y remettre s'il n'y etait plus).

[guillaume07]

mais dans le cas du taquin 2*2 , on s'en sert jamais de ce test , nan ?

[buzard]

Non, en effet dans un cas aussi simple il ne servira pas. Car tu est sûre d'explorer un noeud d'abord par son chemin le plus court (à condition d'utiliser une heuristique admissible, c'est à dire positive et qui ne surestime pas la distance restante)

Par contre c'est presque inutile d'utiliser A*, dans ce cas aussi simple. Un parcours en largeur te donnant les même résultats, plus rapidement (pas de priorité à gérer dans la file d'attente)

[guillaume07]

oui c clair, mais ça fait quand même économiser quelques noeuds