Je me permets d'apporter une précision 2 ans après, pour ceux qui tomberaient sur ce topic et seraient mis dans l'erreur. A la base, tel qu'il a été conçu, A* n'est pas une méthode approchée.

Si l'heuristique est optimiste (elle ne surestime jamais la somme du poids des arcs menant aux sommets finaux) et exacte pour les arcs finaux (sur les prédécesseurs des sommets finaux, elle renvoie le poids de l'arc prédécesseur-final), alors A* est exact (optimal). Il élague la recherche d'autant plus que l'heuristique est de qualité (proche de la vérité). Bien sûr, il y a un compromis à trouver entre l'intensité de l'élagage (gain de temps) et la qualité de l'estimation de l'heuristique (qui prend du temps).

Si l'heuristique n'est pas optimiste (il lui arrive de surestimer la somme du poids des arcs menant aux sommets finaux) ou inexacte pour les arcs finaux, A* est lui-même une heuristique. C'est souvent le cas