ALGORITHME DE RECHERCHE
A*
RÉALISÉ PAR :
LISSIR AMANI
1
PLAN
I. Historique
II. Définition de l’algorithme de recherche
III. Définition l’algorithme A*
IV. Le concept de base de l'algorithme A*
V. Organigramme de l’algorithme A*
VI. Avantages et inconvénients de l’algorithme A*
2
Historique
En informatique, plus précisément en intelligence artificielle, l'algorithme de
recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de
recherche de chemin dans un graphe entre un nœud initial et un nœud final tous
deux donnés.
En raison de sa simplicité il est souvent présenté comme exemple typique
d'algorithme de planification, domaine de l'intelligence artificielle.
L'algorithme A* a été créé pour que la première solution trouvée soit l'une des
meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo
privilégiant la vitesse de calcul sur l'exactitude des résultats. Cet algorithme a été
proposé pour la première fois
par Peter E. Hart, Nils John Nilsson et Bertram Raphael en 1968.
Il s'agit d'une extension de l'algorithme de Dijkstra de 1959 .
3
DÉFINITION DE L’ALGORITHME DE RECHERCHE
LES ALGORITHMES DE RECHERCHE SONT DES
ALGORITHMES CONÇUS POUR RECHERCHER OU
EXTRAIRE DES ÉLÉMENTS D'UNE STRUCTURE DE
DONNÉES.
ILS SONT ESSENTIELS POUR ACCÉDER AUX ÉLÉMENTS
SOUHAITÉS DANS UNE STRUCTURE DE DONNÉES ET LES
RÉCUPÉRER EN CAS DE BESOIN.
EXEMPLE D’ALGORITHME DE RECHERCHE INCLUENT LA
RECHERCHE BINAIRE ,LA RECHERCHE LINÉAIRE,
4
RECHERCHE PAR INTERPOLATION...
Définition l’algorithme A*
5
Un algorithme A* est un algorithme C'est un algorithme pratique qui est Un algorithme A* recherche d'abord
de recherche utilisé pour trouver le souvent utilisé pour parcourir la carte les chemins les plus courts, ce qui en
chemin le plus court entre un point afin de trouver le chemin le plus fait un algorithme optimal et
initial et un point final court à emprunter complet
End End
6
Optimal complet
Trouvera le résultat le Trouve tous les
moins couteux pour un résultats possibles
problème d’un problème
7
Le concept de base de
l'algorithme A*
8
Un algorithme heuristique sacrifie l'optimalité, la précision et l'exactitude au profit de la vitesse, pour
résoudre les problèmes plus rapidement et plus efficacement.
Tous les graphes comportent différents nœuds ou points que l'algorithme doit emprunter pour atteindre le
nœud final. Les chemins entre ces nœuds ont tous une valeur numérique, qui est considérée comme le poids
du chemin. Le total de tous les chemins transversaux donne le coût de cette route.
Au départ, l'algorithme calcule le coût pour tous ses nœuds voisins immédiats, n, et choisit celui qui a le
coût le plus faible. Ce processus se répète jusqu'à ce qu'aucun nouveau nœud ne puisse être choisi et que
tous les chemins aient été parcourus. Il faut alors considérer le meilleur chemin parmi eux. Si f(n)
représente le coût final, il peut être noté comme suit :
f(n) = g(n) + h(n)
9
F(n)
Ce paramètre est utilisé pour trouver le moindre coût
d'un nœud à l'autre.
responsable de trouver le chemin optimal entre la
source et la destination.
10
G(n)
Ce paramètre représente le coût du déplacement d'un
nœud à l'autre.
Le paramètre change pour chaque mouvement d'un
nœud à l'autre.
11
H(n)
Ce paramètre est le chemin heuristique entre le nœud actuel et la destination.
Il ne s'agit pas du coût réel mais du coût supposé entre le nœud et la destination.
12
Comment fonctionne l'algorithme A* ?
alors on va comprendre comment le calcul fonctionne
Notre graphe ici qui a une source S. Destination E et
d'autres nœuds 13
On a comme donnée :
S=5
A=4
B=5
E=0
F(n) = G(n)+ H(n) Pour source
f(n) = g(n) + h(n) = 0 + 5 = 5
Le coût de l'entrée dans la source est le coût du voyage,
zéro, et le coût heuristique, qui est de 5.
14
Pour f(S-A)=1+4=5
Pour f(S-B)=2+5=7
On choisie S-A
Le coût du voyage par A est 5 et B est 7 ,
Alors Nous choisissons donc A pour l'instant
15
Pour f(S - A – E) = ( 1 + 13 ) + 0 = 14
Pour f(S - B – E)= ( 2 + 5 ) + 0 = 7
On choisie S - B - E
Le coût du voyage par SA vers E est de 14 et SB vers
E est seulement de 7.
16
Nous choisissons donc 7 comme chemin le plus court.
Le chemin final est :
S-B-E
17
Pseudocode de l'algorithme A*
Le texte ci-dessous représente le pseudocode de l'algorithme. Il peut être utilisé pour
implémenter l'algorithme dans n'importe quel langage de programmation et constitue
la logique de base de l'algorithme.
Créer une liste ouverte contenant le noeud de départ
S'il atteint le noeud de destination :
Créer une liste vide fermée
S'il n'atteint pas le nœud de destination, alors on considère un nœud avec le score f le
plus bas dans la liste ouverte.
Nous avons terminé
Sinon :
Mettre le noeud actuel dans la liste et vérifier ses voisins
Pour chaque voisin du noeud courant :
Si le voisin a une valeur g plus faible que le nœud actuel et est dans la liste fermée :
Remplacer le voisin par ce nouveau noeud comme parent du voisin. 18
Else Si (g actuel est inférieur et le voisin est dans la liste
ouverte) :
Remplacer le voisin par la valeur g la plus basse et
changer le parent du voisin par le noeud actuel.
Else Si le voisin n'est pas dans les deux listes :
Ajoutez-le à la liste ouverte et définissez sa valeur g
19
Organigramme de l’algorithme A*
20
Initialiser le nœud de départ 'n' et le
mettre dans une liste ouverte
Calculer la fonction de cout
F(n)=g(n)+h(n)
Supprimer ce nœud de la liste
ouverte et le mettre dans le fermé
liste ,Enregistrer l’index de’n’ avec
le plus petite fonction de cout ’f’
Calculez ‘f’ pour chacun Est-ce que ‘n’ est Terminez les algorithmes et
oui
de ces nœuds nœud cible? utilisez des pointeurs de nœuds
pour obtenir le chemin optimal
Non
Trouver les nœuds successifs de ‘n’
qui ne sont pas dans la liste fermée 21
Avantages et inconvénients
de l’algorithme A *
22
Avantages Inconvénients
C'est un algorithme de recherche optimal en terme Cet algorithme est complet si le facteur de
d'heuristique. branchement est fini et que chaque action a
un coût fixe.
C'est l'une des meilleures techniques de recherche
heuristique. Il est utilisé pour résoudre des problèmes de La performance de la recherche A* dépend
recherche complexes. de la précision de l'algorithme heuristique
utilisé pour calculer la fonction h(n).
Il n'y a pas d'autre algorithme optimal garanti pour
développer moins de nœuds que A*.
23
24
