El algoritmo A*, muy resumidamente,
es un método de planificación de rutas basado en la heurística, es decir, en
encontrar el camino más aceptable. Desde el punto de comienzo, se van evaluando
los nodos adyacentes para ver por qué camino ir hasta el punto final en base a
la distancia recorrida desde el comiendo (a la que se llama G) y la distancia que
queda hasta el final (H, de heurística) más una suma de los dos (F). En una
cuadrícula, la heurística se mide según la distancia Manhattan, es decir, se puede
mover a derecha, izquierda, arriba y abajo pero no en diagonal. Para una
información más detallada, recomiendo este video del profesor
Jorge Casillas, de la Universidad de Granada; bien explicado y fácil de seguir.
Como A* es un algoritmo
completo, siempre que haya una solución, el algoritmo la encontrará. Propuesto
en los años 60, ha sido clave para el desarrollo de la Inteligencia Artificial:
fue de hecho protagonista de la partida de ajedrez que Gary Kasparov perdió en
1997.
En cualquier caso, se me
ocurren dos tipos de problemas que el algoritmo A* no podría resolver:
- El primero consiste en
que los obstáculos que se tengan que sortear conforme el camino se va recorriendo
se vayan moviendo. Esto provocaría, primero, mucha lentitud al programa que
debería estar haciendo cálculos sin parar, y segundo, que el camino final
resuelto no sería válido cuando los obstáculos volvieran a cambiar (en el caso
de que al programa le haya dado tiempo a calcular un camino antes de que
cambiasen).
- Otro problema sería que
el espacio a recorrer por el que encontrar el camino y el punto de destino
fueran ampliándose y moviéndose respectivamente. Esto, más que volverlo un
problema irresoluble, lo que haría sería necesitar una cantidad de tiempo
infinita.
No hay comentarios:
Publicar un comentario