Algoritmo de búsqueda A* para niños
La heurística de búsqueda A* (se pronuncia "A asterisco" o "A star") es un tipo de algoritmos de búsqueda en grafos muy inteligente. Fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael. El algoritmo A* ayuda a encontrar el camino más corto o de menor costo entre un punto de inicio y un punto final, siempre que se cumplan ciertas condiciones.
Contenido
¿Por qué es útil el algoritmo A*?
Algunos algoritmos de búsqueda más simples, como el "algoritmo voraz", solo se fijan en la estimación más cercana para avanzar, lo que a veces no lleva al mejor camino. Otros, como los "algoritmos de escalada", solo consideran el costo real de moverse de un lugar a otro, y a veces hay que dar un paso más "caro" para llegar a la solución.
El algoritmo A* es especial porque combina lo mejor de ambos mundos. Tiene en cuenta dos cosas importantes:
- El costo real del camino que ya se ha recorrido para llegar a un punto (llamado g(n)).
- Una estimación de lo que costará llegar desde ese punto hasta el destino final (llamado h'(n)).
Así, A* usa una fórmula para decidir qué camino es el mejor: f(n) = g(n) + h'(n). Esto le permite cambiar de camino si encuentra uno que parece más prometedor, combinando la búsqueda de "primero en anchura" (que explora todos los caminos cercanos) con la de "primero en profundidad" (que intenta llegar rápido al final).
¿Cómo funciona el algoritmo A*?
El algoritmo A* usa dos listas para organizar la información:
- Abiertos: Aquí se guardan los puntos que aún no se han explorado, pero que podrían ser parte del mejor camino. Están ordenados por el valor de f(n), es decir, los que parecen más prometedores van primero.
- Cerrados: Aquí se guardan los puntos que ya se han visitado y analizado.
En cada paso, A* elige el punto de la lista "Abiertos" que tiene el valor f(n) más bajo (el más prometedor). Si ese punto no es el destino final, el algoritmo calcula el valor f(n) para todos los puntos a los que se puede llegar desde él. Luego, los añade a la lista "Abiertos" y mueve el punto original a la lista "Cerrados". Este proceso se repite hasta que se encuentra el destino.
Características importantes de A*
¿Siempre encuentra una solución?
Sí, el algoritmo A* es "completo". Esto significa que si existe un camino entre el punto de inicio y el destino, A* siempre lo encontrará.
¿Es el camino encontrado el mejor?
Para que A* garantice que el camino encontrado es el de menor costo, la estimación h'(n) (la que predice el costo hasta el destino) debe ser "admisible". Esto significa que la estimación nunca debe ser mayor que el costo real. Si la estimación es perfecta, A* encuentra el camino de inmediato. Si la estimación es cero, A* se comporta como una búsqueda de "costo uniforme", que explora todos los caminos por igual.
Si la estimación h'(n) no cumple esta condición (es decir, a veces sobrestima el costo), el algoritmo se llama simplemente "A". Aunque seguirá encontrando un camino, no se puede asegurar que sea el de menor costo.
¿Qué tan rápido es A* y cuánta memoria necesita?
Velocidad del algoritmo
La velocidad con la que A* encuentra una solución depende mucho de qué tan buena sea la estimación h'(n) que se use.
- Si la estimación es muy mala, el algoritmo puede ser lento.
- Si la estimación es muy buena (casi perfecta), el algoritmo puede ser muy rápido.
Memoria necesaria
El mayor desafío de A* es la cantidad de memoria que necesita. Como tiene que guardar información sobre muchos posibles caminos, la memoria requerida puede crecer mucho a medida que el problema se hace más grande. Para resolver esto, se han creado otras versiones del algoritmo, como RTA*, IDA* o SMA*, que intentan usar menos memoria.
Observaciones clave sobre A*
- Si la estimación h'(x) es perfecta, A* llega al destino de forma muy rápida.
- Si h'(x) es cero, la búsqueda se basa solo en el costo real recorrido g(x).
- Si h'(x) es cero y g(x) también es cero, la búsqueda sería aleatoria.
- Si h'(x) es cero y g(x) es 1 o una constante, la búsqueda se comporta como una búsqueda de "primero en anchura".
- Si h'(x) nunca sobrestima el costo real, se garantiza encontrar el camino óptimo, aunque a veces se exploren rutas que parecían buenas pero no lo eran tanto.
- Si h'(x) sobrestima el costo real, no se puede asegurar que el camino encontrado sea el de menor costo.
Véase también
En inglés: A* search algorithm Facts for Kids
