La Inteligencia Artificial lleva tiempo en el candelero. Todo el mundo la usa, para cualquier cosa. Pero es necesario también saber cómo funciona, al menos sus bases. Hace poco ya exploramos el Algoritmo de Dijkstra, también relacionado con la IA. Pero hay más. Uno de los algoritmos más fascinantes dentro de este mundo es el Algoritmo A*. Si alguna vez te has preguntado cómo los personajes de los videojuegos encuentran el camino más corto, o cómo los sistemas de navegación GPS calculan la mejor ruta, es probable que este algoritmo esté trabajando tras bastidores. En este artículo, vamos a sumergirnos en una explicación sencilla del Algoritmo A*, desentrañando sus misterios de una manera accesible para todos.
¿Qué es el Algoritmo A*?
El Algoritmo A* (pronunciado «A estrella») es un algoritmo de búsqueda de caminos y atravesamiento de grafos. En términos más simples, es una receta que las computadoras siguen para encontrar el mejor camino entre dos puntos. Lo que hace que el este algoritmo estrella sea especial es su eficiencia y su capacidad para encontrar el camino óptimo en la mayoría de las situaciones. Si te fijas en la imagen inferior, hay una serie de nodos (marcados como A, B, C, …). Estos nodos están conectados entre ellos por un camino. Este camino tiene un coste (marcado con un número en negrita) y para cada nodo, existe otro valor numérico (llamado heurístico) marcado con un número de color rojo. Veremos qué significan cada uno de ellos.

