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