4. Recherche A*

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.
g=1, h=1 -> 2 g=1, h=1 -> 2 g=1, h=1 -> 2 g=1, h=2 -> 3 g=1, h=2 -> 3 g=1, h=2 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 g=2, h=1 -> 3 Solution en 2 Solution en 2 g=2, h=1 -> 3 g=2, h=2 -> 4 g=2, h=1 -> 3 g=2, h=1 -> 3 g=3, h=1 -> 4 g=3, h=1 -> 4 g=3, h=1 -> 4 g=3, h=1 -> 4 Solution en 3 Solution en 3 g=3, h=1 -> 4 g=3, h=1 -> 4 Solution en 3 Solution en 3 Solution en 3 Solution en 3 g=3, h=1 -> 4 g=3, h=1 -> 4 Solution en 3 Solution en 3 Solution en 3 Solution en 3 Solution en 3 g=3, h=1 -> 4 Solution en 4 Solution en 4 g=4, h=1 -> 5 g=4, h=1 -> 5 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 4 Solution en 5 Solution en 5 Solution en 5 Solution en 5 Solution en 5 Solution en 5 Solution en 6
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 :
f = 1 + 1 = 2 f = 1 + 1 = 2 f = 1 + 1 = 2 f = 1 + 2 = 3 f = 1 + 2 = 3 f = 1 + 2 = 3
On retire le premier de la liste et on recherche ses fils que l'on insère (en les triant) dans la liste.
f = 1 + 1 = 2 f = 1 + 1 = 2 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 1 + 2 = 3 f = 1 + 2 = 3 f = 1 + 2 = 3
On continue le même processus tant que la liste n'est pas vide.
f = 2 + 0 = 2 f = 2 + 0 = 2 f = 1 + 1 = 2 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 2 + 1 = 3 f = 1 + 2 = 3 f = 1 + 2 = 3 f = 1 + 2 = 3
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.
Pages : 1 2 3 4 5 6 7
Detecteur de présence
15 mai 2013
Sommaire général