Souvent pour calculer les déplacements à travers un monde compèxe,vous devez concevoir des algorithmes de déplacement a* fait partie de ceux-là.

Algorithme A*

Introduction

Lorsque l'on veut faire passer un systeme d'un etat a un autre, il peut y avoir la necessite de cout minimum. Ainsi si l'on veut deplacer un pion dans un labyrinthe en le faisant parcourir le moins de distance possible ou resoudre un probleme tel que le jeu du taquin avec le moins de mouvement possible il faut trouver un algorithme capable de trouver la meilleur solution ou de dire si il n'en existe aucune.
L'on peut soit utilise une methode exhaustive pour trouver un moyen d'y parvenir mais cela entraine des temps de calcul astronomique.
L'on peut aussi prendre la premiere solution trouve mais cette solution n'est vraiment pas optimale.

Definitions

Pour un algorithme de recherche il peut y avoir plusieurs strategie d'organisation :
Developpement d'etat :
a completement developpe :
tout les etats sont engendrés, toutes les alternatives sont considerees;
b partielement developpe :
generalement on developpe un successeur et on note pour un retour eventuelle que cette etape n'a pas entirement ete developpe.

Organisations des alternatives :
1)LIFO
2)FIFO
3)Ordonnée

A* est un algorithme a developement complets avec une recherche ordonnée par l'évaluation f.
Il a pour but de determiner un sequence d'etats succesif tels que la somme des couts pour passer d'un etats a l'autre soit minimum.
Cela revient a la recherche d'un chemin de cout minimal dans un graphe oriente G=(U, S)
- U est l'espace de representation fini ou infini
- T C U est l'ensemble des etats terminaux
- S est la relation successeur.

Cette relation traduit un ensemble de regles :
v E S(u) : G comporte un arc de u à v de cout k(u, v) si et seulement si il existe une regle transformant l'etat u en v.
k*(u, v) : minimum du cout des chemins de u a v si il existe un chemin entre ces 2 etats; sinon on prend par convention k*(u, v) = infinity

On definit egalement trois applications de U dans R+ :
- g*(u)=k*(u0, u) : minimunm du cout des chemins de u0 a u;
- h*(u)=min{k*(u, v)|v E T) : minimum du couts des chemins de u a un etat terminal quelconque;
- f*(u)=g*(u)+h*(u) : minimum du couts des chemins passant par u et menant de U0 a un etat terminal.

Sauf dans les cas triviaux, aucune des trois applications f*, g* ou h* n'est connu a priori. Ou utilise donc une information heuristique h(u) qui est une approximation de h*(u).
La qualite de cet estimateur heuristique h est mesure par l'ecart h(u)-h*(u), et apprecie sur la base d'une ou de plusieurs proprietes.

L'algorithme A*

A* partitionne U en deux sous-ensembles :
P : ensemble des etats pendants ( ou ouvert ), ce sont les etats succeptibles d'etre developpe ou redeveloppe.
Q : ensemble des etats deja developpe ou que l'on ne peut pas developpe.

L'algorithme devra choisir l'etat suivant a developpe dans P.
Cet ensemble est totalement ordonne :
----par ordre de valeur croissante de f
---------par valeur decroissante de g
avec priorite aux etats terminaux.

û designera le premier etat pendant (tete de pile).
pere(u) est un pointeur vers l'etat dont u est succeseur.
chemin(u)=(u0, ..., pere(prer(u), pere(u), u).

Algorithme en pseudo code :
Donnees d'entree : graphe G : 5u,S) defini implicitement par U0 et S ; relation de cout k sur les arcs de G; application h de U dans R+

1. Initialisation : P <- {u0}; Q<-0; g(u0)<-0; u<-u0
2. Iterer tantque [P <>0 et û Ë T ]
2.1. Supprimer u de P et le mettre dans Q
2.2. Iterer sur {v E S(u) }
2.2.1. Si [ (v Ë P U Q) ou ( g(v) > g(u)+k(u,v)] alors faire :
--------g(v)<-g(u)+k(u,v)
--------f(v)<-g(v)+h(v)
--------pere(v)<-u
--------Ranger v dans P, dans l'ordre f croissant puis g decroissant.
----Fin iteration 2.2
2.3 Si[P <>0] alors u<-û etat en tete de la pile P
3. Fin Iteration 2

Donnees de sortie : Si (P=0) alors le probleme n'admet pas de solution ;
------------------------Sinon fournir la solution chemin(u)

Terminaison d'a*

Celle-ci est établie pour pratiquement toute fonction d'éstimation heuristique, et pour tout graphe d'états G à coûts positifs ou nuls dans un graphe finis.

proposition

Pour toute h, application de U dans R+ et pour tout G graphe fini à valuations positives ou nulles, A* s'arrête, soit sur un état terminal, soit faute d'état pendant (P=0) s'il n'existe pas de chemin de U0 à un état terminal.

Si G et h vérifient les hypotheses suivantes :

g est un graphe fini ou infini à valuations positives ou nulles dans lequel il existe au moins un chemin de longueur finie entre u0 et un état terminal;

h est une application de U dans R+ telle qu'il existe un majorant n avexh(ui) pour tout état ui sur un chemin optimal (u0...ui...ur) de u0 à un état terminal ur E T; alors A*s'arrête aprés un nombre fini d'étapes et fournit un chemin de u0 à T.

Admissibilité d'A*

proposition

On reprend la même hypothese que pour la proposition precedente.
Par contre, l'admissibilité ne sera établie que pour des heuristiques minorantes.
si h est minorante, alors à la fin de chacune des itérations d'A*, l'état û en tête de la pile P vérifie f(û)<=f*(u)

Compléxité d'A*

La complexite d'un algorithme est fonction de N, nombre d'états du graphe G.
Il dépend, dans le cas de A* principalement de la fonction heuristique h

- dans le pire des cas A*effectue 2^N dévelopements d'états

- si l'heuriostique est minorante la complexite est ramene à N²

-si h est monotone A* effectue au plus N dévelopements.