algorithm => A * Pathfinding

Introduction à A *

A * (Une étoile) est un algorithme de recherche utilisé pour trouver un chemin d'un nœud à un autre. Donc, il peut être comparé avec Breadth First Search , ou l'algorithme de Dijkstra , ou Depth First Search , ou Best First Search. Un algorithme * est largement utilisé dans la recherche de graphes pour améliorer l'efficacité et la précision, le prétraitement de graphe n'étant pas une option.

A * est une spécialisation de Best First Search, dans laquelle la fonction d'évaluation f est définie d'une manière particulière.

f (n) = g (n) + h (n) est le coût minimum depuis le nœud initial jusqu'aux objectifs conditionnés pour aller au nœud de pensée n .

g (n) est le coût minimum entre le nœud initial et n .

h (n) est le coût minimum de n à l'objectif le plus proche de n

A * est un algorithme de recherche informé et garantit toujours de trouver le plus petit chemin (chemin avec un coût minimum) dans le temps le plus court possible (si utilise une heuristique admissible ). Il est donc à la fois complet et optimal . L'animation suivante montre A * search-

Résoudre le problème de 8 casse-tête en utilisant un algorithme A *

Définition du problème :

Un puzzle 8 est un jeu simple constitué d'une grille de 3 x 3 (contenant 9 carrés). L'un des carrés est vide. L’objet est de déplacer les carrés dans différentes positions et d’afficher les chiffres dans l’état «objectif».

Étant donné un état initial de jeu de 8 casse-tête et un état final à atteindre, trouvez le chemin le plus rentable pour atteindre l'état final à partir de l'état initial.

Etat initial :

_ 1 3
4 2 5
7 8 6

Etat final :

1 2 3
4 5 6
7 8 _

Heuristique à assumer :

Considérons la distance de Manhattan entre l'état actuel et l'état final comme heuristique pour cette déclaration de problème.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

Fonction coût total :

Donc, la fonction de coût total f(n) est donnée par,

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

Solution à l'exemple de problème :

Nous trouvons d'abord la valeur heuristique requise pour atteindre l'état final à partir de l'état initial. La fonction coût, g (n) = 0, comme nous sommes dans l'état initial

h(n) = 8

La valeur ci-dessus est obtenue, car 1 dans l'état actuel est 1 distance horizontale que le 1 dans l'état final. Même chose pour 2 , 5 , 6 . _ est à 2 distances horizontales et à 2 distances verticales. La valeur totale pour h(n) est donc 1 + 1 + 1 + 1 + 2 + 2 = 8. La fonction de coût total f(n) est égale à 8 + 0 = 8.

Maintenant, les états possibles qui peuvent être atteints d' un état initial se trouvent et il arrive que l' on peut déplacer soit _ vers la droite ou vers le bas.

Les états obtenus après avoir déplacé ces mouvements sont:

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

Encore une fois, la fonction de coût total est calculée pour ces états en utilisant la méthode décrite ci-dessus et il s’avère être respectivement 6 et 7. Nous avons choisi l'état avec un coût minimum qui est l'état (1). Les prochains mouvements possibles peuvent être Left, Right ou Down. Nous ne bougerons pas à gauche comme nous l'étions auparavant dans cet état. Donc, on peut bouger à droite ou en bas.

Encore une fois, nous trouvons les états obtenus à partir de (1).

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3) conduit à une fonction de coût égale à 6 et (4) à 4. En outre, on considérera (2) obtenu avant, dont la fonction de coût est égale à 7. En choisissant minimum, on obtient (4). Les prochains mouvements possibles peuvent être Left, Right ou Down. Nous obtenons des états:

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

Nous obtenons des coûts égaux à 5, 2 et 4 pour (5), (6) et (7) respectivement. Nous avons également les états précédents (3) et (2) avec 6 et 7 respectivement. Nous avons choisi l'état de coût minimum qui est (6). Les prochains mouvements possibles sont Up, et Down et clairement Down nous mèneront à l'état final conduisant à une valeur de fonction heuristique égale à 0.

A * Pathfinding à travers un labyrinthe sans obstacles

Disons que nous avons la grille 4 par 4 suivante:

Supposons que ce soit un labyrinthe . Il n'y a pas de murs / obstacles, cependant. Nous avons seulement un point de départ (le carré vert) et un point final (le carré rouge). Supposons également que pour passer du vert au rouge, nous ne pouvons pas nous déplacer en diagonale. Donc, en partant du carré vert, voyons les carrés vers lesquels nous pouvons aller et les surlignons en bleu:

Pour choisir la case à déplacer, nous devons prendre en compte 2 heuristiques:

La valeur "g" - C'est à quelle distance ce noeud est du carré vert.
La valeur "h" - C'est à quelle distance ce noeud est du carré rouge.
La valeur "f" - C'est la somme de la valeur "g" et de la valeur "h". C'est le nombre final qui nous indique à quel nœud se déplacer.

Pour calculer ces heuristiques, voici la formule que nous allons utiliser: distance = abs(from.x - to.x) + abs(from.y - to.y)

C'est ce qu'on appelle la formule "Manhattan Distance" .

Calculons la valeur "g" pour le carré bleu immédiatement à gauche du carré vert: abs(3 - 2) + abs(2 - 2) = 1

Génial! Nous avons la valeur: 1. Maintenant, essayons de calculer la valeur "h": abs(2 - 0) + abs(2 - 0) = 4

Parfait. Maintenant, obtenons la valeur "f": 1 + 4 = 5

Ainsi, la valeur finale pour ce noeud est "5".

Faisons la même chose pour tous les autres carrés bleus. Le grand nombre au centre de chaque carré est la valeur "f", tandis que le nombre en haut à gauche est la valeur "g" et le nombre en haut à droite est la valeur "h":

Nous avons calculé les valeurs g, h et f pour tous les nœuds bleus. Maintenant, que choisissons-nous?

Quel que soit celui qui a la valeur f la plus basse.

Cependant, dans ce cas, nous avons 2 nœuds avec la même valeur f, 5. Comment les choisissons-nous?

Simplement, vous pouvez en choisir un au hasard ou définir une priorité. Je préfère généralement avoir une priorité comme celle-ci: "Right> Up> Down> Left"

L'un des nœuds avec la valeur f de 5 nous emmène dans la direction "Down", et l'autre nous prend "Left". Puisque Down est plus prioritaire que Left, nous choisissons le carré qui nous emmène "Down".

Je marque maintenant les noeuds pour lesquels nous avons calculé les heuristiques, mais ne les a pas déplacés en orange, et le noeud que nous avons choisi comme cyan: