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.