Algorithme de recherche A*:
L'algorithme A* est un algorithme de recherche informé utilisé pour
trouver le chemin optimal entre un nœud de départ et un nœud
d'arrivée dans un graphe. C’est une extension de l’algorithme Dijkstra
(ajout d’une heuristique) .
L’algorithme utilise une fonction f d’évaluation pour chaque nœud:
f(n)=h(n)+g(n) où g(n) représente le coût exact pour atteindre le nœud n
depuis le point de départ et h(n) est une estimation heuristique du coût
restant pour atteindre le nœud objectif. Le but de l'algorithme est de
minimiser f(n) tout en explorant les nœuds, afin de trouver le chemin le
plus court.
open-list:liste des nœuds à explorer
closed-list:liste des nœuds traités
n.g: cout depuis le nœud initial jusqu’à nœud n
n.h: valeur de fct heuristique du nœud n
n.f=n.h+n.g
l’algorithme A*:
Exemple d’exécution manuelle:
open-list: closed-list:
1/(n0, 9, void) 1/vide
2/(n1, 5, n0), (n2, 6, n0), 2/(n0, 9, void)
(n3, 7, n0) 3/(n0, 9, void), (n1, 5, n0)
3/(n2, 6, n0), (n3, 7, n0), 4/(n0, 9, void), (n1, 5, n0),
(n5, 12, n1) (n2, 6, n0)
4/(n3, 7, n0), (n4, 9, n2), 5/(n0, 9, void), (n1, 5, n0),
(n5, 12, n1) (n2, 6, n0), (n3, 7, n0)
5/(n2, 5, n3), (n4, 6, n3), 6/(n0, 9, void), (n1, 5, n0),
(n5, 12, n1) (n2, 6, n0), (n3, 7, n0),
6/(n4, 6, n3), (n5, 12, n1)
(n4, 6, n3)
7/(n6, 7, n4), (n5, 12, n1)
7/(n0, 9, void), (n1, 5, n0),
8/Solution : n0, n3, n4, n6
(n2, 6, n0), (n3, 7, n0),
(n4, 6, n3), (n6, 7, n4)
Code python:
def a_star(start, goal, graph, heuristics):
open_list = []
closed_list = []
g_cost = {start: 0}
open_list.append((start, heuristics[start], None))
while open_list:
current_node = min(open_list, key=lambda x: x[1])
open_list.remove(current_node)
node_name = current_node[0]
parent = current_node[2]
if node_name == goal:
path = []
while parent is not None:
path.append(node_name)
node_name = parent
parent = g_cost.get(node_name, None)
path.append(start)
return path[::-1]
closed_list.append(node_name)
for neighbor, cost in graph[node_name]:
if neighbor in closed_list:
continue
tentative_g = g_cost[node_name] + cost
if neighbor not in g_cost or tentative_g < g_cost[neighbor]:
g_cost[neighbor] = tentative_g
f_neighbor = tentative_g + heuristics[neighbor]
open_list.append((neighbor, f_neighbor, node_name))
return None
Critères de Performance de l'Algorithme A*:
Pour évaluer les performances de l'algorithme A*, nous examinons les complexités
en temps et en espace ainsi que l'optimalité de la solution trouvée. L'algorithme A*
se base sur le calcul des coûts exacts et estimés (g(n) et h(n)) pour choisir le
meilleur chemin, ce qui impacte son efficacité.
Illustration Pratique:
Pour montrer comment la complexité en temps et en espace évolue, voici un exemple
illustratif :
Supposons un arbre de recherche où chaque nœud a 3 successeurs (b = 3) et la solution
est à une profondeur de 5 (d = 5). La complexité théorique serait :
Temps :
O(35)=O(243)O(3^5) = O(243)O(35)=O(243)
Espace :
O(35)=O(243)O(3^5) = O(243)O(35)=O(243)
Si l'heuristique choisie est parfaite, A* ne génère que les nœuds sur le chemin optimal.
Par conséquent, il ne générerait que 5 nœuds (d), réduisant la complexité temporelle et
spatiale à :
O(5)=O(d)O(5) = O(d)O(5)=O(d)
Ainsi, la performance de A* dépend directement de la qualité de l'heuristique choisie.
