algorithm
A * Pathfinding

Introducción a A *

Un * (una estrella) es un algoritmo de búsqueda que se utiliza para encontrar la ruta de un nodo a otro. Por lo tanto, se puede comparar con la búsqueda en primer lugar o el algoritmo de Dijkstra , o la búsqueda en profundidad o la primera búsqueda. Un algoritmo * se usa ampliamente en la búsqueda de gráficos para ser mejor en eficiencia y precisión, donde el procesamiento previo de gráficos no es una opción.

A * es una especialización de Best First Search, en la cual la función de evaluación f se define de una manera particular.

f (n) = g (n) + h (n) es el costo mínimo desde el nodo inicial hasta los objetivos condicionados para ir al nodo de pensamiento n .

g (n) es el costo mínimo desde el nodo inicial hasta n .

h (n) es el costo mínimo de n al objetivo más cercano a n

A * es un algoritmo de búsqueda informado y siempre garantiza encontrar la ruta más pequeña (ruta con un costo mínimo) en el menor tiempo posible (si se usa heurística admisible ). Así que es tanto completa como óptima . La siguiente animación muestra A * search-

Resolviendo un problema de 8 rompecabezas usando el algoritmo A *

Definición del problema :

Un rompecabezas 8 es un juego simple que consiste en una cuadrícula de 3 x 3 (que contiene 9 cuadrados). Uno de los cuadrados está vacío. El objetivo es moverse a cuadrados alrededor en diferentes posiciones y tener los números mostrados en el "estado objetivo".

Dado un estado inicial de juego de 8 rompecabezas y un estado final a alcanzar, encuentre el camino más rentable para alcanzar el estado final desde el estado inicial.

Estado inicial :

_ 1 3
4 2 5
7 8 6

Estado final :

1 2 3
4 5 6
7 8 _

Heurística a asumir :

Consideremos la distancia de Manhattan entre el estado actual y el estado final como la heurística para esta declaración de problema.

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

Función de costo total :

Entonces, la función de costo total f(n) viene dada por,

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

Solución al problema de ejemplo :

Primero encontramos el valor heurístico requerido para alcanzar el estado final desde el estado inicial. La función de costo, g (n) = 0, ya que estamos en el estado inicial

h(n) = 8

Se obtiene el valor anterior, ya que 1 en el estado actual está a 1 distancia horizontal de distancia que 1 en el estado final. Lo mismo ocurre con 2 , 5 , 6 . _ está a 2 distancias horizontales y 2 distancias verticales. Entonces, el valor total para h(n) es 1 + 1 + 1 + 1 + 2 + 2 = 8. La función de costo total f(n) es igual a 8 + 0 = 8.

Ahora, se encuentran los posibles estados a los que se puede llegar desde el estado inicial y sucede que podemos mover _ hacia la derecha o hacia abajo.

Así que los estados obtenidos después de mover esos movimientos son:

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

Nuevamente, la función de costo total se calcula para estos estados utilizando el método descrito anteriormente y resulta ser 6 y 7 respectivamente. Elegimos el estado con el costo mínimo que es el estado (1). Los siguientes movimientos posibles pueden ser Izquierda, Derecha o Abajo. No nos moveremos a la izquierda como estábamos anteriormente en ese estado. Por lo tanto, podemos movernos hacia la derecha o hacia abajo.

Nuevamente encontramos los estados obtenidos de (1).

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

(3) lleva a una función de costo igual a 6 y (4) conduce a 4. Además, consideraremos (2) el resultado anterior que tiene una función de costo igual a 7. Elegir el mínimo de ellos conduce a (4). Los siguientes movimientos posibles pueden ser Izquierda o Derecha o Abajo. Obtenemos estados:

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)

Obtenemos costos iguales a 5, 2 y 4 para (5), (6) y (7) respectivamente. Además, tenemos estados anteriores (3) y (2) con 6 y 7 respectivamente. Elegimos el estado de costo mínimo que es (6). Los siguientes movimientos posibles son Arriba, y Abajo y claramente Abajo nos llevarán al estado final que lleva a un valor de función heurística igual a 0.

A * Recorrer un laberinto sin obstáculos.

Digamos que tenemos la siguiente cuadrícula de 4 por 4:

Supongamos que esto es un laberinto . Sin embargo, no hay paredes / obstáculos. Solo tenemos un punto de inicio (el cuadrado verde) y un punto de finalización (el cuadrado rojo). Supongamos también que para pasar de verde a rojo, no podemos movernos en diagonal. Entonces, comenzando desde el cuadrado verde, veamos a qué cuadrados podemos movernos y resáltalos en azul:

Con el fin de elegir a qué cuadrado pasar, debemos tener en cuenta 2 heurísticas:

1. El valor "g": esta es la distancia a la que se encuentra este nodo del cuadrado verde.
2. El valor "h": esta es la distancia a la que se encuentra este nodo del cuadrado rojo.
3. El valor "f" - Esta es la suma del valor "g" y el valor "h". Este es el número final que nos dice a qué nodo movernos.

Para calcular estas heurísticas, esta es la fórmula que usaremos: distance = abs(from.x - to.x) + abs(from.y - to.y)

Esto se conoce como la fórmula "Manhattan Distance" .

Calculemos el valor "g" para el cuadrado azul inmediatamente a la izquierda del cuadrado verde: abs(3 - 2) + abs(2 - 2) = 1

¡Genial! Tenemos el valor: 1. Ahora, intentemos calcular el valor "h": abs(2 - 0) + abs(2 - 0) = 4

Perfecto. Ahora, obtengamos el valor "f": 1 + 4 = 5

Entonces, el valor final para este nodo es "5".

Hagamos lo mismo para todos los otros cuadrados azules. El número grande en el centro de cada cuadrado es el valor "f", mientras que el número en la parte superior izquierda es el valor "g", y el número en la parte superior derecha es el valor "h":

Hemos calculado los valores de g, h y f para todos los nodos azules. Ahora, ¿cuál recogemos?

El que tenga el valor f más bajo.

Sin embargo, en este caso, tenemos 2 nodos con el mismo valor de f, 5. ¿Cómo seleccionamos entre ellos?

Simplemente, elija uno al azar o establezca una prioridad. Generalmente prefiero tener una prioridad como esta: "Derecha> Arriba> Abajo> Izquierda"

Uno de los nodos con el valor f de 5 nos lleva en la dirección "Abajo", y el otro nos lleva a "Izquierda". Como Down tiene una prioridad más alta que Left, elegimos el cuadrado que nos lleva "Down".

Ahora marca los nodos para los que calculamos las heurísticas, pero no nos movimos a, como naranja, y el nodo que elegimos como cian:

Bien, ahora calculemos las mismas heurísticas para los nodos alrededor del nodo cian:

Nuevamente, elegimos el nodo que baja desde el nodo cian, ya que todas las opciones tienen el mismo valor f:

Calculemos las heurísticas para el único vecino que tiene el nodo cian:

Muy bien, ya que seguiremos el mismo patrón que hemos estado siguiendo:

Una vez más, calculemos las heurísticas para el vecino del nodo:

Vayamos allí:

Finalmente, podemos ver que tenemos una casilla ganadora a nuestro lado, por lo que nos movemos allí y hemos terminado.