Notre solution se trouve dans un arbre qui peut être gigantesque. Examinez ce qu'il donne pour une grille de seulement 6 cases. On note g le coût d'une étape (en fait, ici, c'est simplement le nombre de détecteurs présents) et h l'heuristique de l'étape. On note aussi f la somme des deux. Cela représente l'estimation du coût de la solution finale qui passerait par cette étape.
Si on veut être sûr de trouver la meilleurs solution, on ne peut pas se permettre de prendre la première qui vient sinon on trouvera qu'on doit utiliser 4 détecteur alors que 2 suffisent. On va donc utiliser l'algorithme de recherce A* qui consiste à prendre le chemin qui semble le plus court. Dans cet exemple, on commence par lister toutes le états à un détecteur et on les trie par la valeur de leur f croissante :
On retire le premier de la liste et on recherche ses fils que l'on insère (en les triant) dans la liste.
On continue le même processus tant que la liste n'est pas vide.
Et voilà le travail ! Notre solution est sortie après analyse de 14 étapes. C'est mieux que de regarder chacun des 63 noeuds de l'arbre précédent. Voilà donc toute la puissance de l'algorithme de recherche A*. Voyons maintenant son implémentation dans la pratique.