Los fundamentos
Para entender el algoritmo, es útil pensar en él como un explorador muy inteligente. Este explorador no solo mira el terreno que tiene delante, sino que también intenta adivinar qué tan lejos está de su destino. Utiliza esta información para tomar decisiones sobre qué dirección tomar en cada paso de su viaje.
El Algoritmo A* combina dos tipos de información:
- El costo real del camino recorrido hasta el momento (llamémosle G).
- Una estimación del costo restante hasta el objetivo (llamémosle H, de heurística).
La suma de estos dos valores (F = G + H) es lo que el algoritmo utiliza para decidir qué camino seguir. Siempre elige el camino con el valor F más bajo, ya que este representa la mejor estimación del costo total del viaje.
¿Cómo funciona el Algoritmo A*?
Vamos a desglosar el funcionamiento del Algoritmo A* en pasos sencillos:
- Inicio: El algoritmo comienza en el punto de partida y añade este punto a una lista llamada «lista abierta».
- Expansión: Mira todos los puntos adyacentes al punto actual que pueden ser atravesados.
- Cálculo: Para cada punto adyacente, calcula:
- G: El costo real del camino desde el inicio hasta este punto.
- H: Una estimación del costo desde este punto hasta el objetivo.
- F: La suma de G + H.
- Selección: Elige el punto con el valor F más bajo de la lista abierta.
- Movimiento: Se mueve a este punto, lo elimina de la lista abierta y lo añade a una «lista cerrada» de puntos ya visitados.
- Repetición: Repite los pasos 2-5 hasta que:
- Llega al punto objetivo, o
- La lista abierta está vacía (lo que significa que no hay camino posible).
- Trazado del camino: Una vez que llega al objetivo, traza el camino hacia atrás a través de los puntos visitados para encontrar la ruta completa.
La heurística
Un componente crucial en la explicación del Algoritmo A* es la heurística (H). Esta es una función que estima el costo restante hasta el objetivo. La elección de una buena función heurística es crucial para el rendimiento del algoritmo.
Una heurística común es la «distancia Manhattan», que suma las diferencias absolutas en las coordenadas x e y entre el punto actual y el objetivo. Esta funciona bien en grids donde el movimiento está restringido a las direcciones cardinales (arriba, abajo, izquierda, derecha).
Implementación del Algoritmo A* en Python
Veamos cómo se implementa el Algoritmo A* en Python. Este ejemplo utiliza una grid simple donde 0 representa espacios libres y 1 representa obstáculos.
import heapq
def heuristic(a, b):
return abs(b[0] - a[0]) + abs(b[1] - a[1])
def a_star(grid, start, goal):
neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
close_set = set()
came_from = {}
gscore = {start:0}
fscore = {start:heuristic(start, goal)}
open_set = []
heapq.heappush(open_set, (fscore[start], start))
while open_set:
current = heapq.heappop(open_set)[1]
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path
close_set.add(current)
for i, j in neighbors:
neighbor = current[0] + i, current[1] + j
tentative_g_score = gscore[current] + heuristic(current, neighbor)
if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]):
if grid[neighbor[0]][neighbor[1]] == 1:
continue
else:
continue
if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):
continue
if tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1]for i in open_set]:
came_from[neighbor] = current
gscore[neighbor] = tentative_g_score
fscore[neighbor] = gscore[neighbor] + heuristic(neighbor, goal)
heapq.heappush(open_set, (fscore[neighbor], neighbor))
return False
# Ejemplo de uso
grid = [
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (9, 9)
path = a_star(grid, start, goal)
print(path)
Este código implementa el Algoritmo A* para encontrar el camino más corto en una grid de 10×10 con algunos obstáculos. El resultado será una lista de coordenadas que representan el camino óptimo desde el inicio hasta el objetivo.
Aplicaciones prácticas del Algoritmo A*
Este algoritmo no es solo una curiosidad teórica; tiene numerosas aplicaciones prácticas en el mundo real:
- Navegación GPS: Los sistemas de navegación utilizan variantes del Algoritmo A* para calcular las rutas más eficientes.
- Videojuegos: La inteligencia artificial de los personajes en los videojuegos a menudo utiliza el Algoritmo A* para la búsqueda de caminos.
- Robótica: Los robots autónomos lo utilizan para planificar rutas y evitar obstáculos.
- Planificación de redes: En las redes de computadoras, versiones modificadas del Algoritmo A* se utilizan para determinar las rutas más eficientes para el tráfico de datos.
- Procesamiento de lenguaje natural: Algunas aplicaciones de procesamiento de lenguaje natural utilizan el Algoritmo A* para tareas como la corrección ortográfica y la traducción automática.
Ventajas y limitaciones del Algoritmo A*
Ventajas
- Eficiencia: Es más eficiente que muchos otros algoritmos de búsqueda de caminos.
- Optimalidad: Siempre encuentra el camino óptimo si existe uno.
- Flexibilidad: Puede adaptarse a diferentes tipos de problemas ajustando la función heurística.
Limitaciones
- Consumo de memoria: En problemas grandes, puede consumir mucha memoria.
- Dependencia de la heurística: Su eficiencia depende en gran medida de la calidad de la función heurística utilizada.
- Complejidad en espacios continuos: Puede ser difícil de aplicar en espacios de búsqueda continuos o muy grandes.
Conclusión
El Algoritmo A* es una herramienta poderosa en el campo de la inteligencia artificial y la ciencia de la computación. Su capacidad para encontrar caminos óptimos de manera eficiente lo hace invaluable en una amplia gama de aplicaciones.
Comprender este algoritmo no solo nos ayuda a apreciar la inteligencia detrás de muchas tecnologías que usamos a diario, sino que también nos proporciona una visión de cómo los problemas complejos pueden ser resueltos mediante enfoques inteligentes y bien diseñados.
Ya sea que estés desarrollando el próximo gran videojuego, trabajando en sistemas de navegación, o simplemente explorando el fascinante mundo de los algoritmos, ésta es sin duda una herramienta que vale la pena tener en tu arsenal de conocimientos.
Bibliografía
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Russell, S. J., & Norvig, P. (2010). Artificial intelligence: A modern approach (3rd ed.). Pearson Education.
Millington, I., & Funge, J. (2009). Artificial intelligence for games (2nd ed.). CRC Press.
LaValle, S. M. (2006). Planning algorithms. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Koenig, S., & Likhachev, M. (2005). Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics, 21(3), 354-363.
Ferguson, D., Likhachev, M., & Stentz, A. (2005). A guide to heuristic-based path planning. In Proceedings of the international workshop on planning under uncertainty for autonomous systems, international conference on automated planning and scheduling (ICAPS).
Botea, A., Müller, M., & Schaeffer, J. (2004). Near optimal hierarchical path-finding. Journal of Game Development, 1(1), 7-28.
Descubre más desde nauKabits.com
Suscríbete y recibe las últimas entradas en tu correo electrónico.