La búsqueda de caminos es un problema que usualmente se resuelve por medio de algoritmos de búsqueda en grafos como ancho-primero, profundidad-primero, Dijkstra y A*.

En este tipo de problemas conocemos un estado inicial, un estado final (meta) y un conjunto de reglas mediante las cuales podemos realizar “movidas” para ir avanzando en un grafo compuesto por nodos. Eventualmente, avanzado por el grafo, llegaremos al nodo que corresponde a la meta habiendo finalizado la búsqueda y habiendo obtenido el conjunto de movidas que nos lleva de un punto a otro.

El algoritmo A* es uno de los preferidos para este tipo de aplicaciones por ser admisible (si existe una solución la encuentra) y optimal (encuentra la solución óptima, que en nuestro caso particular es el camino mas conveniente).

Fundamentos del algoritmo A*

A* es un algoritmo informado que basa su comportamiento en la evaluación de una función expresada del siguiente modo:

f(n) = g(n) + h(n)

La función se encuentra compuesta por:

g(n) : es el costo de las movidas realizadas.
h(n) : es la función heurística. Representa el costo estimado del mejor camino. Dicha estimación debe ser realizada por defecto, es decir, siempre menor o igual a la real.

En búsqueda de caminos, la función heurística suele ser el camino recto hacia la meta, ya que no importa como sea el mapa, es imposible que exista camino de costo menor.

El modo de realizar el cálculo de la distancia necesaria para llegar a la meta depende del tipo de movidas permitidas.

Si solo podemos movernos vertical y horizontalmente podremos realizar el cálculo de la distancia Manhattan, que consiste en sumar la cantidad de bloques en horizontal y vertical que restan para llegar a la meta. Si además se permiten movidas diagonales, deberemos aplicar Pitágoras y el cálculo será la raíz cuadrada de la suma de los cuadrados de los catetos.

Analicemos un ejemplo para ver el algoritmo en acción:

S representa el punto de partida. La bandera azul representa la meta. Los casilleros de color negro representan obstáculos y los casilleros blancos representan caminos posibles.

Nuestra función heurística será:

En pocas palabras, lo que expresamos en la fórmula anterior fue la distancia que resta para llegar a la meta desde la posición en la cual nos encontramos.

¿Y cuáles serían las primeras movidas posibles?

En la figura anterior vemos a izquierda como avanzamos por el mapa y derecha como queda conformado el árbol con el valor de la función f(n) para cada una de las bases abiertas. De todas ellas seleccionaremos la de menor f, es decir, la de menor costo calculado como la suma del costo del camino recorrido y el costo estimado del camino que resta recorrer.

Para entender como realizamos el cálculo del valor de la función f(n), veamos en mayor detalle como realizamos el cálculo de la primer movida:

¡Es muy sencillo!, g siempre incrementará en uno a medida que avancemos por el mapa (ya que estamos tomando el costo de avance en forma unitaria para todas las posiciones) y h será el resultado de aplicar la fórmula de la figura 2, que es la distancia de dicha posición a la meta.

Pages: 1 2 3