Fonctionnalités de l'algorithme A*

• L'algorithme A* est un algorithme de recherche de chemin extrême.
• A* est utilisé sur des graphes pondérés¹
• Nous pouvons utiliser l'algorithme A* (se prononce A Star) sur des graphes aux pondérations quelconques, et des graphes avec circuits ou sans circuits.
• L'efficacité de A* repose sur la définition de bornes (par exemple des distances à vol d'oiseau).
• L'algorithme A* est plus rapide que Ford-Bellman et Moore-Dijkstra, si le choix heuristique² des bornes est judicieux (dans ce cas, la première solution trouvée est une des meilleures solutions possibles).

Contents Haut

Caractéristiques de l'algorithme A*

Nous parlons d'algorithme heuristique² A* car l'égalité triangulaire entre les bornes n'est pas toujours vérifiée. Si certaines bornes ne respectent pas cette égalité triangulaire, A* donne un chemin qui n'est pas optimum.

Dans certains cas, l'algorithme A* peut toutefois se révéler plus lent à trouver le chemin, même si le choix heuristique est correct. Ces cas se présentent lorsque le chemin à emprunter doit d'abord "s'éloigner" de la destination, par exemple dans le cas d'un labyrinthe dans lequel le chemin qui part dans la direction de la destination est une "voie sans issue".

L'exemple du labyrinthe montre bien que le choix de l'algorithme en fonction de la situation est très important.

Contents Haut

Code de l'algorithme A*

Nous pouvons décomposer notre algorithme en deux phases : une phase d'initialisation des valeurs, et une phase d'exécution qui décrit ce qui se passe lorsque l'algorithme est exécuté.

Les explications suivantes sont identiques à celles que nous avons vu lors de l'algorithme de Moore-Dijkstra. La seule différence est que nous travaillons ici avec une fonction heuristique qui retourne la borne associée aux deux sommets évalués pour un arc.

//Il reste des sommets non traités
tant_que k < n faire
 
	/*i est l'indice de x, j est l'indice de y
	x est non traité, et le chemin(r,x) est le plus court
	de tous les chemins de r vers un sommet non traité */
	i := choisir x ∈ {y |&thinsp;(y ∈ X\definedVertices) ∧
		(pathMinWeights[i]=minimum{
			(pathMinWeights[j]+heuristic(i,j))∀j∈ X\definedVertices
			})};
 
	//k pointe à présent sur le prochain emplacement libre de definedVertices
	k := k+1;
 
	//i est défini comme étant traité
	definedVertices[k] := i;
 
	//vérifier si ce chemin est le meilleur
	pour_tout y ∈ X\definedVertices faire
 
		/*si x est un précédent de y sur un chemin
		plus court que le meilleur chemin actuel...*/
		si pathMinWeights[i]+weight(i,j) < pathMinWeights[j] alors
 
			//le poids du chemin vers "y" est mis à jour
			pathMinWeights[j] := pathMinWeights[i]+weight(i,j);
 
			//j est l'indice du sommet précédent de "x"
			verticesLabels[i] := j;
 
		fin si
	fin pour_tout
fin tant_que

A* vs Moore-Dijkstra

Le fait d'inclure notre fonction heuristique (ligne 9) dans le choix du sommet nous permet de prendre en compte une borne qui limitera les recherches en direction de la destination si les bornes sont judicieusement établies. L'amélioration est remarquable en pratique, bien que la complexité théorique reste identique